"""
 hanoi.py

  Towers of Hanoi in python.

  Based on perl program by DigitalKitty (Katie)
  on perlmonks.org, node 400359 on 10/20/2004

 Jim Mahoney | cs.marlboro.college | Nov 2018 | MIT License

          A             B             C      

          |             |             |
         ---   1        |             |
        -----  2        |             |
       ------- 3        |             |
    ============================================

 For this stack with 3 disks, the moves would be

   disk 1 moves A to B
   disk 2 moves A to C
   disk 1 moves B to C
   disk 3 moves A to B
   disk 1 moves C to A
   disk 2 moves C to B
   disk 1 moves A to B
"""

def move_disks(n, start='A', end='B', extra='C'):
  """Return string of moves moving n disks start one column to another.
     >>> move_disks(1)
     ' disk 1 moves A to B\\n'
     >>> move_disks(2)
     ' disk 1 moves A to C\\n disk 2 moves A to B\\n disk 1 moves C to B\\n'
  """
  result_string = " disk {} moves {} to {}\n"
  if n == 1:
    return result_string.format(1, start, end)      # At top? Just move it.
  else:
    # Here's the heart of it.  The idea is
    #  1) move the top n-1 disks to the extra column, then
    #  2) move the biggest disk n from 'start' to 'end', then
    #  3) move the top n-1 disks again, this time from 'extra' to 'end'.
    return move_disks(n-1, start, extra, end) + \
           result_string.format(n, start, end) + \
           move_disks(n-1, extra, end, start)             

def hanoi():
  n_disks = int(input("Number of disks? "))
  print("The moves are: ")
  print(move_disks(n_disks),)

if __name__=="__main__":
  from doctest import testmod
  testmod()
  hanoi()