4
\$\begingroup\$

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

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.