def Hanoi(quantidade, origem="A", destino="B", auxiliar="C"):
    if quantidade == 1:
        print(f"{origem} → {destino}")
        return
    Hanoi(quantidade-1, origem, auxiliar, destino)
    print(f"{origem} → {destino}")
    Hanoi(quantidade-1, auxiliar, destino, origem)

def Hanoi_passos(quantidade, origem="A", destino="B", auxiliar="C", passo=1):
    if quantidade == 1:
        print(f"{passo}. {origem} → {destino}")
        return passo+1
    passo = Hanoi_passos(quantidade-1, origem, auxiliar, destino, passo)
    print(f"{passo}. {origem} → {destino}")
    passo = Hanoi_passos(quantidade-1, auxiliar, destino, origem, passo+1)
    return passo

def Hanoi_explicado(quantidade, origem="A", destino="B", auxiliar="C", prof=0):
    print(f"{'-'*prof}{'' if prof==0 else ' '}{'Q' if prof == 0 else 'então, primeiro q'}uero mover {quantidade} disco{'s' if quantidade > 1 else ''} de {origem} para {destino}")
    if quantidade == 1:
        print(f"{'-'*prof} Fácil! mova o disco no topo de {origem} para {destino} e fim.")
        return
    Hanoi_explicado(quantidade-1, origem, auxiliar, destino, prof+1)
    print(f"{'-'*prof}{'' if prof==0 else ' '}Agora mova o disco no topo de {origem} para {destino}")
    Hanoi_explicado(quantidade-1, auxiliar, destino, origem, prof+1)
    print(f"{'-'*prof}{'' if prof==0 else ' '}Movi {quantidade} discos de {origem} para {destino}!")

def imprime_Hanoi(pinos):
    L = max(len(str(x)) for x in pinos.keys())
    print()
    for pino, discos in pinos.items():
        if discos:
            x = f"{' '.join([f'{a}cm' for a in discos])}"
        else:
            x = '-'
        print(f"{pino:>{L}}: {x}")
    
def jogar_Hanoi(discos):
    pinos = {'Origem':list(range(discos,0,-1)),
             'Destino':[],
             "Auxiliar":[]}
    while True:
        imprime_Hanoi(pinos)
        if pinos["Origem"] == pinos["Auxiliar"] == []:
            print("Ganhou!")
            return
        if len(pinos["Origem"]) == 1 and len(pinos["Destino"]) == 0:
            print("★!")
        while True:
            de = input("\nMover de: ")
            if de.lower().startswith('o'):
                de = 'Origem'
            if de.lower().startswith('a'):
                de = 'Auxiliar'
            if de.lower().startswith('d'):
                de = 'Destino'
            para = input("Mover para: ")
            if para.lower().startswith('o'):
                para = 'Origem'
            if para.lower().startswith('a'):
                para = 'Auxiliar'
            if para.lower().startswith('d'):
                para = 'Destino'
            if de not in pinos.keys() or para not in pinos.keys() or len(pinos[de]) == 0 or (len(pinos[para]) > 0 and pinos[para][-1] < pinos[de][-1]):
                print("Movimento ilegal!")
            else:
                break
        pinos[para].append(pinos[de].pop())