Clumsy Crucible

Published: 2023-12-25 Original Prompt

Part 1

When you see “efficient pathfinding”, Dijkstra’s algorithm is a good place to start! There are a number of other options (like A*), but I’ve got a soft spot for this one.

Like yesterday, we’ll be parsing a grid and “walking” around it. I’ve gone ahead and promoted that Direction enum to my graph utils so we’ll be using it again. It’ll cover our rotations and offsets:

from enum import IntEnum

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


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

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

    @staticmethod
    def offset(facing: "Direction") -> GridPoint:
        return _ROW_COLL_OFFSETS[facing]


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

Dijkstra’s is a simple and elegant algorithm. I’ve covered many times before. Check those out if you want to know the nuts and bolts of the approach. Today I’m going to focus on what makes this puzzle unique: having to track direction and steps taken.

Normally Dijkstra is only concerned with the cost to reach a position. But because there are restrictions on how far we can travel today, we have to track our current heat level and direction (which informs which neighbors we can move to). Our State will be tuple[int, Position, int], which holds:

tracking cost (aka heat)
a Position class that knows our location and direction (copied yesterday’s State class and removed its next_states)
the number of steps taken in this direction

Let’s get the high level parts of our solution down:

from heapq import heappop, heappush
...

State = tuple[int, Position, int]


class Solution(StrSplitSolution):
    def part_1(self) -> int:
        # bottom-right corner of the grid
        target = len(self.input) - 1, len(self.input[-1]) - 1
        grid = {k: int(v) for k, v in parse_grid(self.input).items()}

        # start walking both directions
        queue: list[State] = [
            (0, Position((0, 0), Direction.DOWN), 0),
            (0, Position((0, 0), Direction.RIGHT), 0),
        ]
        seen: set[tuple[Position, int]] = set()

        while queue:
            cost, pos, num_steps = heappop(queue)

            if pos.loc == target:
                return cost

            if (pos, num_steps) in seen:
                continue
            seen.add((pos, num_steps))

            # TODO: queue states

        return -1

We build a list of State objects and add/remove items using Python’s built-in heapq class (a priority queue implementation; docs). Whenever we consider a State, because the queue is always sorted, we know we have the cheapest way to reach that point (and direction and number of steps left).

If that state’s location is the target, we’re done and must have found the fastest way there! If we’ve been to this location after the same number of steps before, we can skip it (we must have been here at a worse cost, which isn’t useful). We don’t have to track direction because it doesn’t matter how we landed on this position- we can always turn (at least). We finish the “checks” part by adding this point as visited and queue next steps.

To queue steps, we check if that move is valid. It’s valid if it’s in-grid and (if moving forward) we’ve gone less than 2 steps in this direction. That’s not too bad thanks to the step, rotate_and_step, and Python’s walrus operator (which lets us bind variables inside other expressions):

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        ...

        while queue:
            cost, pos, num_steps = heappop(queue)
            ...

            if (left := pos.rotate_and_step("CCW")).loc in grid:
                heappush(queue, (cost + grid[left.loc], left, 1))

            if (right := pos.rotate_and_step("CW")).loc in grid:
                heappush(queue, (cost + grid[right.loc], right, 1))

            if num_steps < 3 and (forward := pos.step()).loc in grid:
                heappush(queue, (cost + grid[forward.loc], forward, num_steps + 1))

Each time we turn, we reset num_steps back to 1. Otherwise, if we’re still under 3 steps, we increment num_steps and move forward. By only adding states that conform to the rules, we don’t have to do any validity checking when reaidng points, only writing them. This will think for a second or so and we’ll have our answer for part 1!

Part 2

Part 2 is much the same as part 1, but our parameters for the min and max travel distance have changed. We can actually do this is about 3 lines:

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
    def _solve(self, min_steps: int, max_steps: int) -> int:
        ...

        while queue:
            cost, pos, num_steps = heappop(queue)

            if pos.loc == target and num_steps >= min_steps: # 1
                return cost

            ...

            if (
                num_steps >= min_steps # 2
                and (left := pos.rotate_and_step("CCW")).loc in grid
            ):
                heappush(queue, (cost + grid[left.loc], left, 1))

            if (
                num_steps >= min_steps # 2
                and (right := pos.rotate_and_step("CW")).loc in grid
            ):
                heappush(queue, (cost + grid[right.loc], right, 1))

            if num_steps < max_steps and (forward := pos.step()).loc in grid: # 3
                heappush(queue, (cost + grid[forward.loc], forward, num_steps + 1))

        return -1

    def part_1(self) -> int:
        return self._solve(0, 3)

    def part_2(self) -> int:
        return self._solve(4, 10)

The changes:

we can only land on the target if we’ve gone the minimum number of steps
we can’t turn unless we’re past our minimum
we only step forward if we’re under the minimum (just like part 1)

Not so bad, overall. Unfortunately, this runs both parts in ~ 8.5 seconds, which is way longer than I want. I could queue way fewer points if I jump forward by min_steps and collect the head along the way. I might also be able to get away with storing a simpler state, but some light experimentation with that hasn’t been promising. I may circle back, but I may leave this one here for now.