コンテンツにスキップするには Enter キーを押してください

タグ: Python

DevQuizの解答(ソースコード)晒し スライドパズル編 #gdd11jp

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問解けたところでやめました


コメントする

UbuntuでiBusが立ち上がらなくなったので試行錯誤して直してみた

Google日本語入力って快適ですよね。
公式にはWindows版しかありませんが、それのオープンソース版がmozc(もずく)という名前で公開されているので、Linuxでもあの快適な日本語入力環境を享受することができます。
とはいえ、ほとんどの人は一生入力しないような固有名詞まで入ったあの変態辞書は含まれてないのですが、「きょう」や「いま」なんかはちゃんと使えます。

mozcはあくまでも読みを漢字に変換する部分を担当するソフトなのでキーボードから文字の入力を受け付ける別のソフトと組み合わせて使うことになります。これには例えばiBus、SCIM、uimといったものがあります。

で、いろんな勉強会やらイベントやらに連れていっている、僕のちっちゃくてかわいいUbuntuネットブックにもmozcを入れて使っているのですが、今回はその相棒のiBusが立ち上がらなくなってしまったというお話。


コメントする

AppEngineのhashlibで日本語を含む文字列のハッシュ値を取得しようとするとエラーになる件

ファイルやテキストの改竄を検知するためにMD5やSHA256などのハッシュ関数を利用してハッシュ値を求めるということはよくあると思うんですが。
Google App Engine / Pythonでこれをやろうとして変なエラーに遭遇してしまい、パニクったので備忘録として書いておきます。

ものすごく要約するとこんなコードを書いていました。

import hashlib

text = u'ほげほげ'
hash = hashlib.sha256(text).hexdigest()

実際はtextには外部から取得した、これよりもっとながーーい文字列が入っていて、その文字列のハッシュ値を求める、というものでした。

localhostのSDKではこれでちゃんと動いてたんですよ。

ところがプロダクション環境にデプロイしてみると、動かない。

ログを見ると、
UnicodeEncodeError: 'ascii' codec can't encode characters in position 18-40: ordinal not in range(128)
と出ていたので、どうやらASCII範囲外の文字をASCII文字列にエンコードしようとしてエラーになっている、ということはわかりました。

が、原因はわかったものの解決法がわからない。

エラーメッセージでググってみると、どうやら外人さんも同じ問題で悩んでいたらしいということがわかり、そこに解決法が載っていました。

というわけで修正したコードがこちらです。

import hashlib

text = u'ほげほげ'
hash = hashlib.sha256(text.encode('utf-8')).hexdigest()

はい、textを明示的に「utf-8」と指定してencodeしてやりました。

これがPythonのややこしいところなんですが、「Unicode型文字列」と「(UTF-8エンコードされた)str型文字列」は全くの別物なんですよね…。

とにもかくにも、これでプロダクション環境でもちゃんとハッシュ値を取得することができるようになりました。


コメントする

Python・JavaScript・PHPでのループ処理のやり方まとめ

最近、仕事でもプライベートでもよくPythonを使っているのですが、ループのやり方が今まで使ってきたJavaScriptやPHPと少し使い勝手が違っていて迷うことがよくあるので防備録としてまとめておきます。
比較対照として、JavaScriptとPHPで同じことをする方法もまとめてみました。
こうやって比較してみるとそれぞれ特徴があって面白かったですよ。


コメントする