Tower of Hanoi solver in Ruby

Question

Solved the classic Tower of Hanoi problem in Ruby, using recursion. Would love your feedback on this.

# Excellent explanation of the solution at 
# http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/13/hanoi.html
Move = 
 Struct.new :disk, :from, :to do
 def to_s
 "Disk #{disk}: #{from} -> #{to}"
 end
 end
def spare_peg(from, to)
 # returns the peg that is not 'from' nor 'to'
 # e.g. if from="A", to="C" ... then spare="B"
 [*"A".."C"].each {|e| return e unless [from, to].include? e}
end
def hanoi(num, from, to)
 if num == 1 # base case
 return [Move.new(num, from, to)]
 end
 spare = spare_peg(from, to)
 moves = hanoi(num - 1, from, spare) # move everything to the spare peg
 moves << Move.new(num, from, to) # move the sole remaining disk to the 'to' peg
 moves += hanoi(num - 1, spare, to) # move all the disks on top of the 'to' peg
end

Sample output:

puts hanoi(3, "A", "B").each {|move| move.to_s}

Disk 1: A -> B
Disk 2: A -> C
Disk 1: B -> C
Disk 3: A -> B
Disk 1: C -> A
Disk 2: C -> B
Disk 1: A -> B

• BenKoshy: my #1 criticism is that it's very difficult to read and understand. Perhaps there are more OOP solutions on the net worth investigating
• Marc Rohloff: If that is your output then I think that there may be an issue with the algorithm. You cannot move Disk 2 without moving Disk 1 first.
• FloatingRock: @MarcRohloff thanks for the heads up, output was truncated .. edited now (it is the correct output though)
• FloatingRock: @BKSpurgeon I did quite a bit of searching to find a solution that was easy to understand. If you have suggestions for improving readability, I'm all ears.
• BenKoshy: @FloatingRock yes you are quite right - that's a challenge i'm currently working on. i don't quite understand your algorithm but i do marvel at it's brevity and simplicity. do you have tests with it as well?

Answer 1

Looks good!

For the spare_peg you could use detect (which can be called on a range)

("A".."C").detect { |peg| ![from, to].include?(peg) }

or some array arithmetic:

([*"A".."C"] - [from, to]).first

(I'd just use detect.)

And a minor thing: I'd use parentheses for declaring the Struct.new call, just for consistency.

• FloatingRock: I sensed the spare_peg method smelled funny.. Thanks for the suggestions!
• Flambino: @FloatingRock No problem, glad you liked it. By the way, it can sometimes be beneficial to let a question sit a little before accepting an answer, just to see if attracts more reviews. Granted, Ruby isn't the most active language on here, but still. I do appreciate the fake internet points, though so I'm not complaining :) Unrelated: It might be interesting to have a way to show the state of the puzzle - the way the algo works, it just outputs the moves, not so much the overview. It's not really part of the task, but food for thought

Answer 2

Obviously this is one of those things which is opinionated but:

1) It might be simpler to use num.zero? as your base case

2) I would pass the spare tower as a parameter rather than calculating it all the time.

Something like:

def hanoi(num, from, to, spare)
 return [] if num.zero? # base case
 moves = hanoi(num - 1, from, spare, to) # move everything to the spare peg
 moves << Move.new(num, from, to) # move the sole remaining disk to the 'to' peg
 moves += hanoi(num - 1, spare, to, from) # move all the disks on top of the 'to' peg
end

• Marc Rohloff: The call would then be puts hanoi(3, 'A', 'B', 'C').join("\n")
• Marc Rohloff: Also if performance were an issue then I would create the moves array once and pass it as a parameter to avoid creating and joining so many arrays. You can even pre-allocate the size to 2**n-1 if you are super worried about speed.
• Flambino: Good answer. I'd recommend you edit it to include the points mentioned in your comments (the answer is the real content; comments can potentially disappear)
• FloatingRock: @MarcRohloff thanks for reading through it. I don't understand why passing spare as a parameter would be better than calculating it in the method. Either way, it's being done once per recursive call (Notice that spare changes between recursive calls, since from/to change too).
• Marc Rohloff: I said it was opinionated didn't I :) I personally just feel its cleaner to pass it around.