Advent of Code 2024: Day 16 - Reindeer Maze

Day 16: Reindeer Maze

Today's challenge was perfect timing for usage of Dijkstras Algorithm. A common algorithm used when trying to find the best traversal of nodes based on a "cost" basis.

To clarify:

In some solutions we've used DFS (Depth-First-Search) or BFS (Breadth-First-Search), which are more about how you traverse a graph, and they don't prioritise path costs (with BFS being better for finding the shortest unweighted paths).

Dijkstra's Algorithm specifically seeks the lowest cost path in graphs with weighted edges (our costs).

You can learn more about Dijkstra's algorithm here in a tutorial I find explains it well with diagrams.

Link to Github & Solution

Part 1

What is a PriorityQueue?

Purpose: A PriorityQueue is a data structure that always retrieves the element with the highest priority (lowest priority value for a min-heap).

Operations:

Enqueue: Adds an element with a priority.

Dequeue: Removes and returns the element with the smallest priority value.

In our code, each state (cost, r, c, dr, dc) is added to the queue with a priority value equal to its cost. This ensures that states with lower costs are processed first, which is important for finding the shortest path.

How Does the Algorithm Work?

Key Components:

State Representation: Each state in the grid is represented as a tuple (cost, row, column, dirRow, dirColumn):

cost: The cumulative cost to reach this state.

row, column: The current row and column in the grid.

dirRow, dirColumn: The current movement direction (e.g., moving right or down).

Priority Queue: The priority queue (pq) ensures that states with the smallest cost (priority) are processed first. This is essential for exploring the grid efficiently.

Dequeuing: When pq.Dequeue() is called, it retrieves the state with the lowest cost. This state is processed to check if it reaches the goal (E) or generates new states (based on neighbouring states).

_Adding New Movements: _After processing a state, the algorithm calculates possible next states (new movements) and enqueues them in the PriorityQueue with their respective costs.

Step-by-Step Walkthrough

The starting position (sr, sc) is found where 'S' is located in the grid.

The initial state (0, sr, sc, 0, 1) (cost 0, starting at sr, sc, moving right by default) is enqueued.

Processing States:

The algorithm dequeues the state with the lowest cost.

If the current position contains 'E', the goal is reached, and the cost is printed.

Otherwise, it calculates possible next states based on the current movement direction and adds them to the queue.

_Possible Movements: _For each dequeued state (cost, row, column, dirRow, dirColumn), the algorithm considers three possible movements:

Continue Forward: Move in the same direction (row + dirRow, column + dirColumn) with an additional cost of 1.

Turn Right: Rotate the direction by 90° to the right. This updates the direction to (dirColumn, -dirRow) with an additional cost of 1000.

Turn Left: Rotate the direction by 90° to the left. This updates the direction to (-dc, dirRow) with an additional cost of 1000.

Example:

If moving down (dirRow = 1, dirColumn = 0):

Continue down: (row + 1, column) with cost +1.

_Turn right: _Move right (row, column+ 1) with cost +1000.

Turn left: Move left (row, column - 1) with cost +1000.

Skip invalid movements:

Out-of-bounds (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols).

Blocked cells (grid[newRow,newCol] == '#').

Skip states that have already been seen (to avoid infinite loops).

_Enqueue Valid Movements: _Valid movements are added to the queue with their associated costs. The priority queue ensures that lower-cost states are processed first.

 Why is this so performant?

As new states (possible movements) are added to the queue, the queue organises them based on their costs.

If 'E' is reached, it must be via the shortest-cost path, because all other potential paths with higher costs are still in the queue. This is the beauty of the PriorityQueue, the quickest to reach the 'E' will always be the lowest priority (in our case cost).

We therefore don't need to check remaining queued neighbours / states, as we know these won't be cheaper then our current iteration.

 Part 2

Key Differences From Part 1:

Part 1: Stops when it finds the first shortest route to "E" using a priority queue.

Part 2: Tracks all possible cheapest paths and works backward (using back tracking) to find all grid tiles (nodes) that contribute to any of these paths, then counts the unique values from the seen / visited nodes on the cheapest paths.

As always I hope this has been helpful, and feel free to give me a follow, or reach out on Twitter / X