Created
November 20, 2011 05:30
-
-
Save adamstegman/1379837 to your computer and use it in GitHub Desktop.
Hanoi solver for Facebook sample challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
# coding: UTF-8 | |
# K pegs, 3 <= K <= 5 | |
# N discs, radius 1 to N, 1 <= N <= 8 | |
# given initial positions and final positions, output minimum moves to achieve it | |
# Input Format: | |
# N K | |
# 2nd line contains N integers. | |
# Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. | |
# 3rd line denotes the final configuration in a format similar to the initial configuration. | |
# Output Format: | |
# The first line contains M - The minimal number of moves required to complete the transformation. | |
# The following M lines describe a move, by a peg number to pick from and a peg number to place on. | |
# If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. | |
class Peg | |
attr_reader :discs | |
def initialize | |
# current radii on this peg | |
@discs = [] | |
end | |
# @return [Boolean] if this peg can accept this radius | |
def accepts?(radius) | |
!discs.first || (radius < discs.first) | |
end | |
# fails silently, use #accepts? before calling | |
def push(radius) | |
@discs.push radius if accepts? radius | |
end | |
def pop | |
@discs.pop | |
end | |
def peek | |
@discs.last | |
end | |
def inspect | |
discs.inspect | |
end | |
end | |
class Game | |
attr_reader :moves | |
def initialize(num_pegs, initial_positions, final_positions) | |
# inputs are 1-based indexes | |
initial_positions = initial_positions.map {|p| p - 1} | |
final_positions = final_positions.map {|p| p - 1} | |
# current state of the pegs | |
@pegs = [] | |
# destination state of the pegs | |
@final_positions = final_positions | |
# disc radii still to place correctly | |
@discs_to_solve = [] | |
# moves made to place discs correctly | |
@moves = [] | |
num_pegs.times do | |
@pegs << Peg.new | |
end | |
# place discs | |
initial_positions.each_with_index do |peg_index, radius| | |
@pegs[peg_index].discs << radius | |
@discs_to_solve << radius | |
end | |
@pegs.each {|peg| peg.discs.sort!.reverse!} | |
@discs_to_solve.sort!.reverse! | |
end | |
# ex: game.move(from: 1, to: 3) | |
def move(args) | |
from_peg = @pegs[args[:from]] | |
to_peg = @pegs[args[:to]] | |
disc = from_peg.peek | |
if to_peg.accepts?(disc) | |
@moves << [args[:from] + 1, args[:to] + 1] # output is 1-based indexes | |
from_peg.pop | |
to_peg.push disc | |
end | |
end | |
# @return [Integer] index of peg containing +disc+ | |
def find(disc) | |
@pegs.each_with_index {|peg, i| return i if peg.discs.include? disc} | |
end | |
def solve(disc) | |
dest_index = @final_positions[disc - 1] | |
dest = @pegs[dest_index] | |
current_index = find(disc) | |
current = @pegs[current_index] | |
unless dest.discs.include?(disc) | |
unless dest.accepts?(disc) && current.peek == disc | |
# move discs above this one if not immediately available | |
above_disc = current.discs.reverse | |
above_disc = above_disc[0...above_disc.index(disc)] | |
above_dest = dest.discs.reverse | |
above_dest.delete_if {|d| d > disc} | |
(above_disc + above_dest).sort!.reverse!.each do |disc_to_move| | |
# don't move to the destination (or the current peg, that's stupid) TODO: this may be flawed logic | |
@pegs.each_with_index do |peg, peg_index| | |
next if peg_index == current_index || peg_index == dest_index | |
if peg.accepts? disc_to_move | |
unless @discs_to_solve.include? disc_to_move | |
@discs_to_solve << disc_to_move | |
@discs_to_solve.sort!.reverse! | |
end | |
move from: current_index, to: peg_index | |
break | |
end | |
end | |
end | |
end | |
raise "bad state: #{inspect}" unless dest.accepts?(disc) && current.peek == disc | |
move from: current_index, to: dest_index | |
end | |
@discs_to_solve.delete disc | |
end | |
def solve! | |
while @discs_to_solve.size > 0 | |
raise "too many moves" if @moves.size >= 7 # never more than 7 moves | |
solve @discs_to_solve.first | |
end | |
end | |
def inspect | |
@pegs.map(&:inspect).inspect | |
end | |
end | |
def readline_to_is | |
ARGF.readline.split.map(&:to_i) | |
end | |
num_discs,num_pegs = readline_to_is | |
initial_positions = readline_to_is | |
final_positions = readline_to_is | |
game = Game.new(num_pegs, initial_positions, final_positions) | |
game.solve! | |
puts game.moves.size | |
game.moves.each do |from, to| | |
puts "#{from} #{to}" | |
end |
how can i run it on ideone?... it gives me error there... will this work for this test case?
7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I wrote this as quickly as possible (not quickly enough), so it's not well-commented and is pretty messy code.