Recursive Hanoi Tower with Play Counter

Asked

Viewed 123 times

1

I wrote this recursive code from Anoi’s tower and was trying to implement a section that told me the minimum number of moves needed and what move we were playing ( add a move whenever it changed).

For example if there were 3 disks:

Primeira jogada: Tower 1 --> Tower 2
etc...
Número minimo de jogadas: 7

How could I implement this? Recursively? With iteration and cycles? I tried recursively but lost myself in my reasoning and could not solve the problem without reformulating everything.

def hanoi():

    def mova(n, origem, destino, aux):
        
        def mova_disco(de, para):
            print("Tower", de, "-->", "Tower", para, "\n\n")


        if n == 1:
            mova_disco(origem, destino)

        else:
            mova(n - 1, origem, aux, destino)
            mova_disco(origem, destino)
            mova(n - 1, aux, destino, origem)

    n = eval(input("Quantos discos deseja considerar? \n -->"))
    print("Solução do puzzle: \n")
    mova(n, "1", "3", "2")

#Running the code

hanoi()
python recursion
  • 1

    In Portuguese, por favor, já que estamos no [pt.so]

  • And by translating, you could explain why you used the eval on user input?

  • @Woss already translated. I used evalei as I would use "int(input)", just for habit and because they use in the book I’m reading. But they work the same way I think.

  • eval is not the same thing as int. The difference is that int converts to number and gives error if you have anything that is not a number, while eval accepts any valid command, and may even be dangerous, see here an example - if the book says to use eval and does not alert to these problems, I would already look with suspicion...

  • Okay, I get it. Thank you. I will take this into account next time before using Eval :) ?

1 answer

0


You can make the roles receive the current move number, and return that updated number.

And as the total of moves to N disks is always 2N - 1, you can print this value directly:

def hanoi():
    def mova(n, origem, destino, aux, jogada):
        def mova_disco(de, para, jogada):
            print(f"Jogada {jogada:>3}: Tower {de} --> Tower {para}")
            return jogada + 1 # atualiza para a próxima jogada

        if n == 1:
            jogada = mova_disco(origem, destino, jogada)
        else:
            jogada = mova(n - 1, origem, aux, destino, jogada)
            jogada = mova_disco(origem, destino, jogada)
            jogada = mova(n - 1, aux, destino, origem, jogada)

        return jogada

    n = int(input("Quantos discos deseja considerar? \n -->"))
    print(f"Solução do puzzle ({2 ** n - 1} jogadas): \n")
    mova(n, "1", "3", "2", 1)

hanoi()

That is, when I move the disk, I print the current move and return the next move. And with each movement I take that return and step into the next movement.

Note also that I used f-string (available from Python 3.6) to print messages. In the case of the move, I also used the formatting options (in the case, >3 to align the numbers to the right, occupying 3 positions).

And I switched eval for int, since int converts what is typed to number (and gives error if it is not a number), while eval performs anything typed, including potentially dangerous commands (see here for more details).

Another solution (worse, read here and here for more details) is to have a global variable as a play counter:

jogada = 1 # variável global
def hanoi():
    def mova(n, origem, destino, aux):
        def mova_disco(de, para):
            global jogada # referenciar a variável global
            print(f"Jogada {jogada:>3}: Tower {de} --> Tower {para}")
            jogada += 1 # atualizar o contador

        if n == 1:
            mova_disco(origem, destino)
        else:
            mova(n - 1, origem, aux, destino)
            mova_disco(origem, destino)
            mova(n - 1, aux, destino, origem)

    n = int(input("Quantos discos deseja considerar? \n -->"))
    print(f"Solução do puzzle ({2 ** n - 1} jogadas): \n")
    mova(n, "1", "3", "2")

hanoi()

Browser other questions tagged python recursion

You are not signed in. Login or sign up in order to post.