Advent of Code 2016 - Day 24

Useful Links

Concepts and Packages Demonstrated

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

Problem Intro

We need to find the shortest path for a cleaning robot to visit a series of numbered locations in a grid. The grid contains open passages (.), walls (#), and the numbered locations we need to visit.

This is a classic Traveling Salesperson Problem (TSP).

Part 1

What is the fewest number of steps required to visit every non-0 number starting from 0?

My strategy is to break this down into two parts:

Find the shortest distance between every pair of numbered locations.
Find the shortest tour that visits all the locations, starting at 0.

The `LayoutState` Class

To manage the state of our search, I created a LayoutState class. This class encapsulates everything we need to know about a particular state in our search:

The layout of the grid.
The current position of the robot.
The goal position.
The path taken so far.

Using a class like this is a good idea because it makes the code more organized and readable. Instead of passing around multiple variables, we can just pass a single LayoutState object. It also allows us to define custom behavior for comparing states, which is crucial for the priority queue.

Finding Pairwise Distances

To find the shortest distance between each pair of locations, I use a Breadth-First Search (BFS) algorithm. The get_shortest_paths function iterates through all combinations of locations and performs a BFS for each pair.

I use complex numbers to represent the coordinates of the grid. This is a handy trick that simplifies movement. The real part of the complex number is the x-coordinate, and the imaginary part is the y-coordinate. Moving up, down, left, or right is as simple as adding a complex number (e.g., 0-1j for up) to the current position.

def get_shortest_paths(layout:list[str], 
                       locations_to_visit:dict[int,complex], 
                       combos:list[tuple[int, int]]) -> dict[tuple, int]:
    distances:dict[tuple, int] = {}
    
    for location_pair in combos:
        # ... (setup for BFS)
        
        while queue:
            layout_state = heapq.heappop(queue)
            
            if layout_state.position == goal:
                distances[location_pair] = len(layout_state.path)
                break
            
            for new_layout_state in layout_state.yield_next_state():
                if new_layout_state not in explored_states:
                    explored_states.add(new_layout_state)
                    heapq.heappush(queue, new_layout_state)
                    
    return distances

The yield_next_state method uses the yield keyword to create a generator. This is a memory-efficient way to produce the next possible states. Instead of creating a list of all next states, the generator produces them one at a time, as they are needed by the for loop in the BFS.

Priority and Comparison

The BFS is implemented using a priority queue (heapq). The priority of each state is determined by the length of the path taken to reach it. This is defined in the LayoutState class:

    @property
    def priority(self):
        return len(self.path)
    
    def __lt__(self, o) -> bool:
        return self.priority < o.priority

The __lt__ method allows heapq to compare two LayoutState objects based on their priority. A lower priority (i.e., a shorter path) means a higher priority in the queue. This ensures that the BFS explores the grid layer by layer, guaranteeing that the first time we reach the goal, it will be via the shortest path.

Solving the TSP

Once I have the distances between all pairs of locations (our leg-to-distance adjacency dictionary), I can solve the TSP. Since the number of locations is small, I can use a brute-force approach: generate all possible permutations of the locations to visit (starting at 0), calculate the total distance for each permutation, and find the minimum.

I use itertools.permutations to generate the permutations.

def solve_tsp(locations_and_distances, start_location=None, end_location=None) -> dict:
    # ... (setup)

    journey_perms = list(permutations(unique_locations))
    
    if start_location is not None:
        journey_perms = [journey for journey in journey_perms if journey[0] == start_location]
 
    journey_distances = {}
    
    for journey in journey_perms:
        journey_distance = 0
        for i in range(len(journey)-1):
            # ... (calculate distance for each leg of the journey)
        
        journey_distances[journey] = journey_distance
    
    return journey_distances

Part 2

What is the fewest number of steps required to visit every non-0 number starting from 0 and then returning to 0?

This is a simple extension of Part 1. I just need to add location 0 to the end of each permutation before calculating the total distance.

    if end_location is not None:
        journey_perms = [tuple(list(journey) + [end_location]) for journey in journey_perms]

Results

Part 1: Shortest journey: ((0, 4, 1, 2, 7, 3, 6, 5), 448)
Part 2: Shortest journey: ((0, 4, 1, 2, 7, 3, 6, 5, 0), 672)
Execution time: 1.8323 seconds

This was a fun problem that combined graph traversal with a classic computer science problem. The use of BFS to pre-compute the distances between all points of interest is a standard technique for solving TSP on a grid.

‹›