hanoi.rb

#!/usr/bin/env ruby

class Hanoi

  # @return [Integer]
  attr_reader :rods

  # @return [Integer]
  attr_reader :discs


  # @param [Integer] rods
  # @param [Integer] discs
  #
  def initialize( rods, discs )
    raise ArgumentError unless rods > 0
    raise ArgumentError unless discs > 0

    @rods = rods
    @discs = discs
  end


  # @return [Position, nil]
  #
  def solve
    tried = []
    positions = [ initial_position ]

    while !positions.empty?
      next_positions = []

      for position in positions
        next if tried.include?( position )
        tried << position

        if position.winning?
          return position
        end

        next_positions.concat position.next_positions
      end

      positions = next_positions
    end

    nil
  end


  # All discs stacked in a cone on the leftmost rod
  # @return [Position]
  #
  def initial_position
    stacks = [ [] ] * ( @rods - 1 )
    stacks.unshift Array.new( ( 1..@discs ).to_a.reverse )

    Position.new self, stacks, nil, nil
  end

end



class Position

  # @return [Enumerable<Array>]
  attr_reader :stacks

  # @return [Position, nil]
  attr_reader :prior

  # @return [Move]
  attr_reader :move


  # @param [Hanoi] hanoi
  # @param [Enumerable<Array>] stacks
  #   Stacks in left-to-right order. Each stack is an array where elements
  #   with higher indices are higher in the stack, i.e. stack[ -1 ] is the top.
  #   stack[ i ] < stack[ j ] where j > i.
  # @param [Position] prior
  #   The prior position
  # @param [Move] move 
  #   The most recent move that led to this position
  #
  def initialize( hanoi, stacks, prior, move )
    @hanoi = hanoi
    @stacks = stacks
    @prior = prior
    @move = move
  end


  # @param [Position] other
  # @return [Boolean]
  #
  def eql?( other )
    stacks.eql? other.stacks
  end


  # @param [Position] other
  # @return [Boolean]
  #
  def ==( other )
    eql? other
  end


  # @return [Boolean]
  #
  def winning?
    @stacks[ -1 ].length == @hanoi.discs
  end


  # @return [Array<Position>]
  #
  def next_positions
    result = []

    stacks.each_with_index do |s, i|
      stacks.each_with_index do |t, j|
        if i != j && s.last && ( t.last.nil? || s.last < t.last )
          result << apply_move( Move.new( i, j ) )
        end
      end
    end

    result
  end


  # @return [Position]
  #   A new Position; does not modify self
  #
  def apply_move( move )
    stacks = @stacks.map( &:dup )
    stacks[ move.to ].push stacks[ move.from ].pop

    Position.new @hanoi, stacks, self, move
  end


  # The moves that lead to this position, in chronological order
  # @return [Array<Moves>]
  #
  def all_moves
    result = []
    position = self

    while position && position.move
      result.push position.move
      position = position.prior
    end

    result.reverse
  end

end



class Move

  # @return [Integer]
  attr_reader :from

  # @return [Integer]
  attr_reader :to

  # @param [Integer] from
  # @param [Integer] to
  #
  def initialize( from, to )
    @from = from
    @to = to
  end

  # @return [String]
  #
  def to_s
    "#{ from } => #{ to }"
  end

end


rods = ARGV[ 0 ] ? ARGV[ 0 ].to_i : 3
discs = ARGV[ 1 ] ? ARGV[ 1 ].to_i : 4

position = Hanoi.new( rods, discs ).solve

if position
  position.all_moves.each do |move|
    puts move
  end
else
  puts "No solution"
end