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 "======================"
Comments