カテゴリー: 技術メモ

GoogleAppsScriptに続いてスライドパズルのソースコードも晒します
CやJavaで挑戦する人が多かったようですが、僕はPythonで挑戦しました

ソースコード中にも書いているのですが、こちらのページのサンプルコードを大いに流用しており、それに独自に改良を加えて完成させました

# -*- coding: utf-8 -*-
# このプログラムは次のサイトを参考にし、サンプルコードを一部利用しました
# http://www.geocities.jp/m_hiroi/light/

import sys
import string

LETTERS = (string.digits + string.ascii_uppercase)[1:]

#
# pqueue.py : 優先度つき待ち行列
#
# Copyright (C) 2006 Makoto Hiroi
#

# 葉の方向へ
def _downheap(buff, n):
size = len(buff)
while True:
c = 2 * n + 1
if c >= size: break
if c + 1 < size: if buff[c] > buff: c += 1
if buff[n] <= buff[c]: break temp = buff[n] buff[n] = buff[c] buff[c] = temp n = c # 根の方向へ def _upheap(buff, n): while True: p = (n - 1) / 2 if p < 0 or buff[p] <= buff[n]: break temp = buff[n] buff[n] = buff[p] buff[p] = temp n = p class PQueue: def __init__(self, buff = []): self.buff = buff[:] # コピー for n in xrange(len(self.buff) / 2 - 1, -1, -1): _downheap(self.buff, n) # データの追加 def push(self, data): self.buff.append(data) _upheap(self.buff, len(self.buff) - 1) # 最小値を取り出す def pop(self): if len(self.buff) == 0: raise IndexError value = self.buff[0] last = self.buff.pop() if len(self.buff) > 0:
# ヒープの再構築
self.buff[0] = last
_downheap(self.buff, 0)
return value

# 最小値を求める
def peek(self):
if len(self.buff) == 0: raise IndexError
return self.buff[0]

# 空か
def isEmpty(self): return len(self.buff) == 0

def print_answer(x, list):
if x is not None:
print_answer(x.prev, list)
if x.moveto:
list.append(x.moveto)
return list

def print_answer_goal(x, list):
while x is not None:
if x.moveto:
list.append(reverse_distance(x.moveto))
x = x.prev
return list

def reverse_distance(moveto):
return {
‘U’:’D’,
‘L’:’R’,
‘R’:’L’,
‘D’:’U’
}[moveto]

class Problem:
x = 0
y = 0
start = ”
end = ”
result = ”
cost = {}
adjacent = []

def __init__(self, line):
x, y, self.start = line.split(‘,’)
self.x = int(x)
self.y = int(y)

end = ”
for ltr in LETTERS[:len(self.start)-1]:
end += ltr if ltr in self.start else ‘=’
end += ‘0’
self.end = end

self.make_adjacent()

def make_adjacent(self):
self.adjacent = []
for i in xrange(len(self.end)):
row = {}
if i >= self.x and self.end[i-self.x] != ‘=’:
row[‘U’] = i-self.x
if i % self.x and self.end[i-1] != ‘=’:
row[‘L’] = i-1
if (i+1) % self.x and self.end[i+1] != ‘=’:
row[‘R’] = i+1
if i < len(self.end)-self.x and self.end[i+self.x] != '=': row['D'] = i+self.x self.adjacent.append(row) def make_distance_table(self, board): size = len(board) table = [[0] * size for _ in xrange(size)] for i in xrange(size): ltr = board[i] if ltr == '=' or ltr == '0': continue p = LETTERS.index(ltr) x1 = i / self.x y1 = i % self.x for j in xrange(size): if board[j] == '=': table[p][j] = 99 else: x2 = j / self.x y2 = j % self.x table[p][j] += max(x1 - x2, x2 - x1) table[p][j] += max(y1 - y2, y2 - y1) return table def solve(self, limit): global start_distance, goal_distance q = PQueue() table ={} # スタートの登録 start_distance = self.make_distance_table(self.end) a = State(self.start, self.start.index('0'), None, 0, 0) q.push(a) table[self.start] = a # ゴールの登録 goal_distance = self.make_distance_table(self.start) a = State(self.end, self.end.index('0'), None, 0, 1) q.push(a) table[self.end] = a cnt = 0 while not q.isEmpty(): if cnt > limit:
return
a = q.pop()
if a.kind == 1: continue # 廃棄オブジェクト
for moveto, x in self.adjacent[a.space].iteritems():
b = a.board[:]
b = b[:a.space] + b[x] + b[a.space+1:]
b = b[:x] + ‘0’ + b[x+1:]
key = b
if key in table:
# 同一局面がある
c = table[key]
if a.dir != c.dir:
# 発見
list = []
if a.dir == 0:
print_answer(a, list)
list.append(moveto)
print_answer_goal(c, list)
else:
print_answer(c, list)
list.append(reverse_distance(moveto))
print_answer_goal(a, list)

