Impossible de se cacher, va falloir tourner.

Comme dans tout les films avec une action répétées pleins de fois, comme de lustrer et frotter, ou peindre des palissades, on a une option pointillés, qui permet de sauter des deux-trois premières itérations directement à la dernière, et de constater, ébahis, les résultats de l'entraînement des padawans, devenu des adultes.

Tout ça pour dire que même avec un cache efficace, tester le cache un milliard de fois, même si on ne calcule vraiment que quelques centaines, ou milliers, d'opérations, ça va être très, très, très long.

Ça ne veut pas dire que le cache est inutile, mais totalement insuffisant.
En pratique, que je le mette ou pas, et ce coup-ci j'ai absolument pensé ma modélisation et toutes mes fonctions, pour avoir un cache le plus efficace possible, ben on gagne quedalle en vitesse, et on sagouine même pas sa RAM, en fait, comme j'ai fait ça super bien, le cache, les caches, ben ils utilisent rien en mémoire.

En fait, tout ce qui compte, c'est de faire des cycles, et de voir quand est-ce qu'on retombe sur un état vu précédemment.
Là on a deux informations : les étapes préalables au démarrage d'un cycle de cycles, et la longueur de ce cycle de cycles.
Si quelqu'un pense, là, maintenant, que j'ai mal choisi mes appellations, il a sans doute raison, c'est bien toute la difficulté du choix d'un bon nom de variable, choix qui n'est pas toujours en O(temps disponible).

Chez moi, on calcule 160 cycles, on boucle sur 77 cycles après 83 cycles de mise en jambe.
Donc avec (1 000 000 000 - 83) modulo 77 = 70, on va chercher le 70^ème cycle de notre cycle de cycles, soit le 83+70=153^ème cycle calculé, c'est l'état final, on le pèse.
Et avec les données de test, on retombe bien sur le 64 prévu, avec un cycle de 7 cycles, et 3 cycles de mise en route, donc 10 cycles calculés, et le milliardième est le 6^ème, youpi !

Mon code est pas super joli, je n'ai pas cherché à factoriser mes fonctions pour glisser vers le nord, sud, est et ouest, donc j'en ai quatre, presque identiques.
Ce qui est plus intéressant, ce sont mes efforts (inutile, mais jolis) pour préparer un cache super efficace et peu gourmand, comme quoi j'ai à la fois appris de mes erreurs passées, et pas du tout appris à anticiper où la difficulté se trouve dans un exercice.
Par contre ça résout l'exercice 1 fastoche avec le code du 2.

Pour comprendre, je considère les problèmes remis à plat, donc une seule chaîne de caractères et on navigue en connaissant la largeur et la hauteur.
Et je stocke ces problèmes dans une dictionnaire avec le hash() en clé. Donc j'appelle mes fonctions avec la valeur de platform qui est un hash(), donc un entier.
Ça veut dire que chaque fonction qui fait glisser les pierres prend en entrée un unique entier, et sort un autre entier.
Autant dire que le cache il pèse pas lourd, il est optimisé, il est efficace (et il est inutile).

Allez, souffrez lecteurs :

from sys import stdin
from functools import cache
def renumerate(sequence, start=None):
 """Reversed enumerate() function
 Can work with generators only if start is given
 """
 n = start
 if start is None:
 n = len(sequence) - 1
 for elem in sequence[::-1]:
 yield n, elem
 n -= 1
