2022-12-12 - Hill Climbing Algorithm
(original .ipynb)
Day 12 puzzle input is a grid of letters with the lower-case letters representing heights (a being the lowers, z being the highest) as well as the start point S and the destination E which have heights "a" and "z" respectively (mine is here). Part 1 involves finding the shortest path from S to Z (where you can only travel "up" one height unit). Part 2 involves finding the shortest path from any a-height point to E.
%%time
from advent import neighbours4
from math import inf
puzzle_input_str = open("./puzzle_input/day12.txt").read()
test_input_str = """
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
""".strip()
def get_height_val(col):
if col == "S":
return ord("a")
elif col == "E":
return ord("z")
return ord(col)
def parse_input(input_str):
start, end = None, None
grid = []
for r, row in enumerate(input_str.splitlines()):
if "S" in row:
start = (r, row.index("S"))
if "E" in row:
end = (r, row.index("E"))
grid.append([get_height_val(col) for col in row])
return start, end, grid
def can_reach(grid, r, c, nr, nc):
return grid[nr][nc] <= grid[r][c] + 1
def build_shortest_paths_grid(grid, from_node, reachable=can_reach):
shortest_paths = [
[inf for _ in row]
for row in grid
]
queue = [(from_node, 0)]
while len(queue) > 0:
(r, c), steps = queue.pop(0)
if steps >= shortest_paths[r][c]:
continue
shortest_paths[r][c] = steps
queue += [
[(nr,nc), steps+1]
for nr,nc in neighbours4(grid, r, c)
if reachable(grid, r, c, nr, nc)
]
return shortest_paths
def part_one(input_str):
start, end, grid = parse_input(input_str)
shortest_paths = build_shortest_paths_grid(grid, start)
end_r, end_c = end
return shortest_paths[end_r][end_c]
assert 31 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
part one: 350 CPU times: user 24.1 ms, sys: 3.98 ms, total: 28 ms Wall time: 26.9 ms
%%time
def can_reach_from(grid, r, c, nr, nc):
return can_reach(grid, nr, nc, r, c)
def part_two(input_str):
start, end, grid = parse_input(input_str)
shortest_paths = build_shortest_paths_grid(grid, end, can_reach_from)
a_path_lengths = []
for r, row in enumerate(grid):
for c, col in enumerate(row):
if col == ord("a"):
a_path_lengths.append(shortest_paths[r][c])
return min(a_path_lengths)
assert 29 == part_two(test_input_str)
print("part two:", part_two(puzzle_input_str))
part two: 349 CPU times: user 25.7 ms, sys: 3.72 ms, total: 29.4 ms Wall time: 28.7 ms