diff options
author | Nguyễn Gia Phong <mcsinyx@disroot.org> | 2021-12-09 15:55:58 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <mcsinyx@disroot.org> | 2021-12-09 15:55:58 +0700 |
commit | 1606066809130d544aaf722d617a1df5670602cb (patch) | |
tree | 18113b7173853c9f54077bb5918429b97db4d625 /aoc/2021/09/part-two.py | |
parent | cb3888c390e424df9572083e9fcabf0cda4c0506 (diff) | |
download | cp-1606066809130d544aaf722d617a1df5670602cb.tar.gz |
[aoc/2021] Finish day 9
Pathetic me even forgot how to implement forest fire )-;
Diffstat (limited to 'aoc/2021/09/part-two.py')
-rw-r--r-- | aoc/2021/09/part-two.py | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/aoc/2021/09/part-two.py b/aoc/2021/09/part-two.py new file mode 100644 index 0000000..99524c4 --- /dev/null +++ b/aoc/2021/09/part-two.py @@ -0,0 +1,20 @@ +from collections import deque +from functools import reduce +from operator import mul +from sys import stdin + +heightmap = [[int(c) for c in s] for s in stdin.read().strip().split()] +get = lambda y, x: 10 if min(x, y) < 0 or max(x, y) > 99 else heightmap[y][x] +adjacent = lambda y, x: ((y, x + 1), (y + 1, x), (y, x - 1), (y - 1, x)) +basins = {(i, j): 0 for i, row in enumerate(heightmap) + for j, height in enumerate(row) + if all(height < get(y, x) for y, x in adjacent(i, j))} +queue, visited = deque((key, key) for key in basins), set() +while queue: + key, pos = queue.popleft() + if pos in visited: continue + basins[key] += 1 + visited.add(pos) + for adj in adjacent(*pos): + if get(*adj) < 9 and adj not in visited: queue.append((key, adj)) +print(reduce(mul, sorted(basins.values(), reverse=True)[:3])) |