1  from lib import *
 2  
 3  input = read_input(2020, 11)
 4  
 5  lines = input.splitlines()
 6  
 7  graph = {}
 8  active = set()
 9  for y, line in enumerate(lines):
10      for x, c in enumerate(line):
11          if c == ".":
12              continue
13          graph[(x, y)] = []
14          for dy in range(-1, 2):
15              for dx in range(-1, 2):
16                  if dx == 0 == dy:
17                      continue
18                  if 0 <= (i := y + dy) < len(lines) and 0 <= (j := x + dx) < len(line) and lines[i][j] != ".":
19                      graph[(x, y)].append((j, i))
20  
21  while True:
22      new_active = set()
23      for p, qs in graph.items():
24          cnt = sum(q in active for q in qs)
25          if p not in active and not cnt or p in active and cnt < 4:
26              new_active.add(p)
27      if active == new_active:
28          break
29      active = new_active
30  
31  print(len(active))
32  
33  
34  graph = {}
35  active = set()
36  for y, line in enumerate(lines):
37      for x, c in enumerate(line):
38          if c == ".":
39              continue
40          graph[(x, y)] = []
41          for dy in range(-1, 2):
42              for dx in range(-1, 2):
43                  if dx == 0 == dy:
44                      continue
45                  k = 1
46                  while 0 <= (i := y + k * dy) < len(lines) and 0 <= (j := x + k * dx) < len(line):
47                      if lines[i][j] != ".":
48                          graph[(x, y)].append((j, i))
49                          break
50                      k += 1
51  
52  while True:
53      new_active = set()
54      for p, qs in graph.items():
55          cnt = sum(q in active for q in qs)
56          if p not in active and not cnt or p in active and cnt < 5:
57              new_active.add(p)
58      if active == new_active:
59          break
60      active = new_active
61  
62  print(len(active))