Advent of Code

Today’s puzzle is about following a path under certain initial conditions and – at least for the first part – a simple rule to determine where to go next. Given a grid map such as this one:

We need to “move” from the starting position ^. We start going in the direction of the “arrow” (^, >, v, <). Every time we hit a #, we have to rotate 90Â° clockwise. If we move out of bounds, we stop. We need to keep track of how many unique positions we go through

Once again, a key here will probably be to find the right data structure. I think the easiest thing will be to keep a set of obstacle positions (faster look-up than a list), and to rotate through four directions, which can be stored as tuples of (drow, dcol): (-1, 0) (up), (0, 1) (right), (1, 0) (down) and (0, -1) (left). We also need to be able to check if we’re out of bounds, which is fairly easy as the grid is rectangular. Let’s start by that, keeping it reasonably generic just in case we need to tweak the behaviour later. Since I know I tend to easily forget if I used a (x, y) or a (row, column) convention in positions, I’ll put positions in a namedtuple so that I can explicitly get pos.row and pos.col.

from collections import namedtuple

Position = namedtuple("Position", ["row", "col"])

def is_out_of_bounds(pos: Position, 
                     minbound: Position,
                     maxbound: Position) -> bool:
    return not ((minbound.row <= pos.row <= maxbound.row) and 
                (minbound.col <= pos.col <= maxbound.col))

ORIENTATION_LOOP = {
    Position(-1, 0): Position(0, 1),
    Position(0, 1): Position(1, 0),
    Position(1, 0): Position(0, -1),
    Position(0, -1): Position(-1, 0)
}

def compute_path(initial_pos: Position,
                 initial_orientation: Position,
                 obstacles: set[Position],
                 bounds: tuple[Position, Position]):
    orientation = initial_orientation
    current_pos = initial_pos
    visited_positions: list[Position] = [current_pos]
    while (next_pos := Position(current_pos.row + orientation.row, 
                                current_pos.col + orientation.col)):
        # stop when out of bounds
        if is_out_of_bounds(next_pos, bounds[0], bounds[1]):
            break
        
        # rotate when hitting obstacle
        if next_pos in obstacles:
            orientation = ORIENTATION_LOOP[orientation]
            continue

        # otherwise, move to next
        current_pos = next_pos
        visited_positions.append(current_pos)

    return set(visited_positions)

I initially thought about putting the orientations in a itertools.cycle iterator, but with this “hardcoded” loop I have the advantage of being able to handle a different starting orientation if needed.

This should work, I think, but I still haven’t actually parsed the file to get all the data in the right format. This may be taking things backward but the advantage is that it forces me to think about how the data will need to be stored based on how I find it easier to manipulate it later, rather than be constrained by an initial choice of data representation.

So how to parse the file? It shouldn’t be too hard: we can go through the grid row-by-row, column-by-column. Whenever we hit a #, we add to the set of obstacles. Whenever we hit a ^, <, > or v, we set the initial position and orientation. And from the number of rows and columns, we set the bounds:

def load_map() -> tuple[Position, Position, set[Position], tuple[Position, Position]]:
    data = load_as_str('day6').strip()
    rows = data.split('\n')

    bounds = (Position(0, 0),
              Position(len(rows)-1, len(rows[0])-1))
    obstacles = set()
    initial_pos = None
    initial_orientation = None
    orientations = {
        '^': Position(-1, 0),
        '>': Position(0, 1),
        'v': Position(1, 0),
        '<': Position(0, -1)
    }

    for row, rowdata in enumerate(rows):
        for col, celldata in enumerate(rowdata):
            if celldata == '#':
                obstacles.add(Position(row, col))
            if celldata in orientations:
                initial_pos = Position(row, col)
                initial_orientation = orientations[celldata]
    
    assert initial_pos is not None
    assert initial_orientation is not None

    return initial_pos, initial_orientation, obstacles, bounds

initial_pos, initial_orientation, obstacles, bounds = load_map()
visited_positions = compute_path(initial_pos,
                                 initial_orientation,
                                 obstacles,
                                 bounds)
print(len(visited_positions))

Conclusion: it works! I did have to debug a little bit my original compute_path, which infinitely-looped to begin with because I updated from initial_pos instead of current_pos, which is a mistake that I’ve made a thousand times in different applications and will certainly make a thousand more times in the future.

Part 2 - stuck in a loop

