I've recently subscribed to Coding for Interviews and received my first email today. The content is great and you should join. Even if you're not looking for a job, it's a short read with nice topics to refresh your memory.

Today's assignment was with stacks. I've used stacks to reverse a list in O(n) but today's challenge was to solve the Tower of Hanoi problem without recursion.

Here's my solution:

# https://gist.github.com/nhocki/4716874

Hanoi = Struct.new(:disk, :source, :dest, :spare)

def move(hanoi)
  "Move #{hanoi.disk.abs} from #{hanoi.source} to #{hanoi.dest}"
end

class Stack
  def initialize
    @data = []
  end

  def push(hanoi)
    @data.unshift(hanoi)
  end

  def pop
    @data.shift
  end

  def peek
    @data.first
  end

  def empty?
    @data.empty?
  end
end


# Resolve the Tower of Hanoi problem with a Stack. You can't use recursion
# in it's traditional way, but adding everything to a stack works the same.
#
# Notice you have to invert the order of the calls to the recursive function
# since the stack is **Last In - First Out**.
def stacker hanoi
  stack = Stack.new
  stack.push(hanoi)

  until stack.empty? do
    hanoi = stack.pop

    if hanoi.disk <= 1
      puts move(hanoi)
    else
      left  = Hanoi.new(hanoi.disk - 1, hanoi.source, hanoi.spare, hanoi.dest)
      right = Hanoi.new(hanoi.disk - 1, hanoi.spare, hanoi.dest, hanoi.source)
      hanoi.disk = -hanoi.disk # force printing it next time it appears
      stack.push right
      stack.push hanoi
      stack.push left
    end
  end
end


# Resolve the Tower of Hanoi problem with recursion.
def recursive hanoi
  if hanoi.disk == 1
    puts move(hanoi)
  else
    left  = Hanoi.new(hanoi.disk - 1, hanoi.source, hanoi.spare, hanoi.dest)
    right = Hanoi.new(hanoi.disk - 1, hanoi.spare, hanoi.dest, hanoi.source)
    recursive(left)
    puts move(hanoi)
    recursive(right)
  end
end

h = Hanoi.new(3, 'A', 'B', 'C')

recursive(h)
puts "\n\n"
stacker(h)

There's another iterative solution but I haven't implemented it. So, if you did or have some other way to solve this, I'd love to know on Twitter @nhocki