Detecting that the program has entered a loop is a stable in Advent of Code puzzles.
Sometimes, it’s part of the puzzle itself, like day 6 of 2024 (my solution) and sometimes it’s an optimisation trick for a puzzle, like day 8 of 2023 (my solution) that would otherwise keep running for a long long time (or end up in never-ending loop).
For most of the puzzles in Advent of Code cinematic universe, the puzzles are usually built in a way that there are only a couple of variables to consider.
To detect a loop, you generally need two things:
- Keep track of every “step” (see below)
- Check if current “step” has been encountered before
A “step” here means a set up variables that define deterministically what the next result is.
For example, walking through a grid, you need location and direction. If you previously walked up on coordinate (1, 2), unless there’s some randomness or some outside influence, walking up on coordinate (1, 2) later leads to exactly same sequence of steps this second time.
Sometimes the variables are not exactly the same. It could be that you end up in a loop if one of the variables is an exact multiple of N. In the aforementioned day 8 of 2023, we needed to calculate the modulo of the amount of steps taken in relation to the length of instructions because the number of steps was a linear increase from 0 to infinity but the length of instructions was finite.
It’s not always easy to spot when a situation calls for a loop detection when in the middle of solving the puzzle, especially if the variables are not exactly the same.