# 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 Apr 19, 2017 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. Apr 19, 2017 at 19:50
• @MarcRohloff thanks for the heads up, output was truncated .. edited now (it is the correct output though) Apr 20, 2017 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. Apr 20, 2017 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? Apr 20, 2017 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! Apr 19, 2017 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 Apr 19, 2017 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") Apr 19, 2017 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. Apr 19, 2017 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) Apr 20, 2017 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). Apr 20, 2017 at 6:17
• I said it was opinionated didn't I :) I personally just feel its cleaner to pass it around. Apr 20, 2017 at 15:18