commit ef4880478bff5b35ace430b3d96038da2a63483d (patch)
parent 64daca1e4a4aa03a7d1210f08844c913983fbc8f
Author: Alex Karle <alex@alexkarle.com>
Date: Sat, 11 Dec 2021 15:59:47 -0500
day9: Improve pt 2 solution runtime
The old solution of "lowering" to neighbors until nothing changed was
slow and hard to grok (at worst case, you'd have to lower R + C times to
get from the bottom right all the way to the top left..., each time
iterating over all R*C elements).
By using a search (this is DFS using the callstack) we guarantee we only
have to iterate over all R*C once (nodes may be visited multiple times,
but we cache whether they are seen).
Diffstat:
| M | 09/b.py | | | 68 | ++++++++++++++++++++++++-------------------------------------------- |
1 file changed, 24 insertions(+), 44 deletions(-)
diff --git a/09/b.py b/09/b.py
@@ -1,60 +1,40 @@
#!/usr/bin/env python3
import sys
-from math import inf
+from collections import defaultdict
+seen = {}
grid = []
+
for l in sys.stdin:
grid.append([int(x) for x in l.strip()])
-# def debug():
-# print("---")
-# for i in range(100):
-# print([x or 0 for x in C[i]])
-# print("---")
-
-def lowest(r, c):
- pt = C[r][c]
- if r > 0 and C[r-1][c] and C[r-1][c] < pt:
- return False, C[r-1][c]
- if c > 0 and C[r][c-1] and C[r][c-1] < pt:
- return False, C[r][c-1]
- if c < 99 and C[r][c+1] and C[r][c+1] < pt:
- return False, C[r][c+1]
- if r < 99 and C[r+1][c] and C[r+1][c] < pt:
- return False, C[r+1][c]
- return True, C[r][c]
-
-# It's a coloring problem... init the grid
-C = [[None] * 100 for i in range(100)]
+def search(r, c, color):
+ if (r, c) in seen or grid[r][c] == 9:
+ return
+
+ seen[(r, c)] = color
+ if r > 0:
+ search(r - 1, c, color)
+ if c > 0:
+ search(r, c - 1, color)
+ if c < 99:
+ search(r, c + 1, color)
+ if r < 99:
+ search(r + 1, c, color)
+
+
+# Search from each point (no-op once seen once)!
i = 1
for r in range(100):
for c in range(100):
- if grid[r][c] != 9:
- C[r][c] = i
- i += 1
-
-# Now iterate through it and lower to nearest
-changed = True
-while changed:
- # debug()
- changed = False
- for r in range(100):
- for c in range(100):
- if C[r][c]:
- is_lowest, val = lowest(r, c)
- if not is_lowest:
- changed = True
- C[r][c] = val
+ search(r, c, i)
+ i += 1
# Finally, count the colors
-G = {}
-for r in range(100):
- for c in range(100):
- if C[r][c]:
- if C[r][c] not in G:
- G[C[r][c]] = 0
- G[C[r][c]] += 1
+G = defaultdict(int)
+for v in seen.values():
+ G[v] += 1
top = sorted(G.values(), reverse=True)
print(top[0] * top[1] * top[2])
