Question

Como Implementar iterativamente a solução da torre de Hanoi usando uma classe para pilhas?

Answer 1

  """
Created on Thu Apr 11 01:38:22 2019

@author: Douglas Silveira
"""

class TorreDeHanoi:
     def __init__(self, numDiscos, origem, intermed, destino):
         self.numDiscos = numDiscos
         self.torres = {
                        origem: Stack(),
                        intermed: Stack(),
                        destino: Stack()
                       }
         for i in range(n, 0, -1):
             self.torres[origem].push(i);

     def moverDisco(self, origem, destino):
         self.torres[destino].push(self.torres[origem].pop())
         print("{} para {}".format(origem, destino))

     def moverTorre(self, n, origem, intermed, destino):
         if n >= 1:
            self.moverTorre(n-1, origem, destino, intermed)
            self.moverDisco(origem, destino)
            self.moverTorre(n-1, intermed, origem, destino)

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return len(self) == 0

     def push(self, item):
         self.items.append(item)

     def pop(self):
         if not self.isEmpty():
             return self.items.pop()
         else:
             raise IndexError("pop from empty Stack")

     def peek(self):
         return self.items[len(self.items)-1]

     def __len__(self):
         return len(self.items)

n = int(input("número de discos: "))
torre = TorreDeHanoi(n, "Origem", "Intermediária", "Destino")
torre.moverTorre(n, "Origem", "Intermediária", "Destino")

Comments

Muito interessante a solução com pilhas, Douglas, porque intuitivamente se assemelha ao problema real da torre de Hanoi. Com as pilhas, você simplifica a sintaxe por puxar os elementos de cima sempre, sem precisar de declarar o elemento específico que se quer acessar (o que aconteceria se estivesse usando listas normais, por exemplo). Eu tentei adicionar uma contagem sempre que a função moverDisco é chamada (usando os Decorators do Python), mas não consegui. Se o professor ou algum outro colega souber uma forma simples de inserir esse contador, seria uma adição interessante.

Apenas uma adição mínima, para seguir a "filosofia" do Python de usar funções sempre que possível para evitar novas execuções do código, incluirei aqui a parte da solução como função:

def solucao_hanoi():
    n = int(input("número de discos: "))
    torre = TorreDeHanoi(n, "Origem", "Intermediária", "Destino")
    torre.moverTorre(n, "Origem", "Intermediária", "Destino")
    
solucao_hanoi()