How to trace steps in a map, Advent of Code 2024 day 6

Back to my Advent of Code challenge, due to some unforeseeable issues, I am unable to complete the challenges in time and am currently about 5–6 days behind. However, I am still determined to complete the puzzles this year. Today, let’s discuss the 6th puzzle.

Copilot generated image that somewhat suits the theme

Looking for things in a 2D plane seems to be a recurring theme for this year. Today, we are tracing the steps of a guard that has a clear, defined movement logic. The guard moves in a straight line and turns right when it is obstructed.

Assuming we are representing each step the guard takes as a point in a 2D plane, we can then represent each step in a different direction as vectors:

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

By performing some calculations as shown below, we obtain a matrix that represents the right rotation

Deriving the rotation matrix

Originally, this was represented as a dictionary, since we will be heavily relying on it for numerous calculations. However, I wanted to ensure proper type annotations, hence this implementation for now.

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

We also require a means to represent position and movement, along with methods to manipulate position and execute rotations:

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

Defining the dunder/magic methods __add__ and __mul__ enables both Point and Direction objects to be manipulated as if they were standard arithmetic operations within the code. The snippet also demonstrates how to effectively type-annotate the Rotation class.

Lastly, we define the models for our input:

class Symbol(Enum):
    Guard = "^"
    Obstruction = "#"

@dataclass
class Space:
    pass

@dataclass
class Guard:
    pass

@dataclass
class Obstruction:
    pass

@dataclass
class Board:
    tiles: dict[Point, Space | Guard | Obstruction]
    width: int
    height: int

Symbol is a standard Enum that encapsulates the meaning of various symbols within the input. Space, Guard, and Obstruction have self-explanatory meanings. Board is a representation of the map. My initial approach involved a more object-oriented design, but I ultimately opted for this implementation where each class simply maintains a state that can be readily inspected.

Let’s start by parsing the input:

def finder(board: tuple[str, ...], symbol: Symbol) -> Generator[Point, None, None]:
    return (
        Point(x, y)
        for y, row in enumerate(board)
        for x, item in enumerate(tuple(row))
        if item == symbol.value
    )

def parse(input: str) -> tuple[Board, Point]:
    board = tuple(input.strip().splitlines())

    return (
        Board(
            {point: Obstruction() for point in finder(board, Symbol.Obstruction)},
            len(board[0]),
            len(board),
        ),
        next(finder(board, Symbol.Guard)),
    )

The guard is represented by a Point object. The finder function is responsible for scanning the input and identifying the positions of the desired symbol. Similar solutions for 2D map parsing will continue to be explored in subsequent posts.

My solution for part 1 is relatively straightforward. To calculate the guard’s next step:

1. Determine the desired destination directly in front of the guard, based on the current direction vector.
2. Check if the desired destination is obstructed.
3. If the desired destination is obstructed: We return the desired destination, and the current direction vector.
4. If the desired destination is not obstructed: We return the current position, and the rotated direction vector.

def check_is_passable(board: Board, point: Point) -> bool:
    return not isinstance(board.tiles.get(point, Space()), Obstruction)

def guard_rotate(direction: Direction, rotation: Rotation) -> Direction:
    return direction * rotation

def guard_move(
    board: Board, guard: Point, direction: Direction, rotation: Rotation
) -> tuple[Direction, Point]:
    result = ()
    destination = guard + direction

    match check_is_passable(board, destination):
        case True:
            result = direction, destination

        case False:
            result = guard_rotate(direction, rotation), guard

    return result

Finally, we address part 1 of the challenge, which requires determining the number of unique tiles visited by the guard.

def get_visited_tiles(
    board: Board,
    guard: Point,
    rotation: Rotation,
    direction: Direction = DIRECTION_DEFAULT,
) -> dict[Point, bool]:
    tiles = {guard: True}

    while check_is_in_board(board, guard):
        direction, guard = guard_move(board, guard, direction, rotation)

        tiles[guard] = True

    # last tile is outside of the board
    del tiles[guard]

    return tiles

def part1(input: str) -> int:
    return len(get_visited_tiles(*parse(input), rotation=RotateRight()))

Part 2 throws a curveball at us! We’re tasked with finding the perfect spot to place a new object on the map to make our robot patrol in a loop forever.

The good news is, finding the right spot isn’t rocket science. We know the robot’s initial path from Part 1, so we just need to place the object somewhere along that route.

Now, the tricky part: how do we know if we’ve successfully created a loop?

Here’s my approach:

1. Track the robot’s moves: Instead of keeping track of its exact position, I focused on recording each “step” it takes. Each step is basically a move from one tile to the next.
2. Look for repeating patterns: If the robot starts repeating the same sequence of steps, we’ve got a loop!
3. Make sure it stays on the map: Crucially, we need to ensure the robot doesn’t wander off the map.

def check_is_passable_with_new_object(
    board: Board, new_obstacle: Point, point: Point
) -> bool:
    return check_is_passable(board, point) and point != new_obstacle

def guard_move_with_new_obstacle(
    board: Board,
    new_obstacle: Point,
    guard: Point,
    direction: Direction,
    rotation: Rotation,
) -> tuple[Direction, Point]:
    result = ()
    destination = guard + direction

    match check_is_passable_with_new_object(board, new_obstacle, destination):
        case True:
            result = direction, destination

        case False:
            result = guard_rotate(direction, rotation), guard

    return result

def check_is_loopable(
    new_obstacle: Point,
    board: Board,
    guard: Point,
    rotation: Rotation,
    direction=DIRECTION_DEFAULT,
) -> bool:
    result = False

    steps = dict()

    while check_is_in_board(board, guard):
        direction, guard_new = guard_move_with_new_obstacle(
            board,
            new_obstacle,
            guard,
            direction,
            rotation,
        )

        step = (guard, guard_new)
        guard = guard_new

        if step[0] == step[1]:
            continue
        elif steps.get(step, False):
            # condition 2: if current step was attempted, it is a loop
            result = True
            break

        steps[step] = True

    return result

def part2(input: str) -> int:
    board, guard = parse(input)

    tiles = get_visited_tiles(board, guard, rotation=RotateRight())
    del tiles[guard]

    return len(
        tuple(
            filter(
                None,
                (
                    check_is_loopable(tile, board, guard, RotateRight())
                    for tile in tiles
                ),
            )
        )
    )

The reason I chose to store the steps in a dictionary is that the order of the steps doesn’t matter for this part of the problem (which hints at a similar concept in a later puzzle).

Since I needed to frequently check if a particular step had already occurred, storing the steps in a dictionary significantly improved performance. Dictionaries in Python are incredibly fast for lookups, making these checks much quicker compared to using a list or tuple.

My initial attempt, which used a different data structure, took around 70 seconds to run on all 8 cores of my machine. By switching to a dictionary, I was able to significantly reduce the runtime to just a few seconds. This demonstrates the power of choosing the right data structure for the task at hand!

That’s it for today. Considering the runtime improvement from 70 seconds on all cores to just a few seconds on a single core, I’m quite happy with the optimization, although I know further improvements are possible (ideally aiming for sub-second execution).

My previous attempt to score a job didn’t end well (yes, still #OpenToWork, ping me!), as I declined a request for additional assignment/test without compensation. Hopefully, things will improve significantly next year, and I shall write again next week.