Advent of Code 2024 - Day 6: Guard Gallivant

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
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:

1
 
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:

1
 
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:

1
2
3
 
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:

1
2
3
 
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
1
2
3
4
5
6
7
8
9
 
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:

1
2
3
4
5
6
7
8
 
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:

1
2
 
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:

1
2
 
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
1
2
3
4
5
 
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:

1
 
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 :)