CODEWITHSUNDEEP
rubyrecursiontowers-of-hanoi
Vendetta
Vendetta

Reputation: 63

Towers of Hanoi: Recursive Explanation in Ruby

NOTE: I understand the recursive solution; but I don't see how the code is achieving it, as I can't follow the step-by-step of the code's executing.

I'm having a difficult time understanding the recursive loop for the Towers of Hanoi. I've commented and tried various tactics to see how the procedure is operating, but I can't seem to grasp how the loops are operating and how the rings are being directed.

  def move(rings, from, destination, other)
    if rings == 1
      ring = from.pop
      p "Move ring #{ring} from #{from} to #{destination}"
      destination.push ring
    else
      move(rings-1, from, other, destination)
      move(1, from, destination, other)
      move(rings-1, other, destination, from)
    end
  end

Here's the output:

"Move ring 1 from a to c"
"Move ring 2 from a to b"
"Move ring 1 from c to b"
"Move ring 3 from a to c"
"Move ring 1 from b to a"
"Move ring 2 from b to c"
"Move ring 1 from a to c"

I've looked at various explanations, however, I don't see one explaining how the loops are being executed. For instance, I can't figure out why in the cases where the rings are even, the first step places ring 1 from a to b, while for all odd number of rings, it's from a to c, as shown above.

I understand the logic behind the solution, that in order to move n number of rings to destination while using an auxiliary peg requires that you first move n-1 number of rings to the auxiliary peg followed by moving the nth ring to the destination and repeating the first procedure, again. But, I'm unsure how the directions for placement are changing, e.g. I don't see how a block is going from c to b when the call to the move method, above, doesn't seem to mention c to b.

Thank you, in advance, for your time and help.

Also, if you have any suggestions for helping track the process of code executions in Ruby, please let me know. I'd love to hear some of your insights to how you'd troubleshoot instances where you're unsure how things are being executed.

Eager to hear your answers :)

Upvotes: 2

Views: 2679

Answers (1)

Sylwester
Sylwester

Reputation: 48765

The tower of Hanoi is an excellent example of a Divide and Conquer algorithm. You have an algorithm that takes for granted it can move everything from source to destination by moving all elements except the last to spare, then move the last one from source to destination, so move all from spare to destination.

Every call to move that isn't the base case gets divided in 2 more calls exponentially until it hits the base case. The trace of you 3-disk game, only considering the first part (before moving the middle element) is:

move(3, source, dest, spare)
move(2, source, spare, dest)
move(1, source, dest, spare)

Where it outputs "move ring 1 from source to spare"

The trick here is that the arguments (the stacks) that are passed have different roles for different level. for the 2. level the destination is the 3. levels spare. When moving from spare to destination suddenly the source gets used as spare, but the function doesn't care about that. It merely does it's shuffling until it hits the base case. There are 2^n-1 moves (base cases hit) for n discs.

The recursion finishes the second level before going back and then the 3. layer starts another 2. layer, after moving it's middle, for the move from spare to destination.

Tip: You should add a trace text, like "entering 3, a, c, b" at the beginning and "exiting 3, a, c, b" at the end. That should give you a good idea how many recursions is done and how it's done.

Upvotes: 6

Related Questions