Google Developer Day 2011:DevQuiz解答晒し大会(7)
スライドパズル
結果はというと……364/5000。いまひとつうまくいかなかった感じ。
- 基本は幅優先探索
- 評価値の小さいものを優先的に探索
- ある程度展開した時点で評価値の小さい64組以外をカット(3*3を除く)
- 評価値 = (パネルのマンハッタン距離の和)+(異なるパネル数)
A*探索も実装してはみたが投入まではいかなかった。
コードはrubyで実装。Pentium4 2.4GHz、メモリ4GBのマシンで実行した。マス数9～16の状態で一通りまわして300問、マス数18～25は1000問くらいの時点で打ち切って64問という具合。効率を一切考えずに書いたんで課題は多いかな。
プログラムは3つに分割した。
1. solver/mod_bfsearch.rb
load 'solver/util.rb'
class Solver
include SolverUtil
attr :board
attr :width
attr :height
attr :result
def initialize(b,w,h)
@board=b
@width=w
@height=h
r="123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[0..b.length-2] + '0'
(0..b.length-1).each { |pos|
r[pos]='=' if b[pos]=='='
}
@result=r
end
def solve(start=@board,close=[])
queue=[]
board=start
init_score = major(@board)
move = ''
until (board == @result || move == nil)
available(board,@width,@height).split('').delete_if { |c|
after = move(c,board,@width,@height)
close.include? after
}.map { |c|
after = move(c,board,@width,@height)
score = major(after)
queue.push [move+c, after, score] if (init_score > score || @width*@height < 10)
close.push after
}
if (queue.length > 512)
queue.sort! { |a, b| a[2] <=> b[2] }
if (@width*@height > 10)
new_queue = queue[0..63]
queue = new_queue
# init_score = (init_score * 9) / 10
init_score = queue[63][2]
end
end
(move, board, s) = queue.shift
end
move
end
def major(board)
dist=0
(0..board.length-1).each { |n|
if (board[n] != '=')
m = @result.index(board[n])
dist += dist(m,n,@width)
end
}
dist + diffs(board)
end
def dist(m,n,w)
d = abs(m-n)/w
if (m > n)
m -= d*w
else
n -= d*w
end
d+abs(m-n)
end
def abs(x)
x = -x if x < 0
x
end
def diffs(board)
d = 0
(0..board.length-1).each { |n|
d += 1 if board[n] != @result[n] && board[n] != '0'
}
d
end
end
2. solver/util.rb
module SolverUtil
def available(board,width,height)
result=''
pos = board.index('0')
result += 'L' if (pos%width != 0 && board[pos-1] != '=')
result += 'R' if (pos%width != width-1 && board[pos+1] != '=')
result += 'U' if (pos/width != 0 && board[pos-width] != '=')
result += 'D' if (pos/width != height-1 && board[pos+width] != '=')
result
end
def move(c,board,width,height)
case c
when 'L'
result=left(board,width,height)
when 'R'
result=right(board,width,height)
when 'U'
result=up(board,width,height)
when 'D'
result=down(board,width,height)
end
result
end
def left(board,width,height)
result=board.dup
pos=board.index('0')
if (pos%width != 0 && board[pos-1] != '=')
result[pos]=result[pos-1]
result[pos-1]='0'
end
result
end
def right(board,width,height)
result = board.dup
pos = board.index('0')
if (pos%width != width-1 && board[pos+1] != '=')
result[pos]=result[pos+1]
result[pos+1]='0'
end
result
end
def up(board,width,height)
result = board.dup
pos = board.index('0')
if (pos/width != 0 && board[pos-width] != '=')
result[pos]=result[pos-width]
result[pos-width]='0'
end
result
end
def down(board,width,height)
result = board.dup
pos = board.index('0')
if (pos/width != height-1 && board[pos+width] != '=')
result[pos]=result[pos+width]
result[pos+width]='0'
end
result
end
end
3. main.rb
load 'solver/mod_bfsearch.rb'
def consume_count(s,c)
r=0
s.split('').each { |c1|
r += 1 if c1 == c
}
r
end
result_file = ARGV[0]
min_size = ARGV[1].to_i
max_size = ARGV[2].to_i
result = open(result_file,"wb")
open("problems.txt", "r") do |f|
move_limits = f.gets.split(' ').map{ |n| n.to_i }
num_problems = f.gets.to_i
num = 0
solved = 0
while (f.gets)
w,h,b=$_.chomp.split(',')
w = w.to_i
h = h.to_i
STDERR.puts "#{num+1} #{solved} #{b} #{w} #{h} #{move_limits}"
if (w.to_i * h.to_i > max_size || w.to_i * h.to_i < min_size)
result.puts ''
else
board=Solver.new(b,w.to_i,h.to_i)
s=''
begin
s = board.solve
if (s != nil)
move_consume = ['L','R','U','D'].map { |c| consume_count(s,c) }
(0..3).each { |n|
move_limits[n] -= move_consume[n]
}
STDERR.puts "#{s} #{move_consume}"
result.puts s
solved += 1
else
result.puts ''
end
rescue SystemStackError
result.puts ''
end
end
num += 1
end
end
