Pythonで。
copyモジュールを使うと遅いのでコピーしないようにした。アルゴリズムは、壁を考慮したマンハッタン距離をつかったBFS枝刈り。狩りかたは探索時のベストスコアを覚えていてそれより閾値以下の経路をバシバシ切る。
キツすぎて経路が見つからない場合は閾値を一つ上げて再探索。一問当たりの制限時間を決めておいて時間の掛かり過ぎる問題はカット。
それからmultiprocessingモジュールのpmapをはじめてつかったけど、これは超便利ですね。なにも考えなくてもコアの数だけ速くなるし
これで、2.4Gのcore2 duoのmacbookで3600問解けた。
ファイルが2つにわかれているのは片方をCythonで高速化しようと奮闘した結果、速く出来なかったという。最初からクラスにしないで解くべきだったなぁと。
あと、debquizで触れたGoにすっかり魅了されましたね。静的型付けでコンパイルできる言語もそこそこできるようになっておきたいなぁ。
slidepuzzle.py
import time from os import environ DEBUG = environ.get('debug', False) class SlidePuzzle(object): """slidepuzzle""" def __init__(self, width, height, initdata): self.width = width self.height = height self.data = [c for c in initdata] self.pos0 = self.find_pos0() self.valid = {} for vi,vc in enumerate('123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:width*height-1]): self.valid[vc] = vi self.maze_score_table = self.maze_score_init() self.score = self.calc_score() def display(self): l = len(self.data) w = self.width d = self.data return "".join(["".join(d[i:(i+w if i+w < l else l) ])+'\n' for i in range(0,l,w)])[:-1] def calc_score(self): return self.maze_score() def can_move(self,direction,last_moved): if direction == 'U': if last_moved == 'D': return False return False if (self.pos0) / self.width == 0 or self.data[self.pos0-self.width] == '=' else True elif direction == 'D': if last_moved == 'U': return False return False if (self.pos0) / self.width == self.height-1 or self.data[self.pos0+self.width] == '=' else True elif direction == 'L': if last_moved == 'R': return False return False if self.pos0 % self.width == 0 or self.data[self.pos0-1] == '=' else True elif direction == 'R': if last_moved == 'L': return False return False if self.pos0 % self.width == self.width-1 or self.data[self.pos0+1] == '=' else True else: return False def next_pattern(self,last_moved): c = 0 if last_moved != 'D': if (self.pos0) / self.width != 0 or self.data[self.pos0-self.width] != '=': c += 1 if last_moved == 'U': if (self.pos0) / self.width != self.height-1 or self.data[self.pos0+self.width] != '=': c += 1 if last_moved == 'R': if self.pos0 % self.width != 0 or self.data[self.pos0-1] != '=': c += 1 if last_moved == 'L': if self.pos0 % self.width != self.width-1 or self.data[self.pos0+1] != '=': c += 1 return c def move(self, direction): if direction == 'U': self.swap(self.pos0,self.pos0-self.width) self.pos0 = self.pos0 - self.width elif direction == 'D': self.swap(self.pos0,self.pos0+self.width) self.pos0 = self.pos0 + self.width elif direction == 'L': self.swap(self.pos0,self.pos0-1) self.pos0 = self.pos0 - 1 elif direction == 'R': self.swap(self.pos0,self.pos0+1) self.pos0 = self.pos0 + 1 def move_string(self, mstr): for m in mstr: self.move(m) def reverse_move(self, direction): if direction == 'U': self.move('D') elif direction == 'D': self.move('U') elif direction == 'L': self.move('R') elif direction == 'R': self.move('L') def reverse_move_string(self, mstr): for m in mstr[::-1]: self.reverse_move(m) def find_pos0(self): return self.data.index('0') def swap(self, i, j): self.data[i], self.data[j] = self.data[j], self.data[i] def maze_score(self): """calculates sum of modified Manhattan distances""" cdef int manhattan_score = 0 cdef int i, manhattan_dist for i,c in enumerate(self.data): if c != '=' and c != '0': dest = self.valid[c] if dest<i: manhattan_dist = self.maze_score_table[dest][i] else: manhattan_dist = self.maze_score_table[i][dest] manhattan_score += manhattan_dist return manhattan_score def maze_score_init(self): table = [[1000]*(self.width * self.height) for l in [1000]*(self.width * self.height)] for i,c in enumerate(self.data): if c != '=': if i%self.width-1 >= 0 and self.data[i-1] != '=': table[i][i-1] = 1;table[i-1][i] = 1; if i%self.width+1 < self.width and self.data[i+1] != '=': table[i][i+1] = 1; table[i+1][i] = 1 if i-self.width-1 > 0 and self.data[i-self.width] != '=': table[i][i-self.width] = 1; table[i-self.width][i] = 1 if i+self.width < len(self.data) and self.data[i+self.width] != '=': table[i][i+self.width] = 1; table[i+self.width][i] = 1 search_path = [] for i in range(len(self.data)): table[i][i] = 0 for i in range(len(self.data)-1): for j in range(i+1,len(self.data)): if self.data[i] != '=' and self.data[j] != '=': search_path.append((i,j)) while len(search_path) > 0: s,g = search_path.pop(0) minimum_path = table[s][g] if not minimum_path < 1000: for m in range(len(self.data)): mp = table[s][m] + table[m][g] if mp < minimum_path: table[s][g] = mp table[g][s] = mp minimum_path = mp if not minimum_path < 1000: search_path.append((s,g)) #print "%d,%d not found" % (s,g) return table class SlidePuzzleSolver(object): """slidepuzzle solver""" def __init__(self,width,height,data,threashold=10,maxtime=10): self.puzzle = SlidePuzzle(width,height,data) self.candidates = [''] self.stats = {''.join(self.puzzle.data):1} self.backward_candidates = [''] self.backward_stats = {'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:width*height-1]+'0':''} self.threashold = threashold self.maxtime = maxtime def solve(self): best = 100 start = time.time() for rval in range(100): # start forward search for cand in self.candidates: if time.time() - start > self.maxtime: return '' self.puzzle.move_string(cand) last_moved = cand[-1] if len(cand) > 0 else '' for direction in ['U','D','L','R']: if self.puzzle.can_move(direction,last_moved): new_cand = cand + direction self.puzzle.move(direction) score = self.puzzle.calc_score() stat = ''.join(self.puzzle.data) if DEBUG: print self.puzzle.display(),'\n' if score == 0: return new_cand else: if self.stats.get(stat,0) == 0: self.stats[stat] = 1 if score < best: best = score if self.puzzle.next_pattern(direction) == 1: self.candidates.insert(0,new_cand) elif score < best + self.threashold + rval: self.candidates.append(new_cand) self.puzzle.reverse_move(direction) self.puzzle.reverse_move_string(cand) # end forward search return ''
solve.py
import sys from slidepuzzle import SlidePuzzleSolver from multiprocessing import Pool def answer (problem_t): problem_num, problem = problem_t prefix = "problem %d: (%s) " % (problem_num+1,problem) mylist = problem.split(',') width = int(mylist[0]) height = int(mylist[1]) data = mylist[2] solver = SlidePuzzleSolver(width, height, data,5,120) result = solver.solve() if len(result) == 0: sys.stderr.write(prefix + 'not found\n') else: sys.stderr.write(prefix + '!!! solved !!!\n') return result class Calculate(object): def run(self, problems): p = Pool(2) return p.map(answer, enumerate(problems)) if __name__ == '__main__': with open("slidepuzzle.txt") as f: lim = [int(i) for i in f.readline()[:-1].split()] Llim,Rlim,Ulim,Dlim = lim[0], lim[1], lim[2], lim[3] Total_boards = int(f.readline()[:-1]) problems = [l.rstrip() for l in f.readlines()] cl = Calculate() results = cl.run(problems) print 'solved: ', len([p for p in results if len(p) > 0])