# hanoiIter.py
'''
  https://cs.stackexchange.com/questions/96624/how-to-solve-tower-of-hanoi-iteratively
  https://en.wikipedia.org/wiki/Tower_of_Hanoi

'''

def moves(n):
  # repeat three steps until all the disks are moved
  totMoves = int(pow(2, n) - 1)
  for i in range(1, totMoves+1):
    if (i % 3 == 1):
      moveDisk(srcNm, destNm)
    elif (i % 3 == 2):
      moveDisk(srcNm, auxNm)
    elif (i % 3 == 0):
      moveDisk(auxNm, destNm)


def moveDisk(p1Nm, p2Nm):
  '''
    When one of these two poles is empty we must move 
    the disk from the non-empty pole to the empty one.

    When the top disk of one pole is smaller than the disk
    on top of the other pole, then we move the smaller of 
    two disks to the pole with the bigger disk.
  '''
  if poles[p1Nm] == []:  # p1 is empty
    doMove(p2Nm, p1Nm)
  elif poles[p2Nm] == []:
    doMove(p1Nm, p2Nm)
  else:
    # look at both top disks for comparison
    p1Disk = poles[p1Nm][-1]
    p2Disk = poles[p2Nm][-1]
    if (p1Disk > p2Disk): # p2 disk is smaller
      doMove(p2Nm, p1Nm)
    else:                 # p1 disk is smaller
      doMove(p1Nm, p2Nm)


def doMove(fromNm, toNm):
  disk = poles[fromNm].pop()
  poles[toNm].append(disk) 
  print(f"Disk {disk}: {fromNm} --> {toNm}  :", strPoles())


def strPoles():
  return f"[ {l2s(poles[srcNm]):{sz}s} [ {l2s(poles[auxNm]):{sz}s} [ {l2s(poles[destNm]):{sz}s}"


def l2s(pole):
  return ' '.join([str(disk) for disk in pole])


# ----------------------

n = int(input("n? "))
sz = n*2

# a dictionary of poles to hold the disks
srcNm, auxNm, destNm,  = 'A', 'B', 'C'    # pole names
poles = {srcNm:[], auxNm:[], destNm:[]}

if n % 2 == 0:
  print("Moving disks from", srcNm, "to", auxNm)
else:
  print("Moving disks from", srcNm, "to", destNm) 

# put disks on source pole
for i in range(n, 0, -1):
  poles[srcNm].append(i)

print(' '*18,  srcNm, ' '*sz, auxNm, ' '*sz, destNm);
print(' '*18, strPoles())

moves(n)