2021-12-09 - Smoke Basin
(original .ipynb)
Day 9 puzzle input is a square grid of integers (mine is here) representing heights of a floor. Part 1 involves finding the sum of lowest points plus 1. Part 2 involves finding the "basins" - the areas surrounding each lowest point which are higher than it (and the points higher than that, and so on) excluding points of height 9.
puzzle_input_str = open("puzzle_input/day9.txt").read() test_input_str = """2199943210 3987894921 9856789892 8767896789 9899965678""" from advent import neighbours4 def parse_line(line): return [int(c) for c in line] def parse_input_lines(input_str): return [parse_line(line) for line in input_str.split("\n")] def is_low_point(grid, r, c): is_low_point = True for nr, nc in neighbours4(grid, r, c): is_low_point = is_low_point and grid[r][c] < grid[nr][nc] return is_low_point def get_low_points(grid): for r, row in enumerate(grid): for c, col in enumerate(row): if is_low_point(grid, r, c): yield (r, c) def part_one(input_str): grid = parse_input_lines(input_str) low_points = get_low_points(grid) return sum(1 + grid[r][c] for r,c in low_points) assert 15 == part_one(test_input_str) print("part one:", part_one(puzzle_input_str))
part one: 423
from advent import grid_to_file def source_and_neighbours(grid, r,c): return [((r,c),(nr,nc)) for nr,nc in neighbours4(grid, r, c)] def part_two(input_str, filename=None): grid = parse_input_lines(input_str) basins = [] for lr,lc in get_low_points(grid): basin = {(lr,lc)} queue = source_and_neighbours(grid, lr, lc) while len(queue) > 0: (r,c), (nr,nc) = queue.pop(0) if grid[nr][nc] == 9: continue if grid[r][c] < grid[nr][nc]: basin.add((nr,nc)) queue += source_and_neighbours(grid, nr, nc) basins.append(len(basin)) if filename: palette = {n:f"#{hex(n)[2:]}00" for n in range(9)} palette[9] = "#fff" grid_to_file(grid, palette, filename, show=True) basins = list(sorted(basins, reverse=True)) return basins[0] * basins[1] * basins[2] assert 1134 == part_two(test_input_str) print("part two:", part_two(puzzle_input_str, filename="day9p2.gif"))
part two: 1198704