Skip to content

Instantly share code, notes, and snippets.

@jonahb
Created March 2, 2016 22:55
Show Gist options
  • Save jonahb/6726ddcc6fef4d3ac81a to your computer and use it in GitHub Desktop.
Save jonahb/6726ddcc6fef4d3ac81a to your computer and use it in GitHub Desktop.
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment