Detección de ciclos en simulaciones
Avance de golpe cuando el estado se repita
Detección de ciclos en simulaciones es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Cuando los pasos se repiten
Algunas simulaciones piden el estado después de un número enorme de pasos, como un billón. Avanzar de uno en uno no terminaría a tiempo. ⏳
Los estados son finitos
Si el número de estados posibles es limitado, la simulación necesariamente volverá a visitar uno de ellos. A partir de ahí se repite para siempre en un ciclo.
Cómo es un ciclo
El recorrido tiene un tramo inicial que conduce al ciclo y, después, un bucle que se repite. Detectar el bucle permite saltar miles de millones de pasos.
Recuerde por dónde ha pasado
Guarde cada estado en un diccionario que lo asocie con el número de paso en que lo vio por primera vez. Volver a verlo revela el ciclo.
seen = {}Detecte la repetición
Antes de cada paso, compruebe si el estado actual ya está en seen. Si lo está, acaba de cerrar el ciclo.
if state in seen:
start = seen[state]Mida la longitud del ciclo
La longitud es el paso actual menos el paso en que vio este estado por primera vez. Ese número de pasos devuelve el estado exactamente al mismo punto.
length = step - seen[state]Avance de golpe usando el módulo
Reste el tramo inicial y tome los pasos restantes módulo la longitud del ciclo. Así solo tendrá que simular un pequeño resto.
rem = (N - start) % lengthComplete los pasos restantes
Ejecute la simulación solo durante esos pasos restantes desde el inicio del ciclo. El estado final coincidirá exactamente con el del paso N.
for _ in range(rem):
state = step_fn(state)Mantenga el estado hasheable
Las claves de un diccionario deben ser hashable, así que convierta las listas en tuplas antes de almacenarlas. Un estado mutable no puede ser una clave.
key = tuple(row)Floyd sin memoria
Si los estados son demasiado grandes para almacenarlos, el algoritmo de Floyd, con su tortuga y su liebre, encuentra un ciclo usando dos punteros y casi nada de memoria adicional.
Por qué esto le salva el día
La detección de ciclos convierte un bucle imposible de un billón de pasos en unos pocos miles de pasos. Reconocer la repetición es todo el truco.
Comprobación rápida
Vio el estado actual por primera vez en el paso s y ahora se encuentra en el paso t.
Resumen
Cuando los estados se repitan, registre cada uno en un mapa, encuentre la longitud del ciclo, avance usando el módulo y simule solo los pasos restantes. 🚀
Preguntas frecuentes
¿La lección «Detección de ciclos en simulaciones» es gratis?
Sí — el texto completo de «Detección de ciclos en simulaciones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Detección de ciclos en simulaciones»?
Avance de golpe cuando el estado se repita Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Detección de ciclos en simulaciones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Modele el estado y avance paso a paso
- Recorridos de cuadrículas y vectores de dirección
- Detección de ciclos en simulaciones
- Domine los complicados casos límite