Sean McLemon | Advent of Code

2024-12-10 - Hoof It

(original .ipynb)

puzzle_input_str = open("./puzzle_input/day10.txt").read()
test_input_str = """89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732"""


def parse_input(input_str):
    def inner_parse():
        for r, row in enumerate(input_str.splitlines()):
            yield [int(col) for col in row]
    return list(inner_parse())


def neighbours(grid, r, c):
    max_r = len(grid)
    max_c = len(grid[0])
    candidates = (
        (r-1, c), (r+1, c),
        (r, c-1), (r, c+1)
    )
    for maybe_r, maybe_c in candidates:
        if maybe_r == r and maybe_c == c:
            continue
        if maybe_r >= max_r or maybe_r < 0:
            continue
        if maybe_c >= max_c or maybe_c < 0:
            continue
        yield (maybe_r, maybe_c)

        
def find_trailheads(grid):
    for r, row in enumerate(grid):
        for c, col in enumerate(row):
            if col == 0:
                yield (r, c)

                
def trailhead_score(grid, r, c):
    reachable = set()
    queue = [(r, c)]
    while queue:
        r, c = queue.pop(0)

        if grid[r][c] == 9:
            reachable.add((r, c))
            continue

        for nr, nc in neighbours(grid, r, c):
            if grid[r][c] + 1 == grid[nr][nc]:
                queue.append((nr, nc))
    
    return len(reachable)


def part_one(input_str):
    grid = parse_input(input_str) 
    trailheads = find_trailheads(grid)
    return sum(trailhead_score(grid, r, c) for r,c in trailheads)


assert 36 == part_one(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 778

def trailhead_score(grid, r, c):
    counter = 0
    queue = [(r, c)]
    while queue:
        r, c = queue.pop(0)

        if grid[r][c] == 9:
            counter += 1
            continue

        for nr, nc in neighbours(grid, r, c):
            if grid[r][c] + 1 == grid[nr][nc]:
                queue.append((nr, nc))
    
    return counter


def part_two(input_str):
    grid = parse_input(input_str) 
    trailheads = find_trailheads(grid)
    return sum(trailhead_score(grid, r, c) for r,c in trailheads)


assert 81 == part_two(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 1925