Python: recursion (3)

Abstract: Computer Tower of Hanoi using recursive method

The Tower of Hanoi consists of three rods labelled as A, B,C. A number of disks (n) with different sizes are in ascending order of size on the rod A, the smallest known as No.1 at the top. Move the entire disk stack to the rod C, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. The smaller disks are always stacked on the larger disks.

The minimum number of moving steps 2ⁿ – 1. For the recursion method to resolve this question,

startpoint: 1~n, 0, 0

recursion:

endpoint: 0,0, 1~n

Moving steps for recursion:

1. Always move No.1 disk (the smallest disk) first in order of A→B→C→A→B→C… if n is even. The order would be A->C->B->A->C->B… if n is odd.

2. Move the other disks except the No.1 disk. If any rod is empty, then move the disk from the other rod to occupy it. If no rod is empty, move the smaller disk.

Note: The ERROR of 'maximum recursion depth exceeded' might occur if n is large.

Here is the script :

# -*- coding: utf-8 -*-
"""
Created on Sat Jun  6 12:56:07 2015

@author: yuan
"""

class hannoi_methods:
    def __init__(self, number):
        self.number=number
        self.steps=0
        self.a=range(1, number+1)
        self.b=[]
        self.c=[]
   
    def move_second(self, x, y):
        #first remove if x or y is empty
        if len(x)==0:
            x.insert(0, y.pop(0))#remove the first from y to x
        elif len(y)==0:
            y.insert(0, x.pop(0))#remove the first from x to y
        else:#remove the smaller one
            if(x[0]<y[0]):
                y.insert(0, x.pop(0))
            else:
                x.insert(0, y.pop(0))
        return x,y

    def recursive_even(self, pos, a, b, c):
        if len(c)==(self.number-1):#endpoint
            c.insert(0,b.pop(0) )
            self.steps += 1
            print pos, a, b, c
            return self.steps
        else:
            print pos, a, b, c
            #remove the No.1 dish
            if(pos==1):
                b.insert(0, a.pop(0))#remove 1 from a to b
                pos=2
                a,c=self.move_second(a,c)#remove the secondary element
            elif(pos==2):
                c.insert(0, b.pop(0))#remove 1 from b to c
                pos=3
                a,b=self.move_second(a,b)
            else:
                a.insert(0, c.pop(0))#remove 1 from c to a
                pos=1
                b,c=self.move_second(b,c)
            self.steps += 2
            #
            return self.recursive_even(pos, a, b, c)

    def recursive_odd(self, pos, a, b, c):
        if len(c)==(self.number-1):#endpoint
            c.insert(0,a.pop(0) )
            self.steps += 1
            print pos, a, b, c
            return self.steps
        else:
            print pos, a, b, c
            #remove the No.1 dish
            if(pos==1):
                c.insert(0, a.pop(0))#remove 1 from a to c
                pos=3
                a,b=self.move_second(a,b)#remove the secondary element
            elif(pos==2):
                a.insert(0, b.pop(0))#remove 1 from b to a
                pos=1
                b,c=self.move_second(b,c)
            else:
                b.insert(0, c.pop(0))#remove 1 from c to b
                pos=2
                a,c=self.move_second(a,c)
            self.steps += 2
            #
            return self.recursive_odd(pos, a, b, c)
           
    def hannoi(self):
        if self.number%2==0:
            steps=self.recursive_even(1, self.a, self.b, self.c)#startpoint
        else:
            steps=self.recursive_odd(1, self.a, self.b, self.c)#startpoint
        print 'Total steps:', steps
       
       
#main programming
#even
r=hannoi_methods(10)
r.hannoi()
#oddd
r=hannoi_methods(19)
r.hannoi()