How to solve Advent of Code 2022 - Day 12 with Python

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

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 matrix A^2 tells you with A^2[i, j] > 0 if you can get from i to j within 2 steps
  • A^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 :D

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... :D