Trois dimensions

Pour ce problème, j'ai considéré qu'on n'était pas vraiment en deux dimensions, mais plutôt en trois. Parce que l'état d'un creuset, ce n'est pas seulement sa position sur le terrain, mais aussi le nombre de cases qu'il a parcouru dans une direction donnée... ce qui se représente également très bien par un nombre, que je considère comme une troisième coordonnée.

Ça permet de se ramener à un problème de parcours de proche en proche, avec une définition bien particulière des voisins d'un point.

Voici le code :

from collections.abc import Iterable, Iterator, Sequence
from typing import Self
import numpy as np
import numpy.typing as npt
import aoc
class City:
 def __init__(self, array: Sequence[Sequence[int]]):
 self.matrix: npt.NDArray[np.ubyte] = np.array(array, dtype=np.ubyte)
 self.ly, self.lx = self.matrix.shape
 @classmethod
 def import_lines(cls, lines: Iterable[str]) -> Self:
 array = [[int(char) for char in line if char != '\n']
 for line in lines]
 return cls(array)
 def walk(self, minturn, maxturn) -> int:
 # We will be using a matrix with three coordinates:
 # * z indicates how many steps were made in which direction:
 # - z < 0: starting, no previous steps!
 # - 0 ≤ z < maxturn: 1 to maxturn steps up ↑
 # - maxturn ≤ z < 2*maxturn: 1 to maxturn steps down ↓
 # - 2*maxturn ≤ z < 3*maxturn: 1 to maxturn steps left ←
 # - 3*maxturn ≤ z < 4*maxturn: 1 to maxturn steps right →
 visits: npt.NDArray[np.int_] = np.full(
 (4 * maxturn, self.ly, self.lx), -1, dtype=np.int_)
 def _neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
 """Yield all directly accessible neighbors of a point, including
 points outside the limits of the city."""
 if z < 0:
 # Special case for start
 yield (0 * maxturn, y - 1, x)
 yield (1 * maxturn, y + 1, x)
 yield (2 * maxturn, y, x - 1)
 yield (3 * maxturn, y, x + 1)
 return
 div, mod = divmod(z, maxturn)
 if div == 0:
 if mod < maxturn - 1:
 yield (z + 1, y - 1, x)
 if mod + 1 >= minturn:
 yield (2 * maxturn, y, x - 1)
 yield (3 * maxturn, y, x + 1)
 return
 if div == 1:
 if mod < maxturn - 1:
 yield (z + 1, y + 1, x)
 if mod + 1 >= minturn:
 yield (2 * maxturn, y, x - 1)
 yield (3 * maxturn, y, x + 1)
 return
 if div == 2:
 if mod + 1 >= minturn:
 yield (0 * maxturn, y - 1, x)
 yield (1 * maxturn, y + 1, x)
 if mod < maxturn - 1:
 yield (z + 1, y, x - 1)
 return
 if div == 3:
 if mod + 1 >= minturn:
 yield (0 * maxturn, y - 1, x)
 yield (1 * maxturn, y + 1, x)
 if mod < maxturn - 1:
 yield (z + 1, y, x + 1)
 return
 def neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
 for z_, y_, x_ in _neighs(z, y, x):
 if 0 <= x_ < self.lx and 0 <= y_ < self.ly:
 yield z_, y_, x_
 currents: dict[tuple[int, int, int], int] = {(-1, 0, 0): 0}
 while len(currents) > 0:
 nexts: dict[tuple[int, int, int], int] = {}
 for current_pos, current_total in currents.items():
 for next_pos in neighs(*current_pos):
 z, y, x = next_pos
 loss = self.matrix[y, x]
 next_total = current_total + loss
 if (visits[next_pos] < 0
 or next_total < visits[next_pos]):
 visits[next_pos] = next_total
 nexts[next_pos] = next_total
 currents = nexts
 loss = -1
 for div in range(4):
 for mod in range(minturn - 1, maxturn):
 z = div * maxturn + mod
 pos = (z, self.ly - 1, self.lx - 1)
 if loss < 0 or 0 < visits[pos] < loss:
 loss = visits[pos]
 return loss
def part1(lines: aoc.Data) -> int:
 """Solve puzzle part 1: determine the minimum total heat loss from start to
 end, using normal crucibles"""
 city = City.import_lines(lines)
 return city.walk(1, 3)
def part2(lines: aoc.Data) -> int:
 """Solve puzzle part 2: determine the minimum total heat loss from start to
 end, using ultra crucibles"""
 city = City.import_lines(lines)
 return city.walk(4, 10)