Advent of Code 2024 - Day 16: Reindeer Maze

• Table of Contents
• Github
• Day 16

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from advent import parse, grid_to_hash, nx

grid      = grid_to_hash(parse(16, list))
(e,s,w,n) = dirs = (1, 1j, -1, -1j)
start     = (1+139j, e)
goal      = (139+1j, None)
G         = nx.DiGraph()

for pos, val in [ (pos, val) for pos, val in grid.items() if val != '#' ]:
    for dir in dirs:
        G.add_edge((pos, dir), (pos, dir *  1j), weight=1000) # rotate right
        G.add_edge((pos, dir), (pos, dir * -1j), weight=1000) # rotate left

        match grid.get(pos + dir, None):                      # move forward
            case '.': G.add_edge((pos, dir), (pos+dir, dir), weight=1)
            case 'E': G.add_edge((pos, dir), (pos+dir, None), weight=1)

def part1():
    return nx.shortest_path_length(G, source=start, target=goal, weight='weight')

def part2():
    return len({ pos
                 for path in nx.all_shortest_paths(G, start, goal, weight='weight')
                 for pos, _ in path })

# ---------------------------------------------------------------------------------------------

assert part1() == 72428
assert part2() == 456

Parsing

We’re given a maze with the start (S) in the lower left, and the goal (E) in the upper right:

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############

I’ll use the grid_to_hash() function to turn this into a dict with positions (as a complex number) for the keys and characters for the values:

1

grid = grid_to_hash(parse(16, list))

Solution

I usually really like maze search puzzles, and today is no exception, except, I made the mistake of using an undirected graph, instead of a directed graph. There was no consequence to this for part 1, but it made part 2 essentially impossible! I struggled with this for far too long, and eventually decided to bite the bullet, and get some help. Fortunately, I spotted a Python solution that used Digraph() instead of Graph(), and that was the only help I needed! The code that I already had worked fine once I made that change.

Part of my agenda for using Python for Advent of Code this year is to make use of Python’s incredible ecosystem, and the networkx library is part of that. I’ve done plenty of depth first and breadth first searching manually in the past, so today I focused on learning how to use this library.

To create the graph structure, I loop over every position on the map that’s not a wall, and then loop over every direction (east, south, west, north). There are three possibilities for every position: rotate right, rotate left, or move forward. I create an edge for each of these possibilities.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

G = nx.DiGraph()

for pos, val in [ (pos, val) for pos, val in grid.items() if val != '#' ]:
    for dir in dirs:
        G.add_edge((pos, dir), (pos, dir *  1j), weight=1000) # rotate right
        G.add_edge((pos, dir), (pos, dir * -1j), weight=1000) # rotate left

        match grid.get(pos + dir, None):                      # move forward
            case '.': G.add_edge((pos, dir), (pos+dir, dir), weight=1)
            case 'E': G.add_edge((pos, dir), (pos+dir, None), weight=1)

Once the graph is constructed, we’re basically done!

Parts

For part 1, we simply return the length of the shortest path with a function of that name:

1
2

def part1():
    return nx.shortest_path_length(G, source=start, target=goal, weight='weight')

For part 2, we need to find all the nodes that exist on any shortest path. So we compute all shortest paths with a library function, then loop over each path, and then each node of the path, and add the position to a set since we only want unique positions:

1
2
3
4

def part2():
    return len({ pos
                 for path in nx.all_shortest_paths(G, start, goal, weight='weight')
                 for pos, _ in path })

New Python Concepts

• Graph().add_edge()
• networkx library
• nx.all_shortest_paths()
• nx.DiGraph()
• nx.Graph()
• nx.shortest_path_length()

Conclusion

Despite the long struggle today, I’m pleased with the puzzle, and the solution. I don’t like wasting time, but it was gratifying to know I had the correct code all along, and my only mistake was choosing the wrong type of graph. I think that lesson will likely last because of the struggle!

Python and the networkx library helped me make a very concise and readable solution.