[PYTHON] Rabbit and turtle algorithm

In the spring of 2014, in the afternoon Q3 of the Applied Information Technology Engineer Examination, a problem was raised regarding the algorithm of the Floyd cycle detection method.

The question text is too long, so please check the question at Applied Information Technology Engineer Examination.com. In the problem, the procedure of following the circulation is likened to the steps of a rabbit and a turtle.

I implemented it in Python, so make a note here. I would like to add a commentary if I have time to spare.

Implemented by Python

I used the standard unittest as the Python testing framework. The problem induces to return a ** tuple (Pair) ** of (s, t), but I changed it a little here because I wanted to calculate the length of the recurring node with one function.

import unittest


def cycle_finding(n):
    m, p = 1, 1  # m..The remainder of the turtle calculation p..Rabbit calculation remainder
    s, t = 0, 0  # s..Position of the first decimal place of the recurring node t..Position of the last decimal digit of the recurring node

    #Until the remainders match
    while True:
        m = (m * 10) % n                #The turtle takes one step
        p = (((p * 10) % n) * 10) % n   #Rabbit takes two steps
        if m == p:
            break

    if p != 0:
        #Detection of the beginning of recurring nodes
        p = 1
        s = 1
        while m != p:
            s += 1
            m = (m * 10) % n
            p = (p * 10) % n
        #Detection of the end of recurring nodes
        p = (p * 10) % n
        t = s
        while m != p:
            t += 1
            p = (p * 10) % n

    if s == 0 and t == 0:
        return 0
    else:
        return t - s + 1


class TestCycleFinding(unittest.TestCase):
    def test_1st_decimal_place(self):
        # n = 3     1 / 3 = 0.33333... -> 0.(3)
        self.assertEqual(cycle_finding(3), 1)

    def test_2nd_decimal_place(self):
        # n = 6     1 / 6 = 0.16666... -> 0.1(6)
        self.assertEqual(cycle_finding(6), 1)

    def test_max_digits(self):
        # n = 7     1 / 7 = 0.14285714285714... -> 0.(142857)
        self.assertEqual(cycle_finding(7), 6)

    def test_two_digit_number(self):
        # n = 56    1 / 56 = 0.01785714285714285... -> 0.017(857142)
        self.assertEqual(cycle_finding(56), 6)


if __name__ == '__main__':
    unittest.main()

Continuation of the answer

Based on the given n, when expressed in O notation, the size of the storage area required by the program of the function junkan is o, and the amount of calculation is ka.

In the Python code I wrote above, I changed the function name to cycle_finding instead of junkan. I was surprised because there was no commentary on the site, but as my answer,

** The size of the storage area deals with only four variables, m, p, s, and t, so Ο (1) **

Time complexity

In this way, in all n that are recurring decimals, the rabbit always catches up with the turtle that is lapped at some rounds of the circulating part, and the remainders of both are the same.

...

When the remainders of the two match, the turtle continues, the rabbit returns to the beginning, and this time both take one step at a time, as shown in Figure 4. The quotient of the next division where the remainders of both match first (<9> and << 9 >>) is the beginning of the recurring clause.

...

After detecting the beginning of the recurring node, as shown in Fig. 5, only the rabbit advances the end of the recurring node step by step until the turtle and the remainder match (<9> and << 15 >>) again. To detect.

** We know that the above 3 loops are Ο (n) at most. ** **

I am not responsible for the explanation. I will buy a collection of past problems next time.

at the end

At first, I wrote it in C ++, but I thought it would be better to write it in Python in the future, so I rewrote it in Python.