Skip to content

Instantly share code, notes, and snippets.

@sorah

sorah/solve.rb Secret

Created September 12, 2011 03:37
Show Gist options
  • Save sorah/ae7c4c0179fd62c17b20 to your computer and use it in GitHub Desktop.
Save sorah/ae7c4c0179fd62c17b20 to your computer and use it in GitHub Desktop.
Google Developer Day 2011 Tokyo / DevQuiz: Sliding puzzles
# 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