Array Problem

array.py

import random

def solve(a):
    n = len(a)
    # get inside the loop by moving n steps (better approach is part 1 of Floyds's below)
    x = 0
    for i in range(n):
        x = a[x]
    # measure the period
    period = 1
    mark = x
    x = a[x]
    while x != mark:
        x = a[x]
        period += 1
    # find beggining of the cycle with pointers x and y
    # x: starts n steps ahead
    x = 0
    for i in range(period):
        x = a[x]
    # advance both x and y until the collision occurs (precisely at the beginning of the cycle)
    y = 0
    while x != y:
        x = a[x]
        y = a[y]
    return x

# Floyd's cycle-finding algorithm
def solve2(a):
    x = a[0]
    y = a[x]
    while x != y:
        x = a[x]
        y = a[a[y]]
    x = 0
    while x != y:
        x = a[x]
        y = a[y]
    return x


def testcase(a, expected):
    actual = solve(a)
    if actual != expected:
        print("ERROR %s actual %d expected %d" % (a, actual, expected))

def randomtest():
    n = 10
    a = [x for x in range(1, n - 1)]
    dup = random.randint(1, n - 2)
    a.append(dup)
    random.shuffle(a)
    testcase(a, dup)

testcase([3, 4, 6, 2, 3, 5, 1], 3)

for i in range(100):
    randomtest()