title: Tortoise and Hare algorithm returning empty result for one case and incorrect for repeated characters
body: <p>I was going through <a href="http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare" rel="nofollow">Wikipedia implementation of Cycle detection using Tortoise-and-Hare algorithm</a>. Using Ruby language, this is what I implemented:</p>
  
  <pre>def tortoise_and_hare(sequence)
    tortoise = 1
    hare = 2
    while sequence[tortoise] != sequence[hare]
      tortoise += 1
      hare += 2
    end
  
    # Find start index of first repetition
    idx = 0
    tortoise = 0
    while sequence[tortoise] != sequence[hare]
      tortoise += 1
      hare += 1
      idx += 1
    end
  
    # Find length of cycle starting from index idx
    length = 1
    hare = tortoise + 1
    while sequence[tortoise] != sequence[hare]
      hare += 1
      length += 1
    end
  
    [idx, length]
  end
  
  sequence = [2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1]
  idx, length = tortoise_and_hare(sequence)
  p sequence[idx, length]
  </pre>
  
  <p>This is working correctly and returns <code>[6, 3, 1]</code>. Now,</p>
  
  <ol>
  <li>If I trim the sequence to <code>[2, 0, 6, 3, 1, 6, 3, 1]</code>, it returns
  empty set.</li>
  <li>I can see the problem is in second loop. If cycle has
  repeating character, algorithm returns incorrect answer. Example,
  <code>[2, 0, 6, 3, 1, 6, 6, 3, 1, 6, 6, 3, 1, 6]</code> returns <code>[6, 3, 1]</code>,
  but should be <code>[6, 3, 1, 6]</code>. I can see the problem is in third
  loop.</li>
  </ol>
  
  <p>So I guess my questions are:</p>
  
  <ol>
  <li>Is the algorithm posted on Wikipedia standard?</li>
  <li>Is my second case incorrect? I know cycle detection means infinitesimally long sequence which my exam is not, but it still has a cycle.</li>
  <li>If the case is correct, what can we do to improve the algorithm and solve the 2 issues I pointed out above?</li>
  </ol>
  
  <p>I tried modifying second loop for first problem (trimming the sequence small enough for the algorithm to fail) and it worked:</p>
  
  <pre>  # Find start index of first repetition
    idx = 0
    tortoise = 0
    while sequence[tortoise] != sequence[hare]
      tortoise += 1
      hare += 1
      hare = tortoise if hare > sequence.length - 1
      idx += 1
    end</pre>
  
  <ol>
  <li>Does it look wrong or may fail in some case?</li>
  <li>What can we do for second problem (repeating characters)?</li>
  </ol>
  
  <p>Although I cam up with another elegant Regex based solution, I still would like to learn more about above algorithm.</p>
  
  <p>Regex solution for curious: <code>/(?&lt;cycle&gt;(\d+\s)+(\d+))\s\k&lt;cycle&gt;/</code></p>
  
  <p>Edit: I understood why it is impossible for it to detect repeated characters. But is there any other algorithm that may help in this situation?</p>