hanoi.rb

require 'pp'

def print_plates(plates, disp_interval)
  max_plate = plates.map{|plate| plate.max || 0}.max
  puts
  max_plate.downto(0) do |i|
    plates.each do |plate|
      width = plate[i].to_i
      full_width = [width * 2 - 1, 0].max
      max_plate_full_width = max_plate * 2 - 1
      padding = (max_plate_full_width - full_width) / 2
      print ' ' * padding
      if full_width.zero?
        print ' '
      else
        print '*' * full_width
      end
      print ' ' * padding
      print ' | '
    end
    print "\n"
  end
  puts '-' * (3 * 2 * (max_plate + 1))
  sleep(disp_interval)
end

def finish_if_solved(plates, history, disp_interval)
  empty_plates = 0
  plates.each_with_index do |plate, i|
    if i != plates.size - 1
      empty_plates += 1 if plate.empty?
    end
  end
  if empty_plates == plates.size - 1
    puts "$$$$$$ Clear!!!! $$$$$$"
    history.each do |snapshot|
      print_plates(snapshot, disp_interval)
    end
    exit 0
  end
end

def clone_plates_with_moving_item(plates, moved_item, from, to)
  idx = 0
  moved_plates = plates.inject([]) {|a, p|
    copied_plate = p.clone
    copied_plate.pop if idx == from
    copied_plate << moved_item if idx == to
    a << copied_plate
    idx += 1
    a
  }
end

def give_up
  raise "!!!!!! Can't solve... !!!!!!"
end

def solve(orig_plates, disp_interval)
  options = [
    {plates: orig_plates, history: [orig_plates]}
  ]
  while options.size > 0 do
    options.each do |option|
      plates = option[:plates]
      history = option[:history]
    
      finish_if_solved(plates, history, disp_interval)

      # Search an available option
      options = []
      plates.each_with_index do |plate, i|
        next if plate.empty?
        top = plate.last

        plates.each_with_index do |another_plate, j|
          next if i == j
          if another_plate.empty? || top < another_plate.last
            moved_plates = clone_plates_with_moving_item(plates, top, i, j)

            unless history.include?(moved_plates)
              options << {plates: moved_plates, history: history + [moved_plates]}
            end
          end
        end
      end
    end
  end

  give_up
end

disp_interval = 0.1
if ARGV[0]
  disp_interval = Float(ARGV[0])
end

solve([[8, 7, 6, 5, 4, 3, 2, 1], [], []], disp_interval)

hanoi_with_tail_recursion.rb

require 'pp'

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: false,
  trace_instruction: false
}

require './internal_hanoi_with_tail_recursion'

def solve(plates, disp_interval)
  solve_rec(plates, [], [], disp_interval)
  give_up
end

disp_interval = 0.1
if ARGV[0]
  disp_interval = Float(ARGV[0])
end

solve([[8, 7, 6, 5, 4, 3, 2, 1], [], []], disp_interval)

internal_hanoi_with_tail_recursion.rb

require 'pp'

def print_plates(plates, disp_interval)
  max_plate = plates.map{|plate| plate.max || 0}.max
  puts
  max_plate.downto(0) do |i|
    plates.each do |plate|
      width = plate[i].to_i
      full_width = [width * 2 - 1, 0].max
      max_plate_full_width = max_plate * 2 - 1
      padding = (max_plate_full_width - full_width) / 2
      print ' ' * padding
      if full_width.zero?
        print ' '
      else
        print '*' * full_width
      end
      print ' ' * padding
      print ' | '
    end
    print "\n"
  end
  puts '-' * (3 * 2 * (max_plate + 1))
  sleep(disp_interval)
end

def finish_if_solved(plates, history, disp_interval)
  empty_plates = 0
  plates.each_with_index do |plate, i|
    if i != plates.size - 1
      empty_plates += 1 if plate.empty?
    end
  end
  if empty_plates == plates.size - 1
    puts "$$$$$$ Clear!!!! $$$$$$"
    history << plates
    history.each do |snapshot|
      print_plates(snapshot, disp_interval)
    end
    exit 0
  end
end

def clone_plates_with_moving_item(plates, moved_item, from, to)
  idx = 0
  moved_plates = plates.inject([]) {|a, p|
    copied_plate = p.clone
    copied_plate.pop if idx == from
    copied_plate << moved_item if idx == to
    a << copied_plate
    idx += 1
    a
  }
end

def give_up
  raise "!!!!!! Can't solve... !!!!!!"
end

def search_available_plates_list(plates, history)
  options = []
  plates.each_with_index do |plate, i|
    next if plate.empty?
    top = plate.last

    plates.each_with_index do |another_plate, j|
      next if i == j
      if another_plate.empty? || top < another_plate.last
        moved_plates = clone_plates_with_moving_item(plates, top, i, j)

        unless history.include?(moved_plates)
          options << moved_plates
        end
      end
    end
  end
  options
end

def solve_rec(plates, history, options_stack, disp_interval)
  finish_if_solved(plates, history, disp_interval)
  unless history.include?(plates)
    history << plates
  end
  next_plates_list = search_available_plates_list(plates, history)
  if next_plates_list.size > 0
    next_plates = next_plates_list.shift
    options_stack << next_plates_list unless next_plates_list.empty?
  else
    if options_stack.size > 0
      next_plates = options_stack.last.shift
      if options_stack.last.empty?
        options_stack.pop
      end
    end
  end

  return unless next_plates

  solve_rec(next_plates, history, options_stack, disp_interval)
end