Wow, this is the first puzzle where my initial reaction is “how the hell am I going to do that?” The goal is to find the number of positions where we can add a single obstacle that would cause the path to be stuck in an infinite loop.

I can think of two different routes to take here: either compute the path, then find a rule to determine where I could add something that would cause the path to turn into a loop… or go the brute-force way and try adding an obstacle to every position of the grid and see when that causes a loop.

In any case, I first need to detect an infinite loop. An infinite loop will happen whenever I pass by the same position with the same orientation twice. I don’t record yet the orientation, but I can change the visited_positions to a dict to record that. Then, I can verify at each new position if it has been visited in the same orientation, in which case I can stop.

def compute_path(initial_pos: Position,
                 initial_orientation: Position,
                 obstacles: set[Position],
                 bounds: tuple[Position, Position]) -> tuple[dict[Position, set[Position]],
                                                             bool]:
    orientation = initial_orientation
    current_pos = initial_pos
    visited_positions: dict[Position, set[Position]] = {current_pos: {orientation}}
    while (next_pos := Position(current_pos.row + orientation.row, 
                                current_pos.col + orientation.col)):
        # stop when out of bounds
        if is_out_of_bounds(next_pos, bounds[0], bounds[1]):
            return visited_positions, False
        
        # rotate when hitting obstacle
        if next_pos in obstacles:
            orientation = ORIENTATION_LOOP[orientation]
            continue

        # otherwise, move to next
        current_pos = next_pos
        
        if current_pos not in visited_positions:
            visited_positions[current_pos] = set()

        if orientation in visited_positions[current_pos]:
            # we're in a loop!
            return visited_positions, True

        visited_positions[current_pos].add(orientation)

    # we shouldn't get here
    raise Exception("Something went terribly wrong.")

And the code correctly finds a loop. Good. So here’s my idea to avoid the brute force: I can only add an obstacle on a potential next position. I can then lookup the “next position and orientation if there was an obstacle ahead”, and see if that would cause a loop. It is, unfortunately, a bad idea: it’s possible to enter a loop even if we haven’t gone through that position yet. Still, I can at least limit the search to the “potential next position”. For each of those when computing the original pass, I can recursively call the compute_path method and check if the new path would loop. I just need to make sure not to accidentally enter an infinite recursion loop: when I’m checking for a new obstacle, I don’t need to re-check for new obstacles. That would be bad. I know because that’s what I initially did.

def compute_path(initial_pos: Position,
                 initial_orientation: Position,
                 obstacles: set[Position],
                 bounds: tuple[Position, Position],
                 check_for_new_obstacles: bool = False) -> tuple[dict[Position, set[Position]],
                                                                 bool,
                                                                 set[Position]]:
    orientation = initial_orientation
    current_pos = initial_pos
    visited_positions: dict[Position, set[Position]] = {current_pos: {orientation}}
    looping_obstacles: set[Position] = set()

    while (next_pos := Position(current_pos.row + orientation.row, 
                                current_pos.col + orientation.col)):
        # stop when out of bounds
        if is_out_of_bounds(next_pos, bounds[0], bounds[1]):
            return visited_positions, False, looping_obstacles
        
        # rotate when hitting obstacle
        if next_pos in obstacles:
            orientation = ORIENTATION_LOOP[orientation]
            continue

        # check if adding an obstacle would cause a loop
        if check_for_new_obstacles:
            _, cause_loop, _ = compute_path(initial_pos, 
                                            initial_orientation, 
                                            obstacles.union(set([next_pos])), 
                                            bounds,
                                            False)
            if cause_loop:
                looping_obstacles.add(next_pos)

        # otherwise, move to next
        current_pos = next_pos
        
        if current_pos not in visited_positions:
            visited_positions[current_pos] = set()

        if orientation in visited_positions[current_pos]:
            # we're in a loop!
            return visited_positions, True, looping_obstacles
        
        visited_positions[current_pos].add(orientation)

    # we shouldn't get here
    raise Exception("Something went terribly wrong.")

It works… even though I think this compute_path method is really trying to do too many things at once.

Conclusions

Big step in difficulty here in my opinion. My solution is certainly not the most efficient or the cleanest, but I’m still glad that I was able to avoid the brute-force. On the 129x129 map, I’d have had to check around 16.000 paths for loops. With my method, I cut that down to around 5.500. Good enough for today.

Advent of Code - Day 6

Day 6, Part 1 - Following a path

Part 2 - stuck in a loop

Conclusions