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