Sean McLemon | Advent of Code

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