Cycle Detection in Simulations
Skip ahead when the state repeats.
Cycle Detection in Simulations is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
When Steps Repeat
Some simulations ask for the state after a huge number of steps, like a trillion. Stepping one at a time would never finish in time. ⏳
States Are Finite
If the number of possible states is limited, the simulation must eventually revisit one. From there it repeats forever in a cycle.
What a Cycle Looks Like
The path has a tail that leads in, then a loop that repeats. Spotting the loop lets you fast-forward past billions of steps.
Remember Where You Have Been
Store each state in a dictionary mapping it to the step number when you first saw it. Seeing it again reveals the cycle.
seen = {}Detect the Repeat
Before each step, check if the current state is already in seen. If it is, you have just closed the loop.
if state in seen:
start = seen[state]Measure the Cycle Length
The length is the current step minus the step you first saw this state. That many steps brings the state right back.
length = step - seen[state]Skip Ahead with Modulo
Subtract the tail, then take the remaining steps modulo the cycle length. Now you only simulate a tiny leftover.
rem = (N - start) % lengthFinish the Leftover Steps
Run the simulation for just those remaining steps from the cycle start. The final state matches step N exactly.
for _ in range(rem):
state = step_fn(state)Keep the State Hashable
Dictionary keys must be hashable, so turn lists into tuples before storing. A mutable state cannot be a key.
key = tuple(row)Floyd Without Memory
If states are too big to store, Floyd's tortoise and hare finds a cycle using two pointers and almost no extra memory.
Why This Saves the Day
Cycle detection turns an impossible trillion-step loop into a few thousand steps. Recognizing repetition is the whole trick.
Quick Check
You first saw the current state at step s, and you are now at step t.
Recap
When states repeat, record each in a map, find the cycle length, skip ahead with modulo, and simulate only the leftover steps. 🚀
Frequently asked questions
Is the “Cycle Detection in Simulations” lesson free?
Yes — the full text of “Cycle Detection in Simulations” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Cycle Detection in Simulations”?
Skip ahead when the state repeats. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Cycle Detection in Simulations” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Model State and Step Forward
- Grid Walks and Direction Vectors
- Cycle Detection in Simulations
- Tame the Tricky Edge Cases