Detecção de Ciclos em Simulações

Algumas simulações pedem o estado após um número enorme de passos, como um trilhão. Avançar um passo de cada vez nunca terminaria a tempo. ⏳

Se o número de estados possíveis for limitado, a simulação necessariamente revisitará algum deles. A partir daí, ela se repetirá para sempre em um ciclo.

O caminho tem uma cauda que leva até um laço que se repete. Identificar o laço permite avançar rapidamente por bilhões de passos.

Armazene cada estado em um dicionário, associando-o ao número do passo em que você o viu pela primeira vez. Vê-lo novamente revela o ciclo.

Antes de cada passo, verifique se o estado atual já foi visto. Se foi, você acabou de fechar o ciclo.

O comprimento é o passo atual menos o passo em que você viu esse estado pela primeira vez. Essa quantidade de passos traz o estado de volta exatamente ao mesmo ponto.

Subtraia a cauda e, depois, calcule os passos restantes módulo o comprimento do ciclo. Agora você só precisa simular uma pequena sobra.

Execute a simulação apenas durante esses passos restantes, a partir do início do ciclo. O estado final será exatamente o mesmo do passo N.

As chaves de um dicionário precisam ser compatíveis com hash, então transforme listas em tuplas antes de armazená-las. Um estado mutável não pode ser uma chave.

Se os estados forem grandes demais para serem armazenados, o algoritmo da tartaruga e da lebre de Floyd encontra um ciclo usando dois ponteiros e quase nenhuma memória extra.

A detecção de ciclos transforma um laço impossível de um trilhão de passos em alguns milhares de passos. Reconhecer a repetição é todo o truque.

Você viu o estado atual pela primeira vez no passo s e agora está no passo t.

Quando os estados se repetirem, registre cada um em um mapa, encontre o comprimento do ciclo, avance usando o módulo e simule apenas os passos restantes. 🚀