self.result = ”.join(list)
q = None
table = None
return
# 距離は同じだから手数を比較すればよい
if c.move > a.move + 1:
# 更新する
if c.kind == 0:
c.kind = 1
c = State(b, x, a, a.move + 1, a.dir, moveto)
table[key] = c
else:
c.prev = a
c.cost = c.cost – c.move + a.move + 1
c.move = a.move + 1
c.kind = 0
# ヒープに追加
q.push(c)
else:
c = State(b, x, a, a.move + 1, a.dir, moveto)
q.push(c)
table[key] = c

cnt += 1
# a の子ノードは展開済み
a.kind = 1
else:
print(u’探索失敗’)

#検算
def verify(self):
board = self.start
for x in self.result:
try:
zero = board.index(‘0’)
idx = self.adjacent[zero][x]

board = board[:zero] + board[idx] + board[zero+1:]
board = board[:idx] + ‘0’ + board[idx+1:]
except:
return False
else:
if board == self.end:
return True
return False

def count_cost(self):
self.cost = {
‘U’: self.result.count(‘U’),
‘L’: self.result.count(‘L’),
‘R’: self.result.count(‘R’),
‘D’: self.result.count(‘D’)
}

def get_distance(board, distance):
v = 0
for x in xrange(len(board)):
p = board[x]
if p in [‘=’, ‘0’]: continue
v += distance[LETTERS.index(p)][x]
return v

class State:
def __init__(self, board, space, prev, move, dir, moveto = None, kind = 0):
self.board = board
self.space = space
self.prev = prev
self.move = move
self.dir = dir
self.moveto = moveto
self.kind = kind
if dir == 0:
dt = start_distance
else:
dt = goal_distance
if prev is None:
self.cost = get_distance(board, dt)
else:
ltr = board[prev.space]
p = LETTERS.index(ltr)
self.cost = prev.cost + 1 – dt[p][space] + dt[p][prev.space]

def __cmp__(self, other):
return self.cost – other.cost

def main(qfile, limit=1000000, skip = ”, *argv):
limit = limit if isinstance(limit, int) else int(limit) if limit.isdigit() else 1000000
skip = [int(i) if i.isdigit() else None for i in skip.split(‘,’)]

f = open(qfile)

#1行目 手数取得
line = f.readline().strip()
limits = dict(zip([‘L’,’R’,’U’,’D’], [int(i) for i in line.split(‘ ‘)]))
used = {‘L’:0, ‘R’:0, ‘U’:0, ‘D’:0}
#print(limits)

#2行目 問題数取得
lines = int(f.readline().strip())
#回答ファイルを開く
try:
result = open( ‘result.txt’, ‘r+’ )
resultList = [x.rstrip() for x in result.readlines()]
#print resultList
if len(resultList) != lines:
resultList.extend( [”] * (lines – len(resultList)) )
result.close()
except:
resultList = [”] * lines

line = f.readline().rstrip()
i = 0
cleared = 0
while line:
problem = Problem(line)

print (‘Q.%s:’ % (i+1))
problem.result = resultList[i].rstrip()
if i+1 in skip:
print (‘… Skipped.’)
elif len(problem.result) and problem.verify():
print (‘… Cleared already.’)

for letter in [‘L’, ‘R’, ‘U’, ‘D’]:
used[letter] += problem.result.count(letter)

cleared += 1
else:
problem.solve(limit)
if problem.verify():
resultList[i] = problem.result
print (‘… Cleared.’)
cleared += 1
else:
print (‘… Error.’)

result = open( ‘result.txt’, ‘w’ )
result.write(‘\n’.join(resultList))
result.close()

line = f.readline().rstrip()
i += 1

f.close()
print(‘Cleared: %s / %s’ % (cleared, lines))
for letter in [‘L’, ‘R’, ‘U’, ‘D’]:
print(‘%s: %s / %s (%f%%)’ % (letter, used[letter], limits[letter], (1.0*used[letter]/limits[letter])*100 ))

if __name__ == ‘__main__’:
if(len(sys.argv) < 2): print u'引数: 問題ファイル名 探索回数 スキップする問題番号' quit() main(*sys.argv[1:]) [/python] コマンドラインで

python2.7 slidePuzzle.py problem.txt 3000000 844

と起動すると、
problem.txtに書かれた問題を読み込み、
1問あたり300万回探索した時点で解答が見つからなければあきらめて次の問題にすすみ、
844問目はスキップし、
結果はresult.txt(決め打ち)に出力されます
ついでに、result.txtにすでに解答が書かれている問題は検算して合っていればスキップします

計算速度はそんなに早くなくて、先代MacBookAirで1週間計算させ続けて解答できたのは4000問でした
ていうかちょうど4000問解けたところでやめました

コメントする