Advent of Code 2016 - Day 22

Useful Links

Concepts and Packages Demonstrated

itertools.permutations Breadth-First Search (BFS)Priority Queues and Heaps Complex Numbers

Problem Intro

We’re presented with a grid of storage nodes. Each node has a size, used space, and available space. We can move data between adjacent nodes, but only if the destination node has enough available space.

Our input looks like this:

/dev/grid/node-x0-y0     90T   69T    21T   76%
/dev/grid/node-x0-y1     92T   72T    20T   78%
...

Part 1

How many viable pairs of nodes are there?

A viable pair of nodes (A, B) is one where:

Node A is not empty.
Nodes A and B are not the same.
The data on node A would fit on node B.

My approach is to first parse the input data using a regular expression to extract the details for each node. I store the nodes in a dictionary, using complex numbers for the coordinates to make indexing easier. This is a neat trick that allows us to represent a 2D grid in a simple, hashable way. The real part of the complex number represents the x-coordinate, and the imaginary part represents the y-coordinate.

Then, I use itertools.permutations to generate all possible pairs of nodes. For each pair, I check if it meets the criteria for a viable pair.

from itertools import permutations

# ... (parsing code)

viable_pairs = defaultdict(list)

perms = permutations(storage_nodes, 2)
for perm in perms:
    node_a = storage_nodes[perm[0]]
    node_b = storage_nodes[perm[1]]
    
    if node_a[USED] > 0 and node_a[USED] <= node_b[AVAIL]:
        viable_pairs[perm[0]].append(perm[1])

viable_pairs_count = sum(len(viable_pairs[node]) for node in viable_pairs)

This is a brute-force approach, but for the size of the input, it’s perfectly fine.

Part 2

What is the fewest number of steps required to move the data from the goal node (top-right) to the access node (top-left)?

This is a shortest path problem. A quick visualization of the grid reveals that there is one empty node, and a wall of “immovable” nodes that are too large to have their data moved. This simplifies the problem significantly.

The `StorageGrid` Class

To solve this, I created a StorageGrid class to represent the state of the grid at any point in our search. This class holds all the information about the grid, including:

The layout of the nodes (movable, immovable, etc.).
The current position of the empty node.
The position of the goal data.
The path the empty node has taken so far.

By encapsulating all this information in a single class, we can treat each state of the grid as a single object. This makes the code much cleaner and easier to work with.

The StorageGrid class also includes methods for generating the next possible states (yield_next_state) and for visualizing the grid (render_grid_as_str).

This approach is a good fit for this problem because it allows us to use standard search algorithms like BFS or A* with minimal modification. The search algorithm doesn’t need to know the details of how the grid works; it just needs to be able to get the next possible states and compare them.

Visualization

To help understand the grid, I created a render_grid_as_str method in my StorageGrid class. This method prints a simplified version of the grid to the console:

    def render_grid_as_str(self) -> str:
        rows = []
        for y in range(self.dims[1]+1):
            row = ""
            for x in range(self.dims[0]+1):
                posn = complex(x, y)
                
                if posn in self.path:
                    row += StorageGrid.TRAVERSED
                else:
                    row += self.nodes[posn]
            
            rows.append(row)
        
        return "\n".join(rows)

This produces output like this:

Ax........................G
.#######################.
.........................
.........................

Where:

A is the access node.
G is the goal node.
_ is the empty node.
. are movable nodes.
# are immovable nodes.
X shows the path the empty node has taken.

This visualization makes it clear that we have a path of movable nodes that we can use to shuffle the empty node around.

Strategy

My strategy is:

Simplify the grid: I create a simplified representation of the grid, as described above.
Move the empty node: I use a Breadth-First Search (BFS) algorithm to find the shortest path to move the empty node from its starting position to the node adjacent to the goal data. To move around the grid, I use a list of vectors represented as complex numbers:
```
VECTORS = [
    0-1j,  # Up
    0+1j,  # Down
    -1+0j, # Left
    1+0j   # Right
]
```
Adding these vectors to a node’s complex coordinate gives the coordinate of the adjacent node.
Move the goal data: Once the empty node is next to the goal data, I can start moving the goal data towards the access node. Each move of the goal data one step to the left requires a sequence of 5 moves: move the empty node up, right, down, down, and then left to get it to the other side of the goal data, ready for the next move.

I implemented the BFS using a priority queue (heapq) to make it an A* search, where the priority is the Manhattan distance to the goal. This helps to find the shortest path more efficiently.

Priority and Comparison

To use the StorageGrid class in a priority queue, I needed to define how to compare two instances. This is done using the __lt__ (less than) and __eq__ (equal) dunder methods.

    @property
    def priority(self):
        return (abs(self.goal.real - self.position.real) + 
                abs(self.goal.imag - self.position.imag))
    
    def __lt__(self, o) -> bool:
        return self.priority < o.priority

    def __eq__(self, o) -> bool:
        if isinstance(o, StorageGrid):
            return self.position == o.position
        else:
            return NotImplemented
    
    def __hash__(self) -> int:
        return hash(self.position)

The priority property calculates the Manhattan distance from the current position of the empty node to the goal. This is a common heuristic for grid-based pathfinding problems.
The __lt__ method allows heapq to compare two StorageGrid objects based on their priority. A lower priority value means a higher priority in the queue.
The __eq__ and __hash__ methods are used to determine if two StorageGrid objects are the same, based on the position of the empty node. This is important for the explored_states set, to avoid visiting the same grid state multiple times.

Here’s the main loop for the BFS:

import heapq

# ... (setup)

queue:list[StorageGrid] = []
explored_states = set()
heapq.heappush(queue, grid)
explored_states.add(grid)

solution_found = False
while queue:
    grid = heapq.heappop(queue)
    
    if (abs(grid.goal.real - grid.position.real) == 1
        and abs(grid.goal.imag - grid.position.imag) == 0):
        solution_found = True
        break
    
    for new_grid in grid.yield_next_state():
        if new_grid not in explored_states:
            explored_states.add(new_grid)
            heapq.heappush(queue, new_grid)

Once the empty node is in position, the total number of moves is the sum of:

The steps to get the empty node next to the goal.
The steps to move the goal data to the access node (5 moves per step).
One final move to get the goal data into the access node.

Results

Viable pairs count = 985
Steps required to move empty node adjacent to goal: 88
Total steps required: 244
Execution time: 0.1101 seconds

This puzzle was a great example of how a problem that seems complex at first can be simplified by visualizing the data and breaking it down into smaller, more manageable steps.

‹›