Cycli detecteren in simulaties

Sommige simulaties vragen naar de toestand na een enorm aantal stappen, bijvoorbeeld een biljoen. Eén voor één stappen zou nooit op tijd klaar zijn. ⏳

Als het aantal mogelijke toestanden beperkt is, moet de simulatie er uiteindelijk één opnieuw bezoeken. Vanaf dat moment herhaalt alles zich voor altijd in een cyclus.

Het pad heeft een aanloop die naar de lus leidt, waarna de lus zich herhaalt. Als je de lus vindt, kun je miljarden stappen overslaan.

Sla elke toestand op in een woordenboek en koppel die aan het stapnummer waarop je haar voor het eerst zag. Als je haar opnieuw ziet, heb je de cyclus gevonden.

Controleer vóór elke stap of de huidige toestand al in seen staat. Als dat zo is, heb je de lus zojuist gesloten.

De lengte is het huidige stapnummer min het stapnummer waarop je deze toestand voor het eerst zag. Na zoveel stappen kom je precies bij de toestand terug.

Trek eerst de aanloop af en neem daarna het aantal resterende stappen modulo de cycluslengte. Nu hoef je nog maar een klein overgebleven stuk te simuleren.

Voer de simulatie vanaf het begin van de cyclus alleen uit voor die resterende stappen. De eindtoestand komt dan precies overeen met stap N.

Sleutels van een woordenboek moeten hasjbaar zijn, dus zet lijsten om in tupels voordat je ze opslaat. Een veranderlijke toestand kan geen sleutel zijn.

Als toestanden te groot zijn om op te slaan, vindt de methode van Floyd met de schildpad en de haas een cyclus met twee verwijzingen en vrijwel geen extra geheugen.

Cyclusdetectie verandert een onmogelijke lus van een biljoen stappen in een paar duizend stappen. Herhaling herkennen is de hele truc.

Wanneer toestanden zich herhalen, registreer je elke toestand in een tabel, vind je de cycluslengte, sla je stappen over met modulo en simuleer je alleen de overgebleven stappen. 🚀