From 1606066809130d544aaf722d617a1df5670602cb Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Thu, 9 Dec 2021 15:55:58 +0700 Subject: [aoc/2021] Finish day 9 Pathetic me even forgot how to implement forest fire )-; --- aoc/2021/09/part-two.py | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 aoc/2021/09/part-two.py (limited to 'aoc/2021/09/part-two.py') 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])) -- cgit 1.4.1