If you missed any previous days, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 β 7 Reasons why you should participate. If you’re here to see the solution of Day 12, continue reading π
Table of Contents
GitHub Repository
https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2022
I will upload all of my solutions there – in the form of Python (or Scala alternatives) notebooks. You have to use your own input for the “input.txt” since everyone gets their own and everyone needs to provide a different solution based on their input.
Day 12 Puzzle
On day 12 of Advent of Code, we had to find the shortest path between S and E on this grid. You can only move up, down, left or right and you can only move to the target tile, if it’s not more than one above you. So if you are at ‘d’, then everything that is ‘e’ or lower(!) is fine.
Basically it’s path finding – if you want to google different algorithms, this is your keyword π
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
As always, I read in all lines:
with open('input.txt', 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
The imports
I used numpy to access the grid – it just has easier indexing functionalities than a list of lists. I used scipy because I did a lot of matrix multiplications, and scipy offers a class for sparse matrices (matrices with very few entries != 0), which helped speed things up a tiny bit.
import numpy as np
from scipy import sparse
The main loop and general idea for part 1
Here’s the idea:
- read letters into numpy grid (2dim array)
- figure out the start and end index if you would flatten the grid (so counting indices from left to right, row after row)
- replace ‘S’ with ‘a’ and ‘E’ with ‘z’, so we can easily use
ord(letter)
to get its ASCII code and compare letter “heights” this way - create an adjacency matrix
- it’s is a square matrix with as many rows as there are fields in the grid (so rows*columns)
- if you can access field j from field i, then
matrix[i, j] = 1
, if not, then it’s 0 - we find out which columns j to set to 1 in each row i by checking the 4 possible neighbors (see function below)
- Adjacency matrices A have the nice feature that if you take
A^2
, this matrixA^2
tells you withA^2[i, j] > 0
if you can get from i to j within 2 stepsA^3[i, j] > 0
means you can get from i to j within 3 steps- and so on
- read more here on Wikipedia: https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers
- create all the matrix powers with increasing n and check when you first get an entry
matrix[start, end] > 0
- Note: all this matrix multiplying took about 5 minutes for the large input on my laptop, so this is far from ideal, but it’s super simple to code and I could do it without googling. But if you want to do it right, probably look for another path finding algorithm.
def solve(file, part=1):
with open(file, 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
grid = np.array([list(row) for row in lines])
# get coordinates of S and E before replacing them
start_coord = np.where(grid.flatten() == 'S')[0][0]
end_coord = np.where(grid.flatten() == 'E')[0][0]
# replace S with a and E with z
grid[np.where(grid == 'S')] = 'a'
grid[np.where(grid == 'E')] = 'z'
if part==2:
start_coord = np.where(grid.flatten() == 'a')[0]
nr_of_fields = grid.shape[0] * grid.shape[1]
# build an adjacency? matrix to document which fields can be reached from which in one step
adj_matrix = np.zeros((nr_of_fields, nr_of_fields))
for i in np.arange(grid.shape[0]):
for j in np.arange(grid.shape[1]):
neighbors_indices = find_reachable_neighbors(grid, i, j)
np.put(adj_matrix[i*grid.shape[1] + j], neighbors_indices, 1)
target_matrix = sparse.csr_matrix(adj_matrix)
adj_matrix = sparse.csr_matrix(adj_matrix)
steps = 1
while (target_matrix.toarray()[start_coord, end_coord] == 0).all() and steps < 500:
if steps % 30 == 0:
print(f"{steps=}")
target_matrix = target_matrix @ adj_matrix
steps += 1
print(steps)
Here is the function for checking the four neighbors and returning the neighbor-indices:
def find_reachable_neighbors(grid, i, j):
neighbors = []
grid_length, grid_width = grid.shape
current_value = grid[i][j]
if 0 < i and \
ord(grid[i-1][j]) <= ord(current_value) + 1:
neighbors.append((i-1)*grid_width + j)
if i + 1 < grid_length and \
ord(grid[i+1][j]) <= ord(current_value) + 1:
neighbors.append((i+1)*grid_width + j)
if 0 < j and \
ord(grid[i][j-1]) <= ord(current_value) + 1:
neighbors.append(i*grid_width + j - 1)
if j + 1 < grid_width and \
ord(grid[i][j+1]) <= ord(current_value) + 1:
neighbors.append(i*grid_width + j + 1)
return neighbors
Part 2
The only adjustment needed for part 2 was that we set every coordinate of ‘a’ (after replacing ‘S’ with ‘a’ too) as a possible start. This means, we also check against every ‘a’ row in our power-matrix which takes a tiny bit longer each iteration.
# the relevant part already included above in the code
if part==2:
start_coord = np.where(grid.flatten() == 'a')[0]
Conclusion
Like I said, all this matrix multiplying took about 5 minutes for the large input on my laptop, so this is far from ideal, but it’s super simple to code and I could do it without googling, which I’m very proud of π
I actually had another idea about doing breadth first search, but I that would have taken me far longer, because I don’t know the details by heart and time is money when you have a full-time job, write a blog post every day and film Vlogmas videos… π
cool, good job.
hey, you are using numpy as well. That will probably speed up implementing the algorithm.
I use pure-python for AoC currently, but may be it is a good chance to take some practice using numpy. π
happy coding.
Oh no, the relevant matrix multiplication part (which takes the longest to run) was done with scipy sparse matrices not numpy. I hoped it would speed things up but it barely made a difference π
I canβt do pure Python, I donβt use many pre-made algorithms but Iβm not implementing a matrix multiplication by myself, that just seems unnecessary π
100% agree. It makes no sense to implement matrix operations.
scipy – oh another cool python library to learn. π