Première partie

C'est pour moi l'occasion d'utiliser enum.Flag qui correspond très bien à des trucs qui peuvent avoir une superposition d'états, ici des tuyaux connectés dans différentes directions.

from collections.abc import Iterable, Sequence
from typing import Optional, Self
import enum
import io
import numpy as np
import numpy.typing as npt
import aoc
Coords = tuple[int, int]
class Tile(enum.Flag):
 NORTH = enum.auto()
 SOUTH = enum.auto()
 EAST = enum.auto()
 WEST = enum.auto()
 def __str__(self) -> str:
 if self is self.__class__(0):
 return ' '
 # if self is self.EAST:
 # return '╶'
 # if self is self.WEST:
 # return '╴'
 if self.NORTH in self: # type: ignore
 if self.EAST in self: # type: ignore
 return '╚'
 if self.WEST in self: # type: ignore
 return '╝'
 if self.SOUTH in self: # type: ignore
 return '║'
 # if self is self.NORTH:
 # return '╵'
 if self.SOUTH in self: # type: ignore
 if self.EAST in self: # type: ignore
 return '╔'
 if self.WEST in self: # type: ignore
 return '╗'
 # if self is self.SOUTH:
 # return '╷'
 if self.EAST in self: # type: ignore
 if self.WEST in self: # type: ignore
 return '═'
 # if self is self.WEST:
 # return '╴'
 raise ValueError('unexpected value %s' % repr(self))
 def vector(self) -> Coords:
 if self is self.NORTH:
 return (-1, 0)
 if self is self.SOUTH:
 return (1, 0)
 if self is self.EAST:
 return (0, 1)
 if self is self.WEST:
 return (0, -1)
 raise ValueError('cannot convert multiple directions to vector')
 @classmethod
 def import_char(cls, char: str) -> Self:
 if char == '.' or char == ' ':
 return cls(0)
 if char == '|':
 return cls.NORTH | cls.SOUTH # type: ignore
 if char == '-':
 return cls.EAST | cls.WEST # type: ignore
 if char == 'L':
 return cls.NORTH | cls.EAST # type: ignore
 if char == 'J':
 return cls.NORTH | cls.WEST # type: ignore
 if char == '7':
 return cls.SOUTH | cls.WEST # type: ignore
 if char == 'F':
 return cls.SOUTH | cls.EAST # type: ignore
 raise ValueError('unsupported pipe description %s' % char)

Et la carte maintenant :

class Map:
 def __init__(self, array: Sequence[Sequence[Tile]], start: Coords):
 self.matrix: npt.NDArray[np.object_] = np.array(array)
 self.ly, self.lx = self.matrix.shape
 self.start = start
 @classmethod
 def import_lines(cls, lines: Iterable[str]) -> Self:
 start: Optional[Coords] = None
 array: list[list[Tile]] = []
 for y, line in enumerate(lines):
 array.append([])
 for x, char in enumerate(line.rstrip()):
 if char == 'S':
 start = (y, x)
 array[-1].append(Tile(0))
 else:
 array[-1].append(Tile.import_char(char))
 map_ = cls(array, (0, 0))
 if start is not None:
 y, x = start
 connections = Tile(0)
 if y >= 1 and Tile.SOUTH in map_[y - 1, x]:
 connections |= Tile.NORTH
 if y < map_.ly - 1 and Tile.NORTH in map_[y + 1, x]:
 connections |= Tile.SOUTH
 if x >= 1 and Tile.EAST in map_[y, x - 1]:
 connections |= Tile.WEST
 if x < map_.lx - 1 and Tile.WEST in map_[y, x + 1]:
 connections |= Tile.EAST
 map_[y, x] = connections
 map_.start = start
 return map_
 else:
 raise ValueError('start position not found')
 def neighs(self, coords: Coords) -> Iterable[Coords]:
 y, x = coords
 for direction in self[coords]:
 dy, dx = direction.vector()
 y_, x_ = y + dy, x + dx
 if y_ >= 0 and y_ < self.ly and x_ >= 0 and x_ < self.lx:
 yield y_, x_
 def __getitem__(self, coords: Coords) -> Tile:
 return self.matrix[coords]
 def __setitem__(self, coords: Coords, value: Tile):
 self.matrix[coords] = value
 def __str__(self):
 s = io.StringIO()
 for line in self.matrix:
 for tile in line:
 s.write(str(tile))
 s.write('\n')
 return s.getvalue()
 def farthest(self) -> int:
 distances: npt.NDArray[np.int_] = np.full(self.matrix.shape, -1, dtype=np.int_)
 distance = 0
 currents: set[Coords] = {self.start}
 while len(currents) > 0:
 nexts: set[Coords] = set()
 for current in currents:
 if distances[current] >= 0:
 continue
 distances[current] = distance
 nexts.update(self.neighs(current))
 currents = nexts
 distance += 1
 return distances.max()

La solution est donnée par la méthode Map.farthest(). C'est un parcours itératif de proche en proche :

1. on construit une matrice de distances au point de départ, initialisée avec des -1 partout ;
2. on commence avec une distance courante de zéro et le point de départ comme unique point courant, mais plus tard on en aura plusieurs (en pratique, deux, mais ça pourrait être plus si on avait des tuyaux trifides) ;
3. pour chaque point courant si aucune distance n'a été précédemment relevée, on note la distance courante et on place ses voisins reliés dans l'ensemble des prochains points courants ;
4. on continue, et on ne s'arrête que quand il n'y a plus aucun point courant.