### 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