Advent of Code 2024-Day 6: Guard Gallivant

from advent import parse, remainder

grid          = (parse(6, list))
width, height = len(grid[0]), len(grid)
rotate        = { '^' : '>', '>' : 'v', 'v' : '<', '<' : '^' }
delta         = { '^' : -1j, '>' : 1,   'v' : 1j,  '<' : -1  }

def get(c):
    x, y = int(c.real), int(c.imag)
    return grid[y][x] if 0 <= x < width and 0 <= y < height else None

def get_guard():
    idx = "".join([ "".join(row) for row in grid ]).find('^')
    return ('^', complex(idx % height, idx // height))

def move(guard):
    g, pos = guard
    pos2   = pos + delta[g]
    ch     = get(pos2)

    match ch:
        case None : return None
        case '#'  : return (rotate[g], pos)
        case _    : return (g, pos2)

def path_positions(guard=get_guard()):
    history = set()

    while guard is not None and guard not in history:
        history.add(guard)
        guard = move(guard)

    return (set(pos for g, pos in history), guard is not None)

def part1():
    return len(path_positions()[0])

def part2():
    def set_ch(pos, ch):
        x, y = int(pos.real), int(pos.imag)
        grid[y][x] = ch

    def is_cycle_with_obstacle(guard, pos):
        set_ch(pos, '#')
        _, cycle = path_positions(guard)
        set_ch(pos, '.')
        return cycle

    guard = get_guard()

    return sum(is_cycle_with_obstacle(guard, pos) for pos in path_positions(guard)[0])

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

assert part1() == 4696
assert part2() == 1443

Parsing

Today we have our first grid map. parse(6, list) gives us a tuple of lists, with one list per line containing our characters. We get width & height in the typical way: width, height = len(grid[0]), len(grid)

Prerequisites

To rotate the guard, we'll use a dictionary with keys being the current position and values being the rotated position:

rotate = { '^' : '>', '>' : 'v', 'v' : '<', '<' : '^' }

To compute the delta for moving the guard, depending on which why they're facing, we'll again use a dictionary with values being complex numbers indicating a two dimensional step:

delta = { '^' : -1j, '>' : 1,   'v' : 1j,  '<' : -1  }

We'll use complex numbers again to represent positions. We'll need a way to get the character at the specified position:

def get(c):
    x, y = int(c.real), int(c.imag)
    return grid[y][x] if 0 <= x < width and 0 <= y < height else None

To get the guard direction and position, we'll convert our grid back into a single string, so we can find the guard character (^) with the str.find() function. Once we have the index, we can compute the x & y coordinates using modular arithmetic. We'll represent the guard information with a 2-tuple. The first element is the direction, and the second element is the position:

def get_guard():
    idx = "".join([ "".join(row) for row in grid ]).find('^')
    return ('^', complex(idx % height, idx // height))

Next, we'll create a move() function to move the guard. We compute the next position, and then check for one of 3 cases:

We're off the grid
We have an obstacle => rotate
We're ok to move

def move(guard):
    g, pos = guard
    pos2   = pos + delta[g]
    ch     = get(pos2)

    match ch:
        case None : return None
        case '#'  : return (rotate[g], pos)
        case _    : return (g, pos2)

Part 1

With the prerequisites in place, the task for part 1 is to find how many positions the guard will occupy as they move. We'll move until we're off the grid or a cycle is detected (we'll need cycle detection for part 2). path_position() returns a 2-tuple of a set of positions and a boolean indicating whether a cycle was detected:

def path_positions(guard=get_guard()):
    history = set()

    while guard is not None and guard not in history:
        history.add(guard)
        guard = move(guard)

    return (set(pos for g, pos in history), guard is not None)

With that, part 1 is simply returning the number of positions:

def part1():
    return len(path_positions()[0])

Part 2

The task for part 2 is to determine how many perfectly positioned obstacles there are. A perfectly positioned obstacle is one that results in the guard getting stuck in a cycle. Our method is a simple one. Take all the positions from part 1, and try putting an obstacle in each position, and test to see if it works. I typically porgram in Racket using an immutable approach, but we'll mutate our grid for this puzzle. Here's a function to set a character at a position in the grid:

def set_ch(x, y, ch):
    grid[y][x] = ch

Next, we need a function to determine if we get a cycle. We'll store each unique guard (direction & position) in a set, so we can detect if we repeat ourselves. Here's the algorithm:

Set an obstacle at pos
Check for a cycle
Unset the obstacle at pos
Return a boolean indicating whether a cycle was detected

def is_cycle_with_obstacle(guard, pos):
    set_ch(pos, '#')
    _, cycle = path_positions(guard)
    set_ch(pos, '.')
    return cycle

With that in place, we just check all the positions from part 1, and sum them up:

sum(is_cycle_with_obstacle(guard, pos) for pos in path_positions(guard)[0])

New Python Concepts

% modulo operator
is not operator
match structural matching
not in operator
str.find()

Conclusion

I always enjoy the Advent of Code grid puzzles, and this was no exception. My first attempt for part 2 was simply to try all positions. This worked, but took 40 seconds. Then I realized I only need to try the positions from part 1, and that dropped the time to 8 seconds. I expect there is a more efficient algorithm, but 8 seconds is fine with me :)