class Stack(object):

    """

    A class to hold arguements and state data.

    """

    def __init__(self,**kwargs):

        self.__dict__.update(kwargs)

    def __repr__(self):

        extra = "|i:%s"%self.i if hasattr(self,'i') else ''

        return "n:%s|stage:%s%s"%(self.n,self.stage,extra)

def memory(function):

    """

    A decorator to help a no-side-effect function avoid

    repeative calculation.

    """

    cache = {}

    def memofunc(*nkw,**kw):

        key=str(nkw)+str(kw)

        if key not in cache:

            cache[key] = function(*nkw,**kw)

        return cache[key]

    return memofunc

def is_equal(rg,*funclist):

    """

    to test whether or not a list of one-arguement functions

    have the same output if given same arguement.

    """

    for n in rg:

        rst=[]

        for func in funclist:

            rst.append(func(n))

            assert len(set(rst))==1

@memory

def hanoi_recur(n):

    """

    n -> (i,v)

    a recursive function to get the smallest number i

    and correspondent value.

    """

    if n==1:

        return 1,1

    psb=[]

    for i in range(n-1,0,-1):

        _, min_v = hanoi_recur(n-i)

        psb_v = 2*min_v+2**i-1

        psb.append((i,psb_v))

    return min(psb,key=lambda x:x[1])

@memory

def hanoi_loop(n):

    """

    The loop version of hanoi_recur.

    """

    if n==1:

        return 1,1

    stack = [Stack(n=n,stage=0,)]

    cache={1:1}

    while stack:

        crt=stack.pop()

        if crt.n in cache:

            psb_v = 2*cache[crt.n]+2**crt.i-1

            crt.prt.psb.append((crt.i,psb_v))

            continue

        if crt.stage==0:

            crt.stage, crt.pgs, crt.psb= 1, 0, []

            stack.append(crt)

            continue

        if crt.stage==1:

            if crt.pgs != crt.n - 1:

                crt.pgs += 1

                stack.append(crt)

                chd = Stack(n=crt.pgs, stage=0, i=crt.n-crt.pgs, prt=crt)

                stack.append(chd)

            else:

                crt.stage=2

                stack.append(crt)

            continue

        if crt.stage==2 and hasattr(crt,'prt'):

            #hasattr - the last stack doesn't have attribute 'prt',

            #so it has to be excluded here.

            _, min_v = min(crt.psb,key=lambda x:x[1])

            psb_v = 2*min_v + 2**crt.i - 1

            crt.prt.psb.append((crt.i,psb_v))

            cache[crt.n] = min_v

            continue

    return min(crt.psb,key=lambda x:x[1])

if __name__=='__main__':

    is_equal(range(1,300),hanoi_loop,hanoi_recur)

    print('passed test!')