class Platform:
 def __init__(self, problem):
 self.width = len(problem[0])
 self.height = len(problem)
 self.size = self.width * self.height
 self.hashes = {}
 self.platform = self.hash("".join(problem))
 # self.print()
 def print(self, platform=None):
 problem = self.hashes[platform or self.platform]
 for y in range(self.height):
 print("|", problem[self.height * y:self.height * (y + 1)])
 def hash(self, problem):
 h = hash(problem)
 if h not in self.hashes:
 self.hashes[h] = problem
 return h
 def get_load(self, platform):
 problem = self.hashes[platform]
 total = [0] * self.width
 for pos, rock in enumerate(problem):
 if rock == "O":
 total[pos % self.width] += self.height - pos // self.width
 return sum(total)
 def turn(self, platform=None):
 @cache
 def _turn(platform):
 platform = self.push_north(platform)
 platform = self.push_west(platform)
 platform = self.push_south(platform)
 platform = self.push_east(platform)
 return platform
 return _turn(platform or self.platform)
 def push_north(self, platform=None):
 @cache
 def _north(platform):
 problem = list(self.hashes[platform])
 empty = list(range(self.width))
 for pos, rock in enumerate(problem):
 x = pos % self.width
 if rock == "O":
 if empty[x] != pos:
 problem[pos] = "."
 problem[empty[x]] = "O"
 empty[x] += self.width
 elif rock == "#":
 empty[x] = pos + self.width
 return self.hash("".join(problem))
 return _north(platform or self.platform)
 def push_south(self, platform=None):
 @cache
 def _south(platform):
 problem = list(self.hashes[platform])
 empty = [self.size - self.width + i for i in range(self.width)]
 for pos, rock in renumerate(problem, self.size - 1):
 x = pos % self.width
 if rock == "O":
 if empty[x] != pos:
 problem[pos] = "."
 problem[empty[x]] = "O"
 empty[x] -= self.width
 elif rock == "#":
 empty[x] = pos - self.width
 return self.hash("".join(problem))
 return _south(platform or self.platform)
 def push_west(self, platform=None):
 @cache
 def _west(platform):
 problem = list(self.hashes[platform])
 empty = [self.height * i for i in range(self.height)]
 for pos, rock in enumerate(problem):
 y = pos // self.width
 if rock == "O":
 if empty[y] != pos:
 problem[pos] = "."
 problem[empty[y]] = "O"
 empty[y] += 1
 elif rock == "#":
 empty[y] = pos + 1
 return self.hash("".join(problem))
 return _west(platform or self.platform)
 def push_east(self, platform=None):
 @cache
 def _east(platform):
 problem = list(self.hashes[platform])
 empty = [self.height * (i + 1) - 1 for i in range(self.height)]
 for pos, rock in renumerate(problem, self.size - 1):
 y = pos // self.width
 if rock == "O":
 if empty[y] != pos:
 problem[pos] = "."
 problem[empty[y]] = "O"
 empty[y] -= 1
 elif rock == "#":
 empty[y] = pos - 1
 return self.hash("".join(problem))
 return _east(platform or self.platform)
resolution = Platform(data)
# Exercice 1 tout facile
print(resolution.get_load(resolution.push_north()))
# Exercice 2
state = resolution.platform
states = [state]
while True:
 state = resolution.turn(state)
 if state in states:
 skip = states.index(state)
 loop = len(states) - skip
 print(f"looping in {loop} cycles after {skip} cycles")
 break
 states.append(state)
state = states[skip + (1000000000 - skip) % loop]
print(resolution.get_load(state))

Bilan : 1,6 secondes et 15Mo de RAM, avec ou sans le cache, c'est pareil, et pas de mauvaise surprise, quand ça a validé les données de test, ça a validé le problème complet.

• Yth.

PS: pour faire plaisir à Tanguy, mon premier jet pour passer l'étape 1 modélisait avec un Enum Rock.RND/SQR/NOP, et ma fonction, unique, était un mix de mes méthodes north et load, tout en une passe, rapide, efficace, pour aller vite fait à l'étape 2.

PPS: je suis resté sur des str au bout du compte, parce qu'une list c'est unhashable, donc je pouvais pas utiliser hash() pour optimiser mes caches (inutiles). Je suppose qu'en revenant à un truc qui fait moins d'explosion de str en list et vice-versa ça doit pouvoir marcher, voire en utilisant un tuple plutôt qu'une liste pour le cache, et une transformation tuple->list->roule_tes_pierres->tuple pour conserver le cache.