19
$\begingroup$

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is logical since we are dealing with cycles).

However, I cannot find any proof that works for a general cycle of this format:enter image description here

I am trying to prove two things.

First, if a cycle does exist, and you advance the tortoise one node each unit of time but the hare two nodes each unit of time, then they will eventually meet.

Second, when they meet the tortoise will be $n$$\alpha$ away from the start of the sequence (where $\alpha$ is the loop length) and also $n$$\alpha$ away from the hare.

$\endgroup$
  • $\begingroup$ This is one of the early exercises in Knuth The Art of Computer Programming vol. 1. There may be a solution in Appendix A. $\endgroup$ – MJD Aug 30 '14 at 0:56
  • 1
    $\begingroup$ It's exercise 6 in section 3.1 (page 7) of Knuth volume 2, not volume 1. There is a solution in Appendix A, on page 539. $\endgroup$ – MJD Aug 30 '14 at 3:20
  • 1
    $\begingroup$ For showing that they eventually must meet, consider the first step at which the tortoise enters the loop. If the hare is on that node, that is a meeting and we are done. If the hare is not on that node, note that on each subsequent step the distance the hare is ahead of the tortoise increases by one, which means that since they are on a loop the distance that the hare is BEHIND the tortoise decreases by one. Hence, at some point the distance the hare is behind the tortoise becomes zero and the meet. $\endgroup$ – tzs Nov 25 '17 at 22:48
28
$\begingroup$

If the preliminary tail is length $T$ and the cycle is length $C$ (so in your picture, $T=3$, $C=6$), we can label the tail nodes (starting at the one farthest from the cycle) as $-T, -(T-1),..., -1$ and the cycle nodes $0, 1, 2, ..., C-1$ (with the cycle node numbering oriented in the direction of travel).

We may use the division algorithm to write $T=kC+r$ where $0\le r<C$.

After $T$ clicks the tortoise is at node $0$ and the hare is at node $r$ (since hare has gone $2T$ steps, of which the first $T$ were in the tail, leaving $T$ steps in the cycle, and $T\equiv r \pmod{C}$).

Assuming $r\ne 0$, after an additional $C-r$ clicks, the tortoise is at node $C-r$; and the hare is at node congruent $\pmod{C}$ to $r+2(C-r)=2C-r\equiv C-r \pmod{C}$. Hence both critters are at node $C-r$. [In the $r=0$ case, you can check that the animals meet at the node $0$.]

The distance from the start at this meeting time is thus $T+C-r=(kC+r)+C-r=(k+1)C$, a multiple of the cycle length, as desired. We can further note, this occurrence is at the first multiple of the cycle length that is greater than or equal to the tail length.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ They're on the same node, so in a sense their distance is $0$; however, at that time we can say that Tortoise has gone $(k+1)C$ steps and hare has gone twice as many steps, namely $2(k+1)C$ so the difference in their distance traveled is indeed $(k+1)C$. $\endgroup$ – paw88789 Aug 30 '14 at 3:46
  • 3
    $\begingroup$ If, as you say, they are now moving one step at a time (with the tortoise back at $-T$), then in $T$ steps, the tortoise will be at $0$ (start of cycle). Meanwhile, the hare, also going one step at a time will go from $C-r$ to $C-r+T= C-r+(kC+r)=(k+1)C\equiv 0 \pmod{C}$; and so hare arrives simultaneously at the start of the cycle. $\endgroup$ – paw88789 Aug 30 '14 at 4:09
  • 1
    $\begingroup$ @RohitSinghRathore If $r=0$, they meet after $T$ steps. They don't have to go the additional $C-r$ steps. $\endgroup$ – paw88789 May 28 '17 at 9:26
  • 1
    $\begingroup$ Such a lovely proof! Loved your numbering scheme. I have one question, is there any intuition behind why C - r steps are required for them to meet? $\endgroup$ – Vikas Tikoo Apr 27 '19 at 6:29
  • 2
    $\begingroup$ @Vikas Tikoo Thanks. And to answer your question: Because when tortoise lands on $0$, starting the cycle, hare is on node $r$ in the cycle. So hare is $r$ ahead of tortoise in the cycle. But that also means that hare is $C-r$ behind tortoise. Hare gains $1$ step for each click of time. So it takes $C-r$ clicks for the catch. $\endgroup$ – paw88789 Apr 27 '19 at 13:26
7
$\begingroup$

This can be generalized a little, to hare step sizes $>2$ and to the tortoise and hare not necessarily starting on the same node. All step sizes $>2$ work if they start on the same node. If they start on different nodes then only a step size of 2 is guaranteed to work no matter what the cycle length.

Let $T =$ the number of nodes before the start of the cycle. Let $C =$ the length of the cycle. Let $S =$ the step size of the hare (2 for the problem as given).

After $n$ iterations, the tortoise has moved $n$ nodes, and the hare $nS$. The hare and tortoise are on the same node whenever $n \geq T$ and $n-T \equiv nS-T$ mod $C$. So we are looking for solutions of $n(S-1) \equiv 0$ mod $C$ with $n \geq T$.

When $S=2$ as in the problem as given, this is simply $n\equiv0$ mod $C$. This happens exactly when $n$ is a multiple of $C$.

When $S>2$ it also happens on every multiple of $C$, but might also happens at other times if $S-1$ and $C$ are not relatively prime.

That covers starting on the same node. For starting on different nodes, let $h =$ the starting node of the hare, and $t=$ the starting node of the tortoise.

Then we need to solve $n(S-1) \equiv t-h$ mod $C$ instead of $n(S-1) \equiv 0$, subject to $t+n\geq T$.

When $S=2$, that is $n\equiv t-h$ mod $C$, which has $n = t-h+kC$ as solutions for all integers $k$. When $S>2$ it is possible that $n(S-1)\equiv t-h$ mod $C$ has no solutions.

Actually, you can even generalize some more, letting the tortoise have a step size $>1$. As long as the tortoise and hare start on the same node, and the hare has a larger step size than the tortoise, it will still work. If $S_h$ is the hare's step size and $S_t$ is the tortoise's step size, then instead of $n(S-1)\equiv 0$ mod $C$ we have to solve $n(S_h-S_t)\equiv 0$ mod $C$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Say there are $l$ elements before the loop starts and $n$ elements in the loop. And $e_l$ is the first element of the loop which is seen when we traverse the linked-list. When we will say "an element $x$ steps ahead of $e$", that will mean, we can reach that element taking $x$ steps from $e$.

Now, when Tr (tortoise) reaches $e_l$, after $l$ iterations, say, Hr (Hare) is $x$ steps ahead of $e_l$. Since Hr has taken total $2l$ steps by then ($l$ steps prior to the loop), so:

$x = l \bmod n$.

In each future iteration, Tr and Hr will progress by 1 and 2 steps respectively, and so each iteration will increase their "gap" by 1. So they will meet after $n-x$ further iterations, when their gap will become $x + (n-x) = n$.

So, till that meeting, Tr has taken total steps = (steps till $e_l$) + (further steps after $e_l$)

= $l + (n-x)$

= $l + n - l \bmod n$

= $n + (l- l \bmod n)$

= a multiple of $n$

Since Hr takes 2 steps in each iteration, so, till the meeting it must have taken double of the Tr's steps, again a multiple of $n$.

Refer here for more information.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.