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.

test_input_str = """1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""

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
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) - 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) - 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