Juha-Matti Santala

# 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
2311944581
``````

You 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
2311944581
``````

The total risk of this path is 40 (the starting position is never entered, so its risk is not counted).

``````from utils import read_input

def transformer(line):
return [int(v) for v in list(line)]

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

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

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

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