Sep 21, 2011

Source code for slide puzzles of DevQuiz 2011(Google Developer Day)

Is it too late to public source code for DevQuiz?
First purpose is to solve over 1000 puzzles in a day and
this code got 1130 correct answers which was good enough for me.
If anybody has a comment, please feel free to do so! (もちろん日本語でも)

from heapq import heappush, heappop, heapreplace
from copy import copy
from random import seed
class Board:
def __init__(self, w, h, situation):
self.w = w
self.h = h
self.length = len(situation)
self.firstSituation = situation
self.goal_str = self.createGoalMap()
self.scoremap = self.createScoreMap()
print "Board:",w,h,self.scoremap

def move(self, situation, pos, i):
assert(situation[pos]=="0")
i = {0:0, 1:1, 2:2, 3:3, 'U':0, 'D':1, 'L':2, 'R':3}[i]
def switch(i,j):
if(i<j): left,right=i,j
else: left,right = j, i
s = situation
return s[:left] + s[right] + s[left+1:right] + s[left] + s[right+1:]

def moveUp():
if(pos-self.w < 0 or situation[pos- self.w]=='='): return None
else: return(switch(pos, pos-self.w), pos-self.w)

def moveDown():
if(pos+self.w >= self.length or situation[pos+self.w]=='='): return None
else: return switch(pos, pos+self.w), pos+self.w

def moveLeft():
if(pos%self.w==0 or situation[pos-1]=='='): return None
else: return switch(pos, pos-1), pos-1

def moveRight():
if(pos%self.w==self.w-1 or situation[pos+1]=='='): return None
else: return switch(pos, pos+1), pos+1
return [moveUp, moveDown, moveLeft, moveRight][i]()

def isGoal(self, situation, pos):
assert(situation[pos]=="0")
if(pos != self.length -1): return False
return situation == self.goal_str

def score(self, situation):
result = 0
for i in xrange(self.length):
if self.goal_str[i] == situation[i]:
result += self.scoremap[i]
return result


def dump(self, situation):
left=0
while(left < self.length):
print situation[left:left+self.w]
left += self.w
print "---------"

def createGoalMap(self):
situation = self.firstSituation
new_str = ""
for i in xrange(len(situation)):
if situation[i]=="=":
new_str += "="
else:
new_str += "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0"[i]
l=len(situation)
while i in xrange(l-1,0,-1):
if new_str[i]=='=': continue
new_str = new_str[:i] + "0" + new_str[i+1:]
break
return new_str

def createScoreMap(self):
score_map = []
for pos in range(self.length):
r,c = self.h - (pos/self.w), self.w - (pos%self.w)
if self.w > self.h:
score = r + 2*c
elif self.h > self.w:
score = 2*r + c
else:
score = r + c
score_map.append(score*score*score*score)
self.score_sum = sum(score_map)
return score_map

def verify(self, solution):
situation = self.firstSituation
pos = situation.index("0")
for c in solution:
situation, pos = self.move(situation, pos, c)
assert(situation == self.goal_str)


def createReverseDic(board, depth):
reverse_dic = {}
situation = board.goal_str

def recurse_proc(direction, n, tracker, situation, pos):
result = board.move(situation, pos, direction)
if result==None: return
new_situation, new_pos = result
tracker = "DURL"[direction] + tracker

if reverse_dic.has_key(new_situation): return
reverse_dic[new_situation] = tracker

if(n==depth): return

for d in [[0,2,3],[1,2,3],[0,1,2],[0,1,3]][direction]:
recurse_proc(d, n+1, tracker, new_situation, new_pos)

reverse_dic[situation] = ""
pos = situation.index("0")
for d in [0,1,2,3]:
recurse_proc(d, 0, "", situation, pos)

return reverse_dic


def solveProblem(board, reverse_dic, depth, stages):
track_dic = {}
solutions = []
score_heap = []
situation = board.firstSituation
heappush(score_heap, (board.score(situation),situation,""))

def recurse_proc(direction, n, tracker, situation, pos):
result = board.move(situation, pos, direction)
if result==None: return
new_situation, new_pos = result
tracker += "UDLR"[direction]

if(new_situation in reverse_dic):
tracker += reverse_dic[new_situation]
solutions.append(tracker)

if track_dic.has_key(new_situation): return
track_dic[new_situation] = tracker

if(n==depth):
if len(score_heap) < 8:
heappush(score_heap, (board.score(new_situation), new_situation, tracker))
else:
heapreplace(score_heap, (board.score(new_situation), new_situation, tracker))
return

for d in [[0,2,3],[1,2,3],[0,1,2],[0,1,3]][direction]:
recurse_proc(d, n+1, tracker, new_situation, new_pos)


for k in range(stages):
seeds = copy(score_heap)
seeds.reverse()
score_heap = []
for score,situation,tracker in seeds:
print "--", score, situation, tracker
for d in [0,1,2,3]:
recurse_proc(d, 0, tracker, situation, situation.index("0"))
if len(solutions) > 0:
solution = solutions[0]
for s in solutions[1:]:
if len(solution) > len(s): solution = s
return solution
##Extra Tries
for k in range(stages):
seeds = copy(score_heap)
seeds.reverse()
score_heap = []
seeds = filter(lambda tpl: 1.0*tpl[0]/board.score_sum>0.9, seeds)
if len(seeds)==0: break
for score,situation,tracker in seeds:
print "++", score, situation, tracker
for d in [0,1,2,3]:
recurse_proc(d, 0, tracker, situation, situation.index("0"))
if len(solutions) > 0:
solution = solutions[0]
for s in solutions[1:]:
if len(solution) > len(s): solution = s
return solution

return None

f = open("problems.txt")
lines = f.read().split("\n")
lefts,rights,ups,downs = map(lambda s: int(s), lines[0].split(" "))
problems = int(lines[1])
print problems, lefts, rights, ups, downs

problems = lines[2:]
results = []
solved = 0
tried = 0

solved_static = {}
tried_static = {}
for num,problem in enumerate(problems):
args = problem.split(',')
w, h, s = int(args[0]), int(args[1]), args[2]
##if len(s) != 24:
## results.append("")
## continue
tried += 1
if w*h in tried_static: tried_static[w*h] += 1
else: tried_static[w*h] = 1
print num, s,
board = Board(w,h,s)
pos = s.index('0')

rev_depth,search_depth,stages=8,8,12
if(w*h==9): rev_depth,search_depth,stages = 20,20,2
elif(w*h==12): rev_depth,search_depth,stages = 20,20,2
elif(w*h==15): rev_depth,search_depth,stages = 15,15,4
elif(w*h==18): rev_depth,search_depth,stages = 12,12,8
elif(w*h==20): rev_depth,search_depth,stages = 10,10,10

reverse_dic = createReverseDic(board,rev_depth)
print "reverse track calculated"

solution = solveProblem(board, reverse_dic, search_depth, stages)
if solution != None:
results.append(solution)
solved += 1
if w*h in solved_static: solved_static[w*h] += 1
else: solved_static[w*h] = 1
else:
results.append("")
print "status: %d/%d(%.2f%%)"%(solved, tried, 100.0*solved/tried)


f = open("result.txt", 'w')
for l in results:
f.write(l+"\n")
f.close()

sizes = tried_static.keys()
sizes.sort()
print "======STATISTICS======"
for size in sizes:
solved = solved_static.get(size) or 0
print "size:%d %d/%d"%(size, solved, tried_static[size])
print "======================"

No comments: