A Visualization Tool
This is a tricky problem to debug, however visualizing the spread of the virus helps.\nHere is a visualization tool that shows how the grid changes each day.\n1
This is a tricky problem to debug, however visualizing the spread of the virus helps.\nHere is a visualization tool that shows how the grid changes each day.\n1 means the cell is infected and 2 means the cell has been contained with walls.\nHere is an example output with a few notes added:\n\n```html5\n<b>Grid status on day 0: Virus has not begun to spread.</b>\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, <b>1</b>, 0, 0]\n[<b>1</b>, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, <b>1</b>, 0, 0, 0, <b>1</b>, 0, 0, 0]   #\n[0, 0, 0, 0, 0, 0, <b>1</b>, 0, 0, 0]   # Notice this group of 1s will be walled first and will not spread\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, <b>1</b>, 0]\n[0, 0, 0, 0, <b>1</b>, 0, <b>1</b>, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n```\n```html5\n<b>Grid status on day 1</b>\n[0, 0, 0, 0, 0, 0, 0, <b>1</b>, 0, 0]\n[<b>1</b>, 0, 0, 0, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, 0]\n[<b>1</b>, <b>1</b>, <b>1</b>, 0, 0, 0, 0, <b>1</b>, 0, 0]\n[<b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, 0, 0, <b>2</b>, 0, 0, 0]   #\n[0, 0, <b>1</b>, 0, 0, 0, <b>2</b>, 0, 0, 0]   # 2 Means the group of infected nodes has been contained\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, <b>1</b>, 0]   #\n[0, 0, 0, 0, <b>1</b>, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>]   #\n[0, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, 0]   # Three groups of 1s have merged into one large group of 1s.\n[0, 0, 0, 0, <b>1</b>, 0, <b>1</b>, 0, 0, 0]   #\n```\n```html5\n<b>Grid status on day 2</b>\n[<b>1</b>, 0, 0, 0, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, 0]   #\n[<b>1</b>, <b>1</b>, <b>1</b>, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>]   # These two groups will not merge\n[<b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, 0]   # because one of them {(3,6), (4,6)} is walled off\n[<b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, 0, <b>2</b>, <b>1</b>, 0, 0]   #\n[<b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, 0, 0, <b>2</b>, 0, 0, 0]   #\n[0, 0, <b>1</b>, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[0, 0, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, 0, 0, 0]\n```\n```html5\n<b>Grid status on day 3</b>\n[<b>2</b>, 0, 0, 0, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>, <b>1</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, <b>2</b>, <b>1</b>, <b>1</b>, 0]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, 0, <b>2</b>, <b>1</b>, 0, 0]\n[0, 0, <b>2</b>, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[0, 0, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, 0, 0, 0]\n```\n```html5\n<b>Grid status on day 4: Virus fully contained. No growth between day 3 and day 4.</b>\n[<b>2</b>, 0, 0, 0, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, 0]\n[<b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0, 0, <b>2</b>, <b>2</b>, 0, 0]\n[0, 0, <b>2</b>, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>]\n[0, 0, 0, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, <b>2</b>, 0]\n[0, 0, 0, 0, <b>2</b>, 0, <b>2</b>, 0, 0, 0]\n```\n\n<br>\n\nTo print a day by day visualization of the virus spread, run the following **Python3** code with a test-case of your choice as the input:\n\n<br>\n\n```python\nclass Group_By_ID(object):\n    def __init__(self, arr = [[]], walls = set(), day = 0, contained = set()):\n        self.group_id = 0\n        self.group = {}\n        self.node_id = {}\n        self.arr = arr\n        self.walls = walls\n        self.quarantine_not_complete = True\n        self.day = day\n        self.contained = contained\n        self.step()\n        self.show()\n    \n    def step(self) -> None:\n        \'\'\'Identifies groups of infected nodes. Places a wall around the most dangerous group.  Spreads the virus by 1 step.\'\'\'\n        self.get_edges()\n        self.group_infections()\n        self.wall_dangerous_group()\n        self.spread_virus()\n    \n    def show(self) -> None:\n        \'\'\'Prints the current status of the array.\'\'\'\n        print(\'\\nGrid status on day {}\'.format(self.day))\n        for r in range(len(self.arr)):\n            print([2 if (r,c) in self.contained else self.arr[r][c] for c in range(len(self.arr[0]))])\n    \n    def get_edges(self) -> None:\n        \'\'\'Identifies infected_edges between two infected nodes and other_edges that have at least one un-infected node.\'\'\'\n        self.infected_edges = set()\n        self.other_edges = set()\n        R, C = len(self.arr), len(self.arr[0])\n        for r in range(R):\n            for c in range(C):\n                for i, j in ((r,c),(r+1,c),(r-1,c),(r,c+1),(r,c-1)):\n                    if (0 <= i < R) and (0 <= j < C):\n                        edge = ((r, c), (i, j))\n                        if edge not in self.walls:\n                            self.infected_edges.add(edge) if self.arr[i][j] == self.arr[r][c] == 1 else self.other_edges.add(edge)\n        \n    def group_infections(self) -> None:\n        \'\'\'Collects infected edges into groups where each group consists of connected infected nodes.\'\'\'\n        for a, b in self.infected_edges:\n            self.union(a, b)\n    \n    def union(self, a, b) -> None:\n        \'\'\'Connects infected nodes a and b.  Updates the infected groups to reflect the new connection.\'\'\'\n        if (a in self.node_id) and (b in self.node_id) and (self.node_id[a] != self.node_id[b]):\n            self.merge_groups(a, b)\n        elif (a in self.node_id) or (b in self.node_id):\n            self.insert_node(a, b)\n        else:\n            self.create_new_group(a, b)\n    \n    def merge_groups(self, a, b) -> None:\n        \'\'\'Both a and b belong to a group.  Merge the smaller group into the larger group.\'\'\'\n        obsolete_id, target_id = sorted((self.node_id[a], self.node_id[b]), key = lambda id: len(self.group[id]))\n        for node in self.group[obsolete_id]:\n            self.node_id[node] = target_id\n        self.group[target_id] |= self.group[obsolete_id]\n        del self.group[obsolete_id]\n    \n    def insert_node(self, a, b) -> None:\n        \'\'\'Only a or only b belongs to a group, add the new node to the existing group.\'\'\'\n        a, b = (a, b) if a in self.node_id else (b, a)\n        target_id = self.node_id[a]\n        self.node_id[b] = target_id\n        self.group[target_id] |= set([b])\n    \n    def create_new_group(self, a, b) -> None:\n        \'\'\'Node a and node b do not belong to a group, create a new group {a, b}.\'\'\'\n        self.group[self.group_id] = set([a,b])\n        self.node_id[a] = self.node_id[b] = self.group_id\n        self.group_id += 1\n    \n    def wall_dangerous_group(self) -> int:\n        \'\'\'Identifies the most dangerous group and places a wall around it.\'\'\'\n        most_infected_nodes = set()\n        new_walls = set()\n        new_contain = -1\n        R, C = len(self.arr), len(self.arr[0])\n        for g in self.group:\n            projected_infected_nodes = set()\n            projected_infected_edges = set()\n            for r, c in self.group[g]:\n                for i, j in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):\n                    if (0 <= i < R) and (0 <= j < C):\n                        edge = ((r, c), (i, j))\n                        if (edge in self.other_edges) and (edge not in self.walls):\n                            projected_infected_edges.add(edge)\n                            projected_infected_edges.add(edge[::-1])\n                            projected_infected_nodes.add((i, j))\n            if len(projected_infected_nodes) > len(most_infected_nodes):\n                most_infected_nodes = projected_infected_nodes.copy()\n                new_walls = projected_infected_edges.copy()\n                new_contain = g\n        \n        if new_contain != -1: self.contained |= self.group[new_contain]\n        self.walls |= new_walls\n        self.quarantine_not_complete = True if new_walls else False\n    \n    def spread_virus(self) -> None:\n        \'\'\'Spreads virus by one step\'\'\'\n        R, C = len(self.arr), len(self.arr[0])\n        for g in self.group:\n            for r, c in self.group[g]:\n                for i, j in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):\n                    if (0 <= i < R) and (0 <= j < C):\n                        edge = ((r,c),(i,j))\n                        if edge not in self.walls:\n                            self.arr[i][j] = 1\n        \n    def __repr__(self):\n        \'\'\'Returns a dictionary of class attributes that represents the current state of the class instance.\'\'\'\n        return {\'arr\': [row[:] for row in self.arr],\n                \'walls\': self.walls.copy(),\n                \'day\': self.day + 1,\n                \'contained\': self.contained.copy()}\n    \nclass Solution:\n    def containVirus(self, arr: List[List[int]]) -> int:\n        print(\'Grid status on day 0\')\n        for row in arr: print(row)\n            \n        sol = Group_By_ID(arr = arr, walls = set(), day = 1, contained = set())\n        while sol.quarantine_not_complete:\n            sol = Group_By_ID(**sol.__repr__())\n        return len(sol.walls) // 2\n```
[]