Pourquoi ça cycle

En voyant la partie 2, j'ai immédiatement pensé deux choses :

1. il faudrait que j'optimise un minimum ma fonction de cycle d'essorage, parce qu'on va l'appeler un certain nombre de fois, même si ce ne sera pas un milliard de fois ;
2. je vais finir par tomber sur un cycle de cycle en effet.

Ce dernier point est une certitude absolue. Pourquoi donc ? Parce qu'il y a 100 ligne et 100 colonnes, donc moins de 100 ×ばつ 100 = 10.000 positions possibles des pierres qui roulent. En fait, bien moins que ça, parce que les positions occupées par les pierres qui ne roulent pas ne sont pas utilisables, et que seules les dispositions stables par le nord – on se comprend – sont admissibles.

Bref, en moins de 10.000 cycles je suis sûr d'avoir au moins deux fois la même disposition. Et retomber sur une disposition déjà vue, c'est aussi retomber sur la disposition suivante au cycle d'après, etc.

Chez moi ça cycle en 64 cycles.

Le code :

from collections.abc import Iterable, Sequence
from typing import Optional, Self
import enum
import io
import itertools
import numpy as np
import numpy.typing as npt
import aoc
class Tile(enum.Enum):
 EMPTY = '.'
 CUBE = '#'
 ROUND = 'O'
 def __str__(self) -> str:
 if self is self.EMPTY:
 return ' '
 if self is self.CUBE:
 return '■しかく'
 if self is self.ROUND:
 return '○しろまる'
 assert False
class Platform:
 def __init__(self, array: Sequence[Sequence[Tile]]):
 self.matrix: npt.NDArray[np.object_] = np.array(array)
 self.ly, self.lx = self.matrix.shape
 self.spaces_horiz: list[list[range]] = []
 self.spaces_vert: list[list[range]] = []
 for y in range(self.ly):
 self.spaces_horiz.append([])
 xs = [-1] + [x for x in range(self.lx) if self.matrix[y, x] is Tile.CUBE] + [self.lx]
 for x1, x2 in itertools.pairwise(xs):
 if x2 - x1 > 1:
 self.spaces_horiz[-1].append(range(x1 + 1, x2))
 for x in range(self.lx):
 self.spaces_vert.append([])
 ys = [-1] + [y for y in range(self.ly) if self.matrix[y, x] is Tile.CUBE] + [self.ly]
 for y1, y2 in itertools.pairwise(ys):
 if y2 - y1 > 1:
 self.spaces_vert[-1].append(range(y1 + 1, y2))
 @classmethod
 def import_lines(cls, lines: Iterable[str]) -> Self:
 array = []
 for line in lines:
 array.append([Tile(char) for char in line.rstrip()])
 return cls(array)
 def __str__(self) -> str:
 s = io.StringIO()
 for line in self.matrix:
 for tile in line:
 s.write(str(tile))
 s.write('\n')
 return s.getvalue()
 def positions(self):
 return tuple((y, x) for (y, x), value in np.ndenumerate(self.matrix) if value is Tile.ROUND)
 def tilt_north(self) -> None:
 for x in range(self.lx):
 column = self.matrix[:, x]
 for space in self.spaces_vert[x]:
 rounds = 0
 for y in space:
 if column[y] is Tile.ROUND:
 rounds += 1
 column[y] = Tile.EMPTY
 for y in range(space.start, space.start + rounds):
 column[y] = Tile.ROUND
 def tilt_south(self) -> None:
 for x in range(self.lx):
 column = self.matrix[:, x]
 for space in self.spaces_vert[x]:
 rounds = 0
 for y in space:
 if column[y] is Tile.ROUND:
 rounds += 1
 column[y] = Tile.EMPTY
 for y in range(space.stop - 1, space.stop - 1 - rounds, -1):
 column[y] = Tile.ROUND
 def tilt_west(self) -> None:
 for y in range(self.ly):
 row = self.matrix[y]
 for space in self.spaces_horiz[y]:
 rounds = 0
 for x in space:
 if row[x] is Tile.ROUND:
 rounds += 1
 row[x] = Tile.EMPTY
 for x in range(space.start, space.start + rounds):
 row[x] = Tile.ROUND
 def tilt_east(self) -> None:
 for y in range(self.ly):
 row = self.matrix[y]
 for space in self.spaces_horiz[y]:
 rounds = 0
 for x in space:
 if row[x] is Tile.ROUND:
 rounds += 1
 row[x] = Tile.EMPTY
 for x in range(space.stop - 1, space.stop - 1 - rounds, -1):
 row[x] = Tile.ROUND
 def cycle(self) -> None:
 self.tilt_north()
 self.tilt_west()
 self.tilt_south()
 self.tilt_east()
 def load_north(self) -> int:
 load = 0
 for (y, x), tile in np.ndenumerate(self.matrix):
 if tile is Tile.ROUND:
 load += self.ly - y
 return load
def part1(lines: aoc.Data) -> int:
 """Solve puzzle part 1: determine the sum of stuff"""
 platform = Platform.import_lines(lines)
 platform.tilt_north()
 return platform.load_north()
def part2(lines: aoc.Data) -> int:
 """Solve puzzle part 2: determine the sum of staff"""
 platform = Platform.import_lines(lines)
 position_cycles: dict[Tuple[Tuple[int]], int] = {}
 target = 1000000000
 first: Optional[int] = None
 for cycle in range(platform.ly * platform.ly):
 positions = platform.positions()
 if positions in position_cycles:
 first = position_cycles[positions]
 break
 position_cycles[positions] = cycle
 platform.cycle()
 else:
 raise ValueError("cannot find a cycle‽")
 assert first is not None
 # `first` is the number of a cycle when, /before/ cycling, the positions
 # were the same as now.
 # `cycle` is the number of current cycle, /before/ cycling.
 loop = cycle - first
 remaining = target - first
 remaining %= loop
 for _ in range(remaining):
 platform.cycle()
 return platform.load_north()