Skip to content

Instantly share code, notes, and snippets.

@kornysietsma
Created March 29, 2010 02:06
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save kornysietsma/347262 to your computer and use it in GitHub Desktop.
class KornyHanoi
def initialize(options={:discs => 8})
@discs = options[:discs]
@all_pegs = [:from, :pivot, :to]
@pegs = {:from => [], :to => [], :pivot => []}
@discs.downto(1) do |num|
@pegs[:from] << num
end
end
def solve
print_state
one_peg = :from
clockwise = {:from => :pivot, :pivot => :to, :to => :from}
anticlockwise = {:from => :to, :pivot => :from, :to => :pivot}
one_move = @discs % 2 == 0 ? clockwise : anticlockwise
while !complete?
# move the 'one' disc
next_one_peg = one_move[one_peg]
shift(:from => one_peg, :to => next_one_peg)
one_peg = next_one_peg
print_state
break if complete?
# and make the only legal move - assume an order of the remaining pegs:
from_peg, to_peg = @all_pegs - [one_peg]
# is this order ok?
if @pegs[from_peg].last == nil || ( @pegs[to_peg].last != nil && @pegs[from_peg].last > @pegs[to_peg].last )
# if not, swap order
from_peg, to_peg = to_peg, from_peg
end
shift(:from => from_peg, :to => to_peg)
print_state
end
end
def complete?
@pegs[:to].length == @discs
end
def shift(params)
from = params[:from]
to = params[:to]
raise "from peg (#{from}) is empty!" if @pegs[from].empty?
@pegs[to].push @pegs[from].pop
end
def print_state
puts @pegs.inspect
end
end
KornyHanoi.new(:discs => 9).solve
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment