Thread: Hanoi Towers

    #1
  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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,854
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo