Tower of Hanoi solver in Ruby

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

• my #1 criticism is that it's very difficult to read and understand. Perhaps there are more OOP solutions on the net worth investigating – BKSpurgeon Apr 19 '17 at 9:29
• 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. – Marc Rohloff Apr 19 '17 at 19:50
• @MarcRohloff thanks for the heads up, output was truncated .. edited now (it is the correct output though) – FloatingRock Apr 20 '17 at 6:14
• @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. – FloatingRock Apr 20 '17 at 6:19
• @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? – BKSpurgeon Apr 20 '17 at 7:12

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.

• I sensed the spare_peg method smelled funny.. Thanks for the suggestions! – FloatingRock Apr 19 '17 at 8:27
• @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 – Flambino Apr 19 '17 at 10:03

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

• The call would then be puts hanoi(3, 'A', 'B', 'C').join("\n") – Marc Rohloff Apr 19 '17 at 16:47
• 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. – Marc Rohloff Apr 19 '17 at 16:51
• 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) – Flambino Apr 20 '17 at 0:13
• @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). – FloatingRock Apr 20 '17 at 6:17
• I said it was opinionated didn't I :) I personally just feel its cleaner to pass it around. – Marc Rohloff Apr 20 '17 at 15:18