En Python

Ma première idée fonctionnait sur l'exemple mais pas sur les données réelles : parcourir récursivement une matrice de proche en proche en évitant simplement les endroits où on est déjà passé, ça atteint vite la limites de longueur de la pile d'appels.

Du coup, j'ai fait du Dijkstra. Enfin quelque chose inspiré de son algorithme en tout cas. Ça pourrait être fait de façon entièrement itérative, mais ça ne valait pas la peine, ça reste raisonnable en récursif.

Une fois qu'on a ça, la deuxième partie du puzzle ne pose pas spécialement de problème. Il y a tout de même deux façons de l'implémenter, une bête et méchante (on prend la première solution et on l'applique plusieurs fois), et une un rien plus futée.

from typing import Iterable, Iterator, List, Optional, Set, Tuple
import numpy as np
Coords = Tuple[int, int]
class Map:
 def __init__(self, matrix: np.ndarray) -> None:
 self.matrix = matrix
 self.ly, self.lx = matrix.shape
 def neighs(self, y: int, x: int) -> Iterator[Coords]:
 """Yield neighbours that are reachable from the given coordinates,
 considering movement rules (no climbing)"""
 for (dx, dy) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
 y_ = y + dy
 x_ = x + dx
 if y_ < 0 or y_ >= self.ly or x_ < 0 or x_ >= self.lx:
 continue
 if self.matrix[y_, x_] - self.matrix[y, x] <= 1:
 yield y_, x_
 def _distances(self, starts: Iterable[Coords], end: Coords,
 distances: np.ndarray) -> None:
 """Update distances matrix by computing walking distance from possible
 starts"""
 if starts == []:
 # Nothing left to explore
 return
 nexts = [] # List[Coords]
 for start in starts:
 start_dist = distances[start]
 if start_dist < 0:
 raise ValueError(
 'cannot compute distances from uncharted point')
 for neigh in self.neighs(*start):
 neigh_dist = distances[neigh]
 if neigh_dist < 0 or start_dist + 1 < neigh_dist:
 # This point has either never been checked before, or has
 # been but we have a shorter path to it
 distances[neigh] = start_dist + 1
 nexts.append(neigh)
 # Update distances from the points we have just updated
 self._distances(nexts, end, distances)
 def min_dist(self, starts: List[Coords], end: Coords) -> int:
 distances = np.full_like(self.matrix, -1)
 """Return the minimal distance to reach end, starting from starts"""
 for start in starts:
 distances[start] = 0
 self._distances(starts, end, distances)
 return distances[end]
def import_lines(lines: Iterable[str]) -> Tuple[Map, Coords, Coords]:
 matrix = [] # type: List[List[int]]
 start = None
 end = None
 for y, line in enumerate(lines):
 matrix.append([])
 for x, char in enumerate(line.rstrip()):
 if char == 'S':
 start = (y, x)
 height = 0
 elif char == 'E':
 end = (y, x)
 height = 25
 else:
 height = ord(char) - ord('a')
 matrix[-1].append(height)
 if start is None or end is None:
 raise ValueError("no start or end position found")
 return Map(np.array(matrix)), start, end
def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
 """Solve part 1 of today's puzzle"""
 map_, start, end = import_lines(lines)
 min1 = map_.min_dist([start], end)
 min2 = map_.min_dist([coords for coords, height # type: ignore
 in np.ndenumerate(map_.matrix)
 if height == 0], end)
 return min1, min2