Solution to Daily Programmer 2015-05-18

daily_programmer_20150518.py

#https://www.reddit.com/r/dailyprogrammer/comments/36cyxf/20150518_challenge_215_easy_sad_cycles


def next_digit(n, b):
    return sum([int(d)**b for d in str(n)])

def recover_cycle(nodes, end):
    tmp = []
    while nodes:
        node = nodes.pop()
        tmp.append(node)
        if node == end:
            break
    return tmp[::-1]

    


def find_sad_cycle(val, base, max_depth = 1000):
    nodes = set([val])
    path = [val]
    i = 0
    while i < max_depth:
        i += 1
        val = next_digit(val, base)
        if val in nodes:
            #then we have a cycle
            print 'Cycle Found', recover_cycle(path, val)
            break
        else:
            nodes.add(val)
            path.append(val)


def floyds_cycle_finding(val, base):
    #implementation of Floyds cycle detecion algorithm adapted to sad-cycle problem
    f = lambda x : next_digit(x, base)

    tortoise = f(val)
    hare = f(f(val))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    #find the starting point of cycle mue
    mu = 0
    tortoise = val
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    #find the length of the shortest cycle
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1

    print mu,lam

    tmp = val
    for _ in range(mu):
        tmp = f(tmp)

    path = [tmp]
    for _ in range(lam):
        tmp = f(tmp)
        path.append(tmp)
    print path

if __name__ == "__main__":
    find_sad_cycle(12, 2)
    find_sad_cycle(117649, 5)
    find_sad_cycle(2, 6)
    find_sad_cycle(7, 7)
    find_sad_cycle(14, 3)


    floyds_cycle_finding(12, 2)
    floyds_cycle_finding(117649, 5)
    floyds_cycle_finding(2, 6)
    floyds_cycle_finding(7, 7)