Advent of Code - 2021
This is a solution to Day 15 of Advent of Code 2021.
Day 15 - Chiton
You've almost reached the exit of the cave, but the walls are getting closer together. Your submarine can barely still fit, though; the main problem is that the walls of the cave are covered in chitons, and it would be best not to bump any of them.
The cavern is large, but has a very low ceiling, restricting your motion to two dimensions. The shape of the cavern resembles a square; a quick scan of chiton density produces a map of risk level throughout the cave (your puzzle input). For example:
1163751742 1381373672 2136511328 3694931569 7463417111 1319128137 1359912421 3125421639 1293138521 2311944581You start in the top left position, your destination is the bottom right position, and you cannot move diagonally. The number at each position is its risk level; to determine the total risk of an entire path, add up the risk levels of each position you enter (that is, don't count the risk level of your starting position unless you enter it; leaving it adds no risk to your total).
Your goal is to find a path with the lowest total risk. In this example, a path with the lowest total risk is highlighted here:
1163751742 1381373672 2136511328 3694931569 7463417111 1319128137 1359912421 3125421639 1293138521 2311944581The total risk of this path is 40 (the starting position is never entered, so its risk is not counted).
Read input
from utils import read_input
def transformer(line):
return [int(v) for v in list(line)]
grid = read_input(15, transformer)
Helper functions to calculate score and to print the grid with path walked
def score_path(path, grid):
return sum(grid[y][x] for (x, y) in path if (x,y) != start_position)
def print_grid(grid, path):
m = len(grid)
for row in range(m):
n = len(grid[row])
for col in range(n):
if (col, row) in path:
print(f'({grid[row][col]})',end="")
else:
print(f' {grid[row][col]} ', end="")
print()
Once again we're getting neighbors and I feel like every time my solution is slightly different.
Maybe I should extract this into a utility function one day soon.
def get_neighbors(position, grid):
max_x = len(grid[0])
max_y = len(grid)
x, y = position
all_neighbors = [
(x, y+1),
(x, y-1),
(x-1, y),
(x+1, y)
]
if x-1 < 0:
all_neighbors.remove((x-1, y))
if x+1 >= max_x:
all_neighbors.remove((x+1, y))
if y-1 < 0:
all_neighbors.remove((x, y-1))
if y+1 >= max_y:
all_neighbors.remove((x, y+1))
return all_neighbors
I was expecting to see a path finding puzzle soon in Advent of Code and today we got one.
A* search algorithm is what I remember from algorithm courses and Youtube' game dev log videos so let's use that!
I struggled quite a bit with a few things but for some reason, my main bug was not in my implementation of A* like I imagined but how I used PriorityQueue.
Reading through the A* pseudocode, we need two helpers here, denoted d and h in the Wikipedia algorithm linked above.
Our d function is just the risk value of the position so let's build get_risk.
Our heuristic function h is Manhattan distance which is the sum of |x1 - x2| and |y1 - y2| in 2D space.
def get_risk(position, grid):
x, y = position
return grid[y][x]
def manhattan(pos1, pos2):
return sum((abs(pos1[0] - pos2[0]), abs(pos1[1] - pos2[1])))
The A* function a_star is just an implementation from Wikipedia since I'm nowhere smart enough to figure this stuff out myself.
This was my first time using PriorityQueue which is a queue which returns the smallest value when called .get(). We store (risk, position) combinations there and .get() uses the first value in the tuple to determine priority.
from collections import defaultdict
from queue import PriorityQueue
import math
def reconstruct_path(path, current):
total_path = [current]
while current in path:
current = path[current]
total_path.append(current)
total_path.reverse()
return total_path
def a_star(grid, start, goal, h, d):
open_set = PriorityQueue()
open_set.put((0, start))
path = {}
g_score = defaultdict(lambda: math.inf)
g_score[start] = 0
f_score = defaultdict(lambda: math.inf)
f_score[start] = h(start, goal)
while not open_set.empty():
risk, current = open_set.get()
if current == goal:
return reconstruct_path(path, current)
for neighbor in get_neighbors(current, grid):
tentative_g_score = g_score[current] + d(neighbor, grid)
if tentative_g_score < g_score[neighbor]:
path[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + h(neighbor, goal)
if neighbor not in open_set.queue:
open_set.put((tentative_g_score + h(neighbor, goal), neighbor))
return False
What is the lowest total risk of any path from the top left to the bottom right?
start_position = (0,0)
end_position = (len(grid[0]) - 1, len(grid) - 1)
path = a_star(grid, start_position, end_position, manhattan, get_risk)
score = score_path(path, grid)
print(f'Solution: {score}')
assert score == 741
Solution: 741
Part 2
Now that you know how to find low-risk paths in the cave, you can try to find your way out.
The entire cave is actually five times larger in both dimensions than you thought; the area you originally scanned is just one tile in a 5x5 tile area that forms the full map. Your original map tile repeats to the right and downward; each time the tile repeats to the right or downward, all of its risk levels are 1 higher than the tile immediately up or left of it. However, risk levels above 9 wrap back around to 1. So, if your original map had some position with a risk level of 8, then that same position on each of the 25 total tiles would be as follows:
8 9 1 2 3 9 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7Each single digit above corresponds to the example position with a value of 8 on the top-left tile. Because the full map is actually five times larger in both dimensions, that position appears a total of 25 times, once in each duplicated tile, with the values shown above.
I originally had this brilliant idea that I don't need to actually generate the missing pieces of the grid, just adjust how d and get_neighbors work. But I kept getting wrong answer after wrong answer.
And then I realized, I had jumped into conclusions without reading (again).
I had missed this:
However, risk levels above 9 wrap back around to 1.
So my solution was moot.
Then I caved in (pun intended) and just created a new, expanded grid.
It turned out to be the better solution regardless because it keeps everything else the same.
def expand_grid(grid, n=5):
new_grid = []
l = len(grid)
for y in range(l * n):
new_grid.append([])
for x in range(l * n):
orig_x = x % l
orig_y = y % l
orig_value = grid[orig_y][orig_x]
new_value = (orig_value + x // l + y // l)
if new_value > 9:
new_value = new_value - 9
new_grid[y].append(new_value)
return new_grid
Using the full map, what is the lowest total risk of any path from the top left to the bottom right?
new_grid = expand_grid(grid)
end_position = (len(new_grid[0]) - 1, len(new_grid) - 1)
path = a_star(new_grid, start_position, end_position, manhattan, get_risk)
score = score_path(path, new_grid)
print(f'Solution: {score}')
assert score == 2976
Solution: 2976
Appendix A: Debug path printer
Since the real grids are too big to deal with visually, I want to show what my path printer looks like with the example input.
It's not easy to visualize grids with just ASCII, especially if you want to display any kind of extra information like in this case the path. I chose to surround visited cells with parenthesis and non-visited with empty space.
For boolean grids, I've earlier used a variation of '#" for True or visited and either . or for False or non-visited cells. Both options have their pros and cons.
I added a neat example flag to my input reader so I can easily get the example data in.
example_grid = read_input(15, transformer, example=True)
end_position = (len(example_grid[0]) - 1, len(example_grid) - 1)
path = a_star(example_grid, start_position, end_position, manhattan, get_risk)
print_grid(example_grid, path)
(1) 1 6 3 7 5 1 7 4 2
(1) 3 8 1 3 7 3 6 7 2
(2)(1)(3)(6)(5)(1)(1) 3 2 8
3 6 9 4 9 3 (1)(5) 6 9
7 4 6 3 4 1 7 (1) 1 1
1 3 1 9 1 2 8 (1)(3) 7
1 3 5 9 9 1 2 4 (2) 1
3 1 2 5 4 2 1 6 (3) 9
1 2 9 3 1 3 8 5 (2)(1)
2 3 1 1 9 4 4 5 8 (1)