Notebook

Try not to step in the puddles too much¶

https://adventofcode.com/2023/day/17

As has become an Adent of Code tradition, we've been giving a path solving game. The twist is in figuring out what constitutes a 'state' in the path.

At first glance you'd give each position in the grid a state; you'd track the direction, the position, and the number of steps in a single direction. However, the number of steps used to reach a position is actually not all that relevant for any position that then changes direction on the next 'move'; for an equal total heat loss it doesn't matter if it took you 1, 2 or 3 same-direction steps to reach a specific position. Or even if you came from one, or the opposite direction.

Let me illustrate. Here is an example section of grid, and in the middle, at position D-4, is a crucible that moved down into that square, and it'll turn either left or right at the next move:

	A	B	C	D	E	F	G
1
2
3
4				V
5
6
7

Because it can only move up to 3 steps in a single direction, it could reach any of the cells along the row, so A-4, B-4, C-4, E-4, F-4 or G-4. It can't go further than that, it will have to turn on one of those 6 positions, and it then can only go up or down. Let's mark those positions with | bars:

	A	B	C	D	E	F	G
1
2
3
4	\|	\|	\|	V	\|	\|	\|
5
6
7

Now, we can already see that if the crucible had reached this position from below (moving up), the same 6 positions could have been reached.

If the crucible had reached this position from the left or right, then the crucible can only move up or down; it's the same picture as before, but rotated by 90 degrees. Because it doesn't matter if the crucible moved left or right, I've marked the position in the following table with | again, and all the positions it can reach with -:

	A	B	C	D	E	F	G
1				-
2				-
3				-
4				\|
5				-
6				-
7				-

So, for this path finding problem, the individual step states track position and orientation, and we can then generate the next set of steps by making those 6 steps in the two directions and flipping the orientation.

Next, I'm using A* search for this problem and so need a heuristic to prioritise nodes more likely to reach the goal with minimal heat loss. The heuristic must, at most, be equal to the actual final cost of the path. I'm using the manhattan distance between the position and the end goal as the lower bound heat loss, because every cell in the map will incur at least 1 unit of loss. Then, simply add the heat loss of the path so far and we have a great heuristic!

In [1]:

from __future__ import annotations

import typing as t
from dataclasses import dataclass, field
from enum import IntEnum
from heapq import heapify, heappop, heappush
from itertools import count


class PriorityQueue[T]:
    def __init__(self, *initial: tuple[int, T]) -> None:
        self._queue: list[tuple[int, int, T]] = []
        self._count = count()
        for pri, item in initial:
            self.put(pri, item)
        heapify(self._queue)

    def __len__(self) -> int:
        return len(self._queue)

    def put(self, pri: int, item: T) -> None:
        heappush(self._queue, (pri, next(self._count), item))

    def get(self) -> T:
        if not self:
            raise ValueError("Queue is empty")
        return heappop(self._queue)[-1]


class Pos(t.NamedTuple):
    x: int = 0
    y: int = 0

    def __add__(  # pyright: ignore[reportIncompatibleMethodOverride]
        self, other: t.Self
    ) -> t.Self:
        if isinstance(other, Pos):
            return self._replace(x=self.x + other.x, y=self.y + other.y)
        return NotImplemented

    def __sub__(self, other: t.Self) -> int:
        if isinstance(other, Pos):
            return abs(self.x - other.x) + abs(self.y - other.y)
        return NotImplemented


class Orientation(IntEnum):
    # value, -delta, +delta, orthogonal
    hor = 1, Pos(0, -1), Pos(0, 1), "ver"
    ver = 2, Pos(-1, 0), Pos(1, 0), "hor"

    if t.TYPE_CHECKING:
        negd: Pos
        posd: Pos
        _opposite: str

    else:

        def __new__(
            cls, value: int, negd: Pos, posd: Pos, orthogonal: str
        ) -> Direction:
            inst = int.__new__(cls, value)
            inst._value_ = value
            inst.negd, inst.posd, inst._opposite = negd, posd, orthogonal
            return inst

    @property
    def orthogonal(self) -> Orientation:
        return Orientation[self._opposite]


@dataclass(frozen=True, slots=True)
class CruciblePosition:
    pos: Pos
    orientation: Orientation
    heat_loss: int = field(compare=False, default=0)

    def heuristic(self, goal: Pos) -> int:
        return self.heat_loss + (self.pos - goal)

    def moves(self, map: Map) -> t.Iterable[t.Self]:
        orient = self.orientation
        orthogonal = orient.orthogonal
        new = type(self)

        pos, hloss = self.pos, self.heat_loss
        for _ in range(3):
            pos += orient.negd
            if (loss := map.get(pos)) is None:
                break
            hloss += loss
            yield new(pos, orthogonal, hloss)

        pos, hloss = self.pos, self.heat_loss
        for _ in range(3):
            pos += orient.posd
            if (loss := map.get(pos)) is None:
                break
            hloss += loss
            yield new(pos, orthogonal, hloss)


class Map(t.Mapping[Pos, int]):
    _map: dict[Pos, int]
    _goal: Pos

    def __init__(self, map_text: str) -> None:
        lines = map_text.splitlines()
        self._map = {
            Pos(x, y): int(hl)
            for y, line in enumerate(lines)
            for x, hl in enumerate(line)
        }
        self._goal = Pos(len(lines[0]) - 1, len(lines) - 1)

    def __getitem__(self, pos: Pos) -> int:
        return self._map[pos]

    def __iter__(self) -> t.Iterator[Pos]:
        return iter(self._map)

    def __len__(self) -> int:
        return len(self._map)

    def __contains__(self, pos: object) -> bool:
        return pos in self._map

    def least_heat_loss(
        self, crucible_type: type[CruciblePosition] = CruciblePosition
    ) -> int:
        goal = self._goal
        start = Pos()
        open: dict[CruciblePosition, int] = {
            crucible_type(start, Orientation.hor): 0,
            crucible_type(start, Orientation.ver): 0,
        }
        queue: PriorityQueue[CruciblePosition] = PriorityQueue(
            *((cp.heuristic(goal), cp) for cp in open)
        )
        closed: set[CruciblePosition] = set()

        while open:
            current = queue.get()

            if open.get(current) != current.heat_loss:
                # a better path was found already
                continue

            if current.pos == goal:
                return current.heat_loss

            del open[current]
            closed.add(current)
            for neighbor in current.moves(self):
                if neighbor in closed:
                    continue
                if open.get(neighbor, float("inf")) <= neighbor.heat_loss:
                    continue
                open[neighbor] = neighbor.heat_loss
                queue.put(neighbor.heuristic(goal), neighbor)

        raise AssertionError("should never reach here")


test_input = """\
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""
test_map = Map(test_input)
assert test_map.least_heat_loss() == 102

In [2]:

import aocd

map = Map(aocd.get_data(day=17, year=2023))
print("Part 1:", map.least_heat_loss())

Part 1: 1256

Taking bigger steps, further¶

With part two now revealed, I am very pleased with my choice of states for the path search! Because the ultra crucible path is now simply the set of positions between 4 and 10 steps away. We never have to worry about wether or not the crucible has made enough steps to stop at teh end goal here, because a state will never produce a next move that's fewer than 4 steps away.

With A* search pruning the search tree and not having to track states for every single step and direction, part 2 is solved very quickly, in about a second. I also tried a straight up Dijkstra (breath-first) search, without the heuristic, and this doubled the time needed.

In [3]:

class UltraCruciblePosition(CruciblePosition):
    def moves(self, map: Map) -> t.Iterable[t.Self]:
        orient = self.orientation
        orthogonal = orient.orthogonal
        new = type(self)

        pos, hloss = self.pos, self.heat_loss
        for step in range(1, 11):
            pos += orient.negd
            if (loss := map.get(pos)) is None:
                break
            hloss += loss
            if step >= 4:
                yield new(pos, orthogonal, hloss)

        pos, hloss = self.pos, self.heat_loss
        for step in range(1, 11):
            pos += orient.posd
            if (loss := map.get(pos)) is None:
                break
            hloss += loss
            if step >= 4:
                yield new(pos, orthogonal, hloss)


assert test_map.least_heat_loss(UltraCruciblePosition) == 94

In [4]:

print("Part 1:", map.least_heat_loss(UltraCruciblePosition))

Part 1: 1382