# -*- coding: utf-8 -*-
 
from __future__ import print_function
from itertools import islice, cycle, chain, izip, repeat
 
 
class keeping_iterator(object):
    '''Holds the iterator and keeps the last value returned by the iterator'''
    def __init__(self,iterable):          
        self.it = iter(iterable)
        self.val = next(self.it) #get the first value
 
    def next(self):
        self.val = next(self.it)
        return self.val
 
    def __iter__(self):
        return self
 
 
def consume_iterator_until_values_match(iter1,iter2):
    '''Advance the iterators until their values match.
    Returs the number of iterations it took'''
    for n,(i1,i2) in enumerate(izip(iter1,iter2),1):
        if i1==i2:
            return n
 
 
def detect_cycle(iterable):
    '''Detect a cycle in iterable object.
    Iterable must return an independend iterator on iter(iterable)'''
 
    tortoise = keeping_iterator(iterable)
    hare = keeping_iterator(islice((iterable),None,None,2))  #two steps at a time
    #it will start from the first value and only then will be advancing 2 values at a time
 
    consume_iterator_until_values_match(tortoise,hare)
 
    hare = tortoise #put hare in the place of tortoise
    tortoise = keeping_iterator(iterable) #start tortoise from the very beginning
    mu = consume_iterator_until_values_match(chain(repeat(tortoise.val,1),tortoise),
                                             chain(repeat(hare.val,1),hare)) - 1
    #begin with the current val of hare.val and the value of tortoise which is in the first position
    # ' - 1' since the first value corresponds to mu=0
 
    hare = tortoise
    tortoise_val = tortoise.val
    lamb = consume_iterator_until_values_match(repeat(tortoise_val),hare)
 
    print('mu: {0}'.format(mu))
    print('lamb: {0}'.format(lamb))
 
 
if __name__ == '__main__':
 
    class iterable(object):
        '''Emulate the object returning iterators having cycles'''
        def __init__(self,beginning,cycling):
            '''
beginning: the beginning part with no cycles (its length corresponds to mu)
cycling: the part which will be cycling (its length corresponds to lamb)
'''
            self.beginning = beginning
            self.cycling = cycling
 
        def __iter__(self):
            return chain(iter(self.beginning),cycle(iter(self.cycling)))
 
    detect_cycle(iterable('1234','678'))

IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KCmZyb20gX19mdXR1cmVfXyBpbXBvcnQgcHJpbnRfZnVuY3Rpb24KZnJvbSBpdGVydG9vbHMgaW1wb3J0IGlzbGljZSwgY3ljbGUsIGNoYWluLCBpemlwLCByZXBlYXQKCgpjbGFzcyBrZWVwaW5nX2l0ZXJhdG9yKG9iamVjdCk6CiAgICAnJydIb2xkcyB0aGUgaXRlcmF0b3IgYW5kIGtlZXBzIHRoZSBsYXN0IHZhbHVlIHJldHVybmVkIGJ5IHRoZSBpdGVyYXRvcicnJwogICAgZGVmIF9faW5pdF9fKHNlbGYsaXRlcmFibGUpOiAgICAgICAgICAKICAgICAgICBzZWxmLml0ID0gaXRlcihpdGVyYWJsZSkKICAgICAgICBzZWxmLnZhbCA9IG5leHQoc2VsZi5pdCkgI2dldCB0aGUgZmlyc3QgdmFsdWUKCiAgICBkZWYgbmV4dChzZWxmKToKICAgICAgICBzZWxmLnZhbCA9IG5leHQoc2VsZi5pdCkKICAgICAgICByZXR1cm4gc2VsZi52YWwKCiAgICBkZWYgX19pdGVyX18oc2VsZik6CiAgICAgICAgcmV0dXJuIHNlbGYKCgpkZWYgY29uc3VtZV9pdGVyYXRvcl91bnRpbF92YWx1ZXNfbWF0Y2goaXRlcjEsaXRlcjIpOgogICAgJycnQWR2YW5jZSB0aGUgaXRlcmF0b3JzIHVudGlsIHRoZWlyIHZhbHVlcyBtYXRjaC4KICAgIFJldHVycyB0aGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgaXQgdG9vaycnJwogICAgZm9yIG4sKGkxLGkyKSBpbiBlbnVtZXJhdGUoaXppcChpdGVyMSxpdGVyMiksMSk6CiAgICAgICAgaWYgaTE9PWkyOgogICAgICAgICAgICByZXR1cm4gbgogICAgICAgIAoKZGVmIGRldGVjdF9jeWNsZShpdGVyYWJsZSk6CiAgICAnJydEZXRlY3QgYSBjeWNsZSBpbiBpdGVyYWJsZSBvYmplY3QuCiAgICBJdGVyYWJsZSBtdXN0IHJldHVybiBhbiBpbmRlcGVuZGVuZCBpdGVyYXRvciBvbiBpdGVyKGl0ZXJhYmxlKScnJwoKICAgIHRvcnRvaXNlID0ga2VlcGluZ19pdGVyYXRvcihpdGVyYWJsZSkKICAgIGhhcmUgPSBrZWVwaW5nX2l0ZXJhdG9yKGlzbGljZSgoaXRlcmFibGUpLE5vbmUsTm9uZSwyKSkgICN0d28gc3RlcHMgYXQgYSB0aW1lCiAgICAjaXQgd2lsbCBzdGFydCBmcm9tIHRoZSBmaXJzdCB2YWx1ZSBhbmQgb25seSB0aGVuIHdpbGwgYmUgYWR2YW5jaW5nIDIgdmFsdWVzIGF0IGEgdGltZQoKICAgIGNvbnN1bWVfaXRlcmF0b3JfdW50aWxfdmFsdWVzX21hdGNoKHRvcnRvaXNlLGhhcmUpCiAgICAKICAgIGhhcmUgPSB0b3J0b2lzZSAjcHV0IGhhcmUgaW4gdGhlIHBsYWNlIG9mIHRvcnRvaXNlCiAgICB0b3J0b2lzZSA9IGtlZXBpbmdfaXRlcmF0b3IoaXRlcmFibGUpICNzdGFydCB0b3J0b2lzZSBmcm9tIHRoZSB2ZXJ5IGJlZ2lubmluZwogICAgbXUgPSBjb25zdW1lX2l0ZXJhdG9yX3VudGlsX3ZhbHVlc19tYXRjaChjaGFpbihyZXBlYXQodG9ydG9pc2UudmFsLDEpLHRvcnRvaXNlKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW4ocmVwZWF0KGhhcmUudmFsLDEpLGhhcmUpKSAtIDEKICAgICNiZWdpbiB3aXRoIHRoZSBjdXJyZW50IHZhbCBvZiBoYXJlLnZhbCBhbmQgdGhlIHZhbHVlIG9mIHRvcnRvaXNlIHdoaWNoIGlzIGluIHRoZSBmaXJzdCBwb3NpdGlvbgogICAgIyAnIC0gMScgc2luY2UgdGhlIGZpcnN0IHZhbHVlIGNvcnJlc3BvbmRzIHRvIG11PTAKCiAgICBoYXJlID0gdG9ydG9pc2UKICAgIHRvcnRvaXNlX3ZhbCA9IHRvcnRvaXNlLnZhbAogICAgbGFtYiA9IGNvbnN1bWVfaXRlcmF0b3JfdW50aWxfdmFsdWVzX21hdGNoKHJlcGVhdCh0b3J0b2lzZV92YWwpLGhhcmUpCgogICAgcHJpbnQoJ211OiB7MH0nLmZvcm1hdChtdSkpCiAgICBwcmludCgnbGFtYjogezB9Jy5mb3JtYXQobGFtYikpCiAgICAgCgppZiBfX25hbWVfXyA9PSAnX19tYWluX18nOgogICAgCiAgICBjbGFzcyBpdGVyYWJsZShvYmplY3QpOgogICAgICAgICcnJ0VtdWxhdGUgdGhlIG9iamVjdCByZXR1cm5pbmcgaXRlcmF0b3JzIGhhdmluZyBjeWNsZXMnJycKICAgICAgICBkZWYgX19pbml0X18oc2VsZixiZWdpbm5pbmcsY3ljbGluZyk6CiAgICAgICAgICAgICcnJwpiZWdpbm5pbmc6IHRoZSBiZWdpbm5pbmcgcGFydCB3aXRoIG5vIGN5Y2xlcyAoaXRzIGxlbmd0aCBjb3JyZXNwb25kcyB0byBtdSkKY3ljbGluZzogdGhlIHBhcnQgd2hpY2ggd2lsbCBiZSBjeWNsaW5nIChpdHMgbGVuZ3RoIGNvcnJlc3BvbmRzIHRvIGxhbWIpCicnJwogICAgICAgICAgICBzZWxmLmJlZ2lubmluZyA9IGJlZ2lubmluZwogICAgICAgICAgICBzZWxmLmN5Y2xpbmcgPSBjeWNsaW5nCgogICAgICAgIGRlZiBfX2l0ZXJfXyhzZWxmKToKICAgICAgICAgICAgcmV0dXJuIGNoYWluKGl0ZXIoc2VsZi5iZWdpbm5pbmcpLGN5Y2xlKGl0ZXIoc2VsZi5jeWNsaW5nKSkpCgogICAgZGV0ZWN0X2N5Y2xlKGl0ZXJhYmxlKCcxMjM0JywnNjc4Jykp