Sean McLemon | Advent of Code

2021-12-15 - Chiton

(original .ipynb)

Day 15 puzzle input is a 2D grid representing a cave with digits representing various "risk" values for each tile in a cave (mine is here). Part 1 involves finding a path through this from top-left to bottom-right with the lowest total "risk". Part 2 involves the same but for a grid that is 5x the size (right and down) and kinda repeated with a slight alteration.

puzzle_input_str = open("puzzle_input/day15.txt").read()
test_input_str = """1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""

from advent import neighbours4
from heapq import heapify, heappush, heappop
from math import inf


def parse_input(input_str):
    grid = []
    for line in input_str.split("\n"):
        grid.append([int(c) for c in line])
    return grid


def build_risk_grid(grid):
    risks = []
    for row in grid:
        risks.append([inf] * len(row))
    return risks


def find_path(grid, risk_grid, target_r, target_c):    
    queue = [(0, (0,0))]
    risk_grid[0][0] = 0
    heapify(queue)
    
    while len(queue) > 0:
        risk, (r,c) = heappop(queue)
        if r == target_r and c == target_c:
            return risk
        
        for nr, nc in neighbours4(grid, r, c):
            new_risk = risk + grid[nr][nc]
            if new_risk < risk_grid[nr][nc]:
                risk_grid[nr][nc] = new_risk
                heappush(queue, (new_risk, (nr,nc)))
    
    raise Exception(f"No path to ({target_r}, {target_c}) found")    

    
def part_one(input_str):
    grid = parse_input(input_str)
    risk_grid = build_risk_grid(grid)
    target_r = len(grid)    - 1
    target_c = len(grid[0]) - 1    
    return find_path(grid, risk_grid, target_r, target_c)


assert 40 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))

part one: 393

def build_5x_grid(input_str):
    base_grid = parse_input(input_str)
    grid = []
    for rep_r in range(5):
        for row in base_grid:
            new_row = []
            for rep_c in range(5):
                for c in row:
                    n = c + rep_r + rep_c
                    if n > 9:
                        n -= 9
                    new_row.append(n)
            grid.append(new_row)
    
    return grid


def part_two(input_str):
    grid = build_5x_grid(input_str)
    risk_grid = build_risk_grid(grid)  
    target_r = len(grid)    - 1
    target_c = len(grid[0]) - 1    
    return find_path(grid, risk_grid, target_r, target_c)


assert 315 == part_two(test_input_str)
print("part one:", part_two(puzzle_input_str))

part one: 2823