Guard Gallivant

Part 1

Another day, another grid puzzle. And another job for my grids module, which I also used on Day 4.

Today, we’ll be tracking the position of an easily predictable guard through a grid with various obstacles. The guard will have a location in the grid and a direction in which she¹ faces. Luckily, my grids module already has two classes that naturally help us model her behavior: Direction and Position.

Direction allows us to represent the directions up, down, left, and right. Each direction has an offset property (the row/column offset you need to add to move in that direction), and a rotate method that rotates a direction Counter-ClockWise or ClockWise.

from enum import IntEnum

type Rotation = Literal["CCW", "CW"]

class Direction(IntEnum):
    UP = 0
    RIGHT = 1
    DOWN = 2
    LEFT = 3

    def rotate(self, towards: Rotation) -> "Direction":
        offset = 1 if towards == "CW" else -1
        return Direction((self.value + offset) % 4)

    @property
    def offset(self) -> GridPoint:
        return _ROW_COLUMN_OFFSETS[self]

_ROW_COLUMN_OFFSETS: dict[Direction, GridPoint] = {
    Direction.UP: (-1, 0),
    Direction.RIGHT: (0, 1),
    Direction.DOWN: (1, 0),
    Direction.LEFT: (0, -1),
}

And Position is essentially a grid location with a facing direction — with a few convenience methods for stepping forward and rotating. This will be our representation of the gallivanting guard.

class Position(NamedTuple):
    point: GridPoint
    facing: Direction

    @property
    def next_point(self) -> GridPoint:
        return add_points(self.point, self.facing.offset)

    def step(self) -> Self:
        return type(self)(self.next_point, self.facing)

    def rotate(self, towards: Rotation) -> Self:
        return type(self)(self.point, self.facing.rotate(towards))

If you want to see another example of the Position class in action, I’d encourage you to check out my solution to 2023 Day 16, where I used it to model beams of light. Otherwise, if the use of these classes seems clear so far, read on!

To create our guard, we’ll need two pieces of information: her starting point, and her facing direction. She starts at the location of the ^ character — which we can find using a generator inside of next() — and facing up.

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid = parse_grid(self.input)
        guard = Position(
            point=next(k for k, v in grid.items() if v == "^"),
            facing=Direction.UP,
        )
        ...

We’ll want to track the guard, making sure she follows her strict protocol until she exits the grid. This seems like a good thing to put into a function.

Because we want to count only the unique points the guard has seen, we’ll track those points in a set that we return once we’re done. After we track the guard’s current point, she will follow her protocol: turn clockwise if about to walk into an obstacle, otherwise step forward.

def track_guard(grid: Grid[str], guard: Position) -> set[GridPoint]:
    seen: set[GridPoint] = set()

    while guard.point in grid:
        seen.add(guard.point)

        if grid.get(guard.next_point) == "#":
            guard = guard.rotate("CW")
        else:
            guard = guard.step()

    return seen

We also return the set of seen points, so we can count them with len to get our answer.

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        ...
        points_seen = track_guard(grid, guard)
        return len(points_seen)

Of course, this assumes that the guard will always eventually exit the grid; if she didn’t, and her path went into some sort of loop contained within the grid, the track_guard function would never finish. Though an infinite loop doesn’t happen in our case (because Eric Wastl is nice), this possibility is something to keep in mind.

Part 2

As it turns out, we want the guard to get into an infinite loop — and we’ll accomplish this by placing some obstacle somewhere in the grid. But before we do that, we’ll have to ensure that our track_guard function can handle this scenario.

Two changes will need to be made to track_guard:

1. If the guard eventually exits the grid, we’ll still return the set of seen locations. But if the guard gets stuck in an infinite loop, we’ll want to return a different value that we can create a special check for. The obvious choice here would seem to be None, as there is no path that exits the grid.
2. Rather than tracking only the seen locations, we’ll want to track the seen positions — with both location and direction — so we can detect a loop if the guard revisits a previously-seen position. We’ll still want to return only the locations, though, so we can use a set comprehension to get each position’s grid point.

def track_guard(grid: Grid[str], guard: Position) -> set[GridPoint] | None:
    path: set[Position] = set()

    while guard.point in grid:
        if guard in path:
            return None
        path.add(guard)

        if grid.get(guard.next_point) == "#":
            guard = guard.rotate("CW")
        else:
            guard = guard.step()

    return {p.point for p in path}

Our track_guard function will now return None if the guard gets into an infinite loop, and will otherwise act the same as before. At this point, it’s a good idea to assert that the set of seen points will not be None for our Part 1 solution.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        grid = parse_grid(self.input)
        guard = Position(
            point=next(k for k, v in grid.items() if v == "^"),
            facing=Direction.UP,
        )
        points_seen = track_guard(grid, guard)
        assert points_seen is not None

        ...  # TODO Add count-obstacle-placements code

        return len(points_seen), ...

Now we can try placing obstacles in the grid. An obstacle can be placed on any empty tile (i.e. without a guard or another obstacle), so let’s first try brute-forcing all possible obstacle placements and tallying the ones that get the guard stuck in a loop.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        ...

        num_obstacle_placements = 0
        for obstacle_point in grid:
            # An obstacle can only be placed on an empty tile
            if grid[obstacle_point] != ".":
                continue

            # Try placing an obstacle here
            grid[obstacle_point] = "#"
            blocked_points = track_guard(grid, guard)
            # If the guard got stuck in a loop, tally this placement
            if blocked_points is None:
                num_obstacle_placements += 1
            # Un-place the obstacle
            grid[obstacle_point] = "."

        return len(points_seen), num_obstacle_placements

This brute-force approach works, but it takes almost a full minute to run on my machine. A better approach would be to only try placing obstacles along the guard’s original path, as those points are the only ones the guard would run into.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        ...

        for obstacle_point in points_seen:
            ...

        ...

This already reduces the runtime to ~11.7 seconds on my machine — a massive improvement! But can we do better?

Whenever a new obstacle placement is tried, the guard has to walk along her original path up to that obstacle, and it’s only afterwards that her path diverges. So if track_guard returned the positions along the guard’s path, instead of only the locations, perhaps the traversal of this path up to the new obstacle could be done faster.

But how should we represent these positions? It’s not exactly obvious which data structure to use.

• The path positions must be in order from earliest to latest, which suggests that we should use a list of Positions.
• Checking whether a path position was already seen should be fast, which suggests that we should use a set of Positions.
• If we use a list to place the positions in order, we won’t have fast membership checking. But if we use a set to allow for fast membership checking, we lose the ability to place them in order.²

In effect, what we need is some sort of “ordered set”. Does such a data structure exist in Python? Technically, it does: the humble dict.

• Checking whether an item with a certain key exists in a dict is very fast; both sets and dicts use an object’s “hash value” to check its membership.
• As of Python 3.7, dicts remember the order in which new keys are inserted.

So if we use the keys of a dict to store the path positions — using None as the associated value, because it doesn’t matter — we get the exact “ordered set” behavior we want!

>>> d = {}
>>> d["one"] = None
>>> d["two"] = None
>>> d["three"] = None
>>> d
{"one": None, "two": None, "three": None}
>>> list(d)
["one", "two", "three"]

We can use this knowledge to improve the runtime of our solution, but it’ll take a bit of refactoring.

First, we’ll change track_guard so that it uses a dict to track positions along the path, and returns those positions as a list (instead of the locations as a set). As stated, these path positions will remain in the order that they were inserted into the dict.

def track_guard(grid: Grid[str], guard: Position) -> list[Position] | None:
    path: set[Position] = set()
    # HACK This dict is being used as an "ordered set", so to speak. It
    # stores the positions in order (with values of None), and we can
    # quickly check whether it contains a certain position.
    path: dict[Position, None] = {}

    while guard.point in grid:
        if guard in path:
            return None
        path.add(guard)
        path[guard] = None

        if grid.get(guard.next_point) == "#":
            guard = guard.rotate("CW")
        else:
            guard = guard.step()

    return {p.point for p in path}
    return list(path)

Next, we’ll tweak our Part 1 solution to leave this new path positions list as is, and then use it to construct the points_seen set.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        grid = parse_grid(self.input)
        guard = Position(
            point=next(k for k, v in grid.items() if v == "^"),
            facing=Direction.UP,
        )
        path = track_guard(grid, guard)
        assert path is not None
        points_seen = {p.point for p in path}
        ...

Finally, we can implement the actual speedup. In Part 2, instead of starting each gallivant from the guard’s starting position, we can start from the path position just before the guard would hit the newly placed obstacle; after all, the path will be identical up to that point. (This is why we saved the initial path: to avoid recalculating it each time.)

The way we can find this path position is by using next; we’ll be looking for the “next” path position where the guard would overlap the obstacle if she stepped forward.³

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        ...
        num_obstacle_placements = 0
        for obstacle_point in points_seen:
            # An obstacle can only be placed on an empty tile
            if grid[obstacle_point] != ".":
                continue

            # Try placing an obstacle here
            grid[obstacle_point] = "#"
            # NOTE Because the guard's path will be identical up to the
            # obstacle, we can start the guard directly before it.
            blocked_guard = next(
                p for p in path if p.next_point == obstacle_point
            )
            blocked_path = track_guard(grid, blocked_guard)
            # If the guard got stuck in a loop, tally this placement
            if blocked_path is None:
                num_obstacle_placements += 1
            # Un-place the obstacle
            grid[obstacle_point] = "."

        return len(points_seen), num_obstacle_placements

Believe it or not, this approach ends up considerably faster; the new runtime is ~5.7 seconds on my machine. I think that’s about as good as I can do while still keeping the code simple.