It would not be an Advent of Code calendar without a path finding challenge. Time to bust out the A* search algorithm again!
For past challenges that were solvable using path finding, see:
from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count
from typing import Final, Iterator, Self, TypeAlias
Pos: TypeAlias = tuple[int, int]
@dataclass(frozen=True)
class HikingNode:
"""Node on the A* search graph"""
x: int
y: int
steps: int = 0
@property
def pos(self) -> Pos:
return self.x, self.y
def cost(self, target: Pos) -> int:
"""Calculate the cost for this node, f(n) = g(n) + h(n)
The cost of this node is the number of steps taken (g) plus estimated
cost to get to end goal (h).
Here we use the manhattan distance to the target as the estimated cost.
"""
return self.steps + abs(target[0] - self.x) + abs(target[1] - self.y)
def transitions(self, heightmap: "HeightMap") -> Iterator[Self]:
height = heightmap[self.x, self.y]
accessible = chr(ord(height) + 1) if height < "z" else "z"
steps = self.steps + 1
positions = (
(self.x + dx, self.y + dy) for dx, dy in ((-1, 0), (0, -1), (0, 1), (1, 0))
)
yield from (
__class__(x, y, steps)
for x, y in positions
if (x, y) in heightmap and heightmap[x, y] <= accessible
)
# once we have read the heightmap, replace the start and end markers with heights
_transmap: Final[dict[int, int]] = str.maketrans("SE", "az")
class HeightMap:
def __init__(self, map: list[str]) -> None:
self._height = len(map)
self._width = len(map[0])
self._start = next(
(x, y) for y, row in enumerate(map) if (x := row.find("S")) >= 0
)
self._target = next(
(x, y) for y, row in enumerate(map) if (x := row.find("E")) >= 0
)
self._map = [row.translate(_transmap) for row in map]
def __getitem__(self, pos: Pos) -> int:
x, y = pos
return self._map[y][x]
def __contains__(self, pos: Pos) -> bool:
x, y = pos
return 0 <= x < self._width and 0 <= y < self._height
def __str__(self) -> str:
return "\n".join(["".join([str(r) for r in row]) for row in self._matrix])
def fewest_steps_needed(self) -> int:
start = HikingNode(*self._start)
open = {start}
unique = count() # tie breaker when costs are equal
pqueue = [(start.cost(self._target), next(unique), start)]
closed = set()
seen = {
start.pos: start.steps
} # pos -> step count. Ignore nodes that took more steps
while open:
node = heappop(pqueue)[-1]
if node.pos == self._target:
return node.steps
open.remove(node)
closed.add(node)
for new in node.transitions(self):
if new in closed or new in open:
continue
if seen.get(new.pos, float("inf")) < new.steps:
continue
seen[new.pos] = new.steps
open.add(new)
heappush(pqueue, (new.cost(self._target), next(unique), new))
example = """\
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
""".splitlines()
test_heightmap = HeightMap(example)
assert test_heightmap.fewest_steps_needed() == 31
import aocd
heightmap = HeightMap(aocd.get_data(day=12, year=2022).splitlines())
print("Part 1:", heightmap.fewest_steps_needed())
Part 1: 352
Where part one was best solved with A* path finding, the second part can best be solved using Breadth-first search; start at the target, and work your way back to find the shortest path to a widening set of locations, until you find an a
stop you can reach. You are guaranteed to find the nearest a
spot this way.
Just remember to reverse the criteria for what is an acceptable next position to try; the preceding letter in the alphabet or higher are acceptable (so go from m
down to l
, stay on m
, or move to n
, o
, p
, etc.).
from collections import deque
class InverseHikingNode(HikingNode):
def transitions(self, heightmap: "HeightMap") -> Iterator[Self]:
height = heightmap[self.x, self.y]
accessible = chr(ord(height) - 1) if height > "a" else "a"
steps = self.steps + 1
positions = (
(self.x + dx, self.y + dy) for dx, dy in ((-1, 0), (0, -1), (0, 1), (1, 0))
)
yield from (
__class__(x, y, steps)
for x, y in positions
if (x, y) in heightmap and heightmap[x, y] >= accessible
)
def shortest_hiking_path(heightmap: HeightMap) -> int:
"""Find the shortest path from a starting point at elevation 'a'."""
start = InverseHikingNode(*heightmap._target)
queue = deque([start])
seen = {start}
while queue:
node = queue.popleft()
if heightmap[node.pos] == "a":
return node.steps
for new in node.transitions(heightmap):
if new not in seen:
seen.add(new)
queue.append(new)
assert shortest_hiking_path(test_heightmap) == 29
print("Part 2:", shortest_hiking_path(heightmap))
Part 2: 345