1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2014
Posts
1
Rep Power
0

#### Hanoi Towers

Code:
```def hanoi_move ( start , via , target ,n ,k ):
""" finds the k-th move in an Hanoi Towers instance
with n discs """
if n <=0:
return "zero or fewer disks"
elif k <=0 or k >=2** n or type(k )!= int :
return "number of moves is illegal"
elif k ==2**( n -1):
return str . format ("disk {} from {} to {}",n , start , target )
elif k <2**( n -1):
return hanoi_move ( start , target , via ,n -1 , k)
else:
return hanoi_move ( via , start , target ,n -1 ,k -2**( n -1))```
may you explain the last row, why it is not (via, target, start ,n -1 ,k -2**( n -1)? why k=2^(n-1) when disk n is moved from start to target?
2. I think I do understand the quick code to determine which move is the kth move. Clear explanation---another story. I wrote a lot of confusion which I deleted before posting. Then wrote a program. See if you can figure it out from this code which plays ToH. In this output the towers are in constant position, original source, original extra, and original sink.
Code:
```'''
\$ python p.py
0:  (dcba)  (    )  (    )
1:  (dcb )  (a   )  (    )
2:  (dc  )  (a   )  (b   )
3:  (dc  )  (    )  (ba  )
4:  (d   )  (c   )  (ba  )
5:  (da  )  (c   )  (b   )
6:  (da  )  (cb  )  (    )
7:  (d   )  (cba )  (    )
8:  (    )  (cba )  (d   )
9:  (    )  (cb  )  (da  )
10:  (b   )  (c   )  (da  )
11:  (ba  )  (c   )  (d   )
12:  (ba  )  (    )  (dc  )
13:  (b   )  (a   )  (dc  )
14:  (    )  (a   )  (dcb )
15:  (    )  (    )  (dcba)
'''

class Hanoi:

def __init__(self, n, verbosity=0):
self.n = n
self.verbosity = verbosity
self.fmt = '{:4d}:'+('  ({:%ds})'%self.n)*3
self.reset()

def verbose(self):
if self.verbosity:
print(self)

def reset(self):
self.towers = [list(reversed('abcdefghijklmnop'[:self.n])), [], []]
self.count = 0

def __str__(self):
return self.fmt.format(self.count, *(''.join(t) for t in self.towers))

def __call__(self):
self.verbose()
self.hanoi(0, 1, 2, self.n)

def hanoi(self,a,b,c,n):
if n:
self.hanoi(a,c,b,n-1) # move all but 1 onto the extra pile b
t = self.towers
self.count += 1
t[c].append(t[a].pop()) # move the 1 onto the destination
self.verbose()
self.hanoi(b,a,c,n-1) # move those of b to destination

h = Hanoi(4, True)
h()```
notes: I think there's a way to have string formatting use a format method. I didn't look it up. I think there are ways to incorporate field widths and various braces into string formats. I didn't study that either.
Last edited by b49P23TIvg; February 17th, 2014 at 10:35 AM.