Possible approach to visualize the Tower of Hanoi problem-CodePudding

I recently started learning more about recursion in Python and quickly got myself into the Tower of Hanoi problem.

I already have a recursive solution in Python, which prints the moves I should play to solve the problem, but I would like to visualize it and see the pieces moving.

What would be a possible approach to it?

CodePudding user response：

Perhaps as command line strings:

{"peg1": [0, 1, 2],
 "peg2": [0, 0, 3],
 "peg3": [0, 0, 0]}

as:

   |          |          |   
  -|-         |          |   
 --|--     ---|---       |   
=============================

It would be all about translating the lists into these peg pictures.

This you can reached by:

def peg_to_strings(peg_list, dct={0: "   |   ",
                                  1: "  -|-  ",
                                  2: " --|-- ",
                                  3: "---|---"}):
    return [dct[x] for x in peg_list]   ["======="]

def interleave(lists, lst):
    # interleave([1, 2, 3], 'a') => [1, 'a', 2, 'a', 3]
    res = [(l, lst) for l in lists]
    return [y for x in res for y in x][:-1]

def transpose(lists):
    # transpose([[1, 2, 3], ['a', 'b', 'c']]) => [[1, 'a'], [2, 'b'], [3, 'c']]
    return [[l[i] for l in lists] for i in range(len(lists[0]))]

def pegs_to_strings(pegs_dct, inbetween=["    ", "    ", "    ", "===="]):
    lists = [peg_to_strings(pegs_dct[f"peg{x}"]) for x in [1,2,3]]
    return [''.join(strings) for strings in transpose(interleave(lists, inbetween))]

pegs_dct = {"peg1": [0, 1, 2],
            "peg2": [0, 0, 3],
            "peg3": [0, 0, 0]}

print('\n'.join(pegs_to_strings(pegs_dct)))

#    |          |          |   
#   -|-         |          |   
#  --|--     ---|---       |   
# =============================

So for the visualization steps, you have to bring the pegs into this dictionary form.

CodePudding user response：

If you model your pegs as a list of lists with the larger discs at the lower indices, it should be relatively simple to implement a printing function and a movement function (that also prints). You can then feed your movements to that function.

def printHanoi(pegs):
    height = sum(map(len,pegs))
    for r in reversed(range(height)):
        for peg in pegs:
            disc = "-" * (0 if r>=len(peg) else peg[r])
            print(f"{disc:>{height}}|{disc:{height}}", end=" ")
        print()
    invalid = any(p[::-1]!=sorted(p) for p in pegs)
    print("="*(height*6 5),"INVALID"*invalid)        
    print()


def moveHanoi(pegs,fromPeg,toPeg):
    pegs[toPeg].append(pegs[fromPeg].pop(-1))
    printHanoi(pegs)

Output:

pegs = [[3,2,1],[],[]]
printHanoi(pegs)
moveHanoi(pegs,0,2)
moveHanoi(pegs,0,1)
moveHanoi(pegs,2,1)
moveHanoi(pegs,0,2)

  -|-      |       |   
 --|--     |       |   
---|---    |       |   
=======================

   |       |       |   
 --|--     |       |   
---|---    |      -|-  
=======================

   |       |       |   
   |       |       |   
---|---  --|--    -|-  
=======================

   |       |       |   
   |      -|-      |   
---|---  --|--     |   
=======================

   |       |       |   
   |      -|-      |   
   |     --|--  ---|---
=======================

This will work for any tower height and, if your algorithm makes illegal moves, it will illustrate them as well:

pegs = [[5,4,3,2,1],[],[]]
printHanoi(pegs)
moveHanoi(pegs,0,2)
moveHanoi(pegs,0,1)
moveHanoi(pegs,0,2)
    
    -|-          |           |      
   --|--         |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----      |           |      
===================================

     |           |           |      
   --|--         |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----      |          -|-     
===================================

     |           |           |      
     |           |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----    --|--        -|-     
===================================

     |           |           |      
     |           |           |      
     |           |           |      
 ----|----       |        ---|---   
-----|-----    --|--        -|-     
=================================== INVALID

If you build your Hanoi solver as a generator, you will be able to use it in a for-loop that simply calls the moveHanoi() function:

def solveHanoi(count,fromPeg=0,toPeg=2,tempPeg=1):
    if not count: return
    yield from solveHanoi(count-1,fromPeg,tempPeg,toPeg)
    yield fromPeg,toPeg
    yield from solveHanoi(count-1,tempPeg,toPeg,fromPeg)
        
pegs = [[3,2,1],[],[]]
printHanoi(pegs)
for f,t in solveHanoi(3):
    moveHanoi(pegs,f,t)