-
-
Save sorah/ae7c4c0179fd62c17b20 to your computer and use it in GitHub Desktop.
Google Developer Day 2011 Tokyo / DevQuiz: Sliding puzzles
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
# this script requires ruby 1.9.2 | |
# usage: ruby solve_with_desc.rb [filename] | |
# or ruby solve_with_desc.rb < filename (via STDIN) | |
require 'pp' | |
class Array | |
def hdup | |
self.inject([]){|r,i| r << i.dup } | |
end | |
end | |
module Puzzle | |
def self.parse(input=ARGF.read) | |
Parser.new(input).parse | |
end | |
class ProblemList | |
include Enumerable | |
attr_reader :solves | |
def initialize(ary,l,r,u,d) | |
@problems = ary | |
@solves = nil | |
@l_limit = l | |
@r_limit = r | |
@u_limit = u | |
@d_limit = d | |
@l = \ | |
@r = \ | |
@u = \ | |
@d = 0 | |
end | |
def [](i) | |
@problems[i] | |
end | |
def each(&block) | |
@problems.each &block | |
end | |
def solve_all | |
@problems.each {|problem| puts problem.solve } | |
end | |
def limit(of=nil) | |
if of | |
raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(of.to_sym) | |
eval "@#{of}_limit" | |
else | |
Hash[[:l,:r,:u,:d].map{|t| [t, limit(t)] }] | |
end | |
end | |
def used(type=nil) | |
if type | |
raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym) | |
eval "@#{type}" | |
else | |
Hash[[:l,:r,:u,:d].map{|t| [t, used(t)] }] | |
end | |
end | |
def remain(of=nil) | |
if of | |
raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(of.to_sym) | |
limit(of) - used(of) | |
else | |
Hash[[:l,:r,:u,:d].map{|t| [t, remain(t)] }] | |
end | |
end | |
def use(type) | |
case type | |
when Hash | |
type.each do |k,v| | |
eval "@#{k} += #{v}" | |
end | |
else | |
raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym) | |
eval "@#{type} += 1" | |
end | |
self | |
end | |
end | |
class Problem | |
attr_reader :board, :commits, :latest, :no, :empty | |
def initialize(board, i=0) | |
@board = board | |
@latest = board.hdup | |
@first = to_s | |
@commits = [] | |
@empty = nil | |
@no = i | |
#@dic = {} | |
end | |
def latest | |
@latest | |
end | |
def used | |
@commits.inject({l:0,r:0,u:0,d:0}) do |r,i| | |
r[i]+=1;r | |
end | |
end | |
def use(type) | |
raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym) | |
detect_empty unless @empty | |
case type.to_sym | |
when :l | |
return false if @empty[1] == 0 | |
if @latest[@empty[0]][@empty[1]-1] == :"=" | |
return false | |
else | |
@latest[@empty[0]][@empty[1]-1], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]][@empty[1]-1] | |
@empty[1] -= 1 | |
end | |
when :r | |
return false if @empty[1] == (@latest[@empty[0]].size-1) | |
if @latest[@empty[0]][@empty[1]+1] == :"=" | |
return false | |
else | |
@latest[@empty[0]][@empty[1]+1], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]][@empty[1]+1] | |
@empty[1] += 1 | |
end | |
when :u | |
return false if @empty[0] == 0 | |
if @latest[@empty[0]-1][@empty[1]] == :"=" | |
return false | |
else | |
@latest[@empty[0]-1][@empty[1]], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]-1][@empty[1]] | |
@empty[0] -= 1 | |
end | |
when :d | |
return false if @empty[0] == (@latest.size-1) | |
if @latest[@empty[0]+1][@empty[1]] == :"=" | |
return false | |
else | |
@latest[@empty[0]+1][@empty[1]], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]+1][@empty[1]] | |
@empty[0] += 1 | |
end | |
end | |
@commits << type.to_sym | |
true | |
end | |
def detect_empty | |
@empty = board.each_with_index.inject([]) do |r,(l,i)| | |
r[1] ? r : [i,l.index(nil)] | |
end | |
end | |
def goal? | |
if @latest[-1][-1].nil? | |
m = self.to_s | |
a = m.gsub(/[=0]/,"") | |
b = a.chars.sort.join | |
a == b# && m[-1] == "0" #&& (m.gsub(/\d/,"!") == n.gsub(/\d/,"!")) | |
end | |
end | |
def to_s | |
@latest.map do |l| | |
l.map{|x| x.nil? ? :"0" : x }.join | |
end.join | |
end | |
def undo(n=1) | |
n.times do | |
@commits.pop | |
end | |
self | |
end | |
def complete | |
@commits.join.upcase | |
end | |
def solve | |
reset | |
queue = [[@board.hdup, @commits.dup, detect_empty]] | |
types = [:l,:r,:u,:d] | |
hash = {} | |
i = 0 | |
while (a=queue.shift) | |
if i != a[1].join.size | |
puts a[1].join | |
i = a[1].join.size | |
end | |
types.each do |t| | |
set *a | |
next if reverse?(t) | |
next unless use(t) | |
return complete if goal? | |
unless hash.has_key?(@latest) | |
hash[@latest] = true | |
q = [@latest.hdup, @commits.dup, @empty.dup] | |
queue << q | |
end | |
#@commits.pop #undo | |
end | |
end | |
end | |
def set(b,c,s) | |
@latest = b.hdup | |
@commits = c.dup | |
@empty = (s.nil? ? nil : s.dup) | |
end | |
def reset | |
@commits = [] | |
@empty = nil | |
end | |
class CannotMove < Exception; end | |
class LimitReached < Exception; end | |
class Goal < Exception; end | |
def reverse?(t) | |
hash = { | |
l: :r, | |
r: :l, | |
u: :d, | |
d: :u | |
} | |
hash[@commits[-1]] == t | |
end | |
end | |
class Parser | |
attr_reader :input, :list | |
def initialize(input) | |
@input = input | |
@list = nil | |
end | |
def parse | |
lines = input.split(/\r?\n/) | |
l,r,u,d = lines.shift.split(/ /).map(&:to_i) | |
problem_count = lines.shift.to_i | |
problems = [] | |
while (problem = parse_problem(lines.shift, problems.size)) | |
problems << problem | |
end | |
raise "problem_count != problems.size" unless problems.size == problem_count | |
problems.sort_by{|problem| problem.board.size * problem.board[0].size } | |
@list = ProblemList.new(problems,l,r,u,d) | |
end | |
private | |
def parse_problem(line, i) | |
if line | |
w,h,b = line.split(/,/) | |
b = b.chars.to_a | |
w,h = w.to_i, h.to_i | |
ls = [] | |
h.times do |i| | |
l = [] | |
w.times do |j| | |
chr = b.shift.to_sym | |
if chr == :"0" | |
l << nil | |
else | |
l << chr | |
end | |
end | |
ls << l | |
end | |
raise "b is not empty" unless b.empty? | |
Problem.new ls, i | |
else | |
nil | |
end | |
end | |
end | |
end | |
#pp Puzzle.parse | |
Puzzle.parse(ARGF.read).solve_all |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment