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

月別: 2011年9月

移転しました

水嶋.jpのドメイン上でブログを書き始めめたのが去年の10月のこと。
日本語ドメイン上にブログを設置したのは初めてのことだったので、ちゃんと動いたときは感動しました。
それから今日まで、よく書く時期や、1ヶ月ほどほったらかしたりしてた時期もあったりしましたが、なんとか約11ヶ月間運営してきました。

日本語ドメインを利用しているサイトはあまり多くないので、紹介したときに目立つことは目立つのですが、やはり不便なことが多いのも事実…。
URLを貼っても自動リンクにならないこともよくあります。
「Gmailからメール送れない」と文句を言われたこともありました。

そんなもんだから、やっぱりなんだかんだでローマ字のほうが便利だなぁ…と思ったりして。

で。

今回、ちょうどサーバを移転する計画があったので、それに合わせて新しく取ったドメインにブログのアドレスも変更することにしました。

新しいドメインは今ご覧の mzsm.me です。
今までよりは格段に入力しやすくなったかと思います。
どうぞよろしくお願いします。

もちろん、水嶋.jpは苗字という自分のアイデンティティを表すドメインなので、これからも維持し続けていくつもりです。
とりあえず、水嶋.jpドメインのアドレスへのアクセスは、全部mzsm.meドメインの同一ページにリダイレクトするように設定していますので、リンク切れになることは多分ない…はずです。


コメントする

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


コメントする

DevQuizの解答(ソースコード)晒し GoogleAppsScript編 #gdd11jp

いろいろ拙いところはありますがせっかくなので晒します
Google Docsで見る場合はこちら

JSONのURLは人によって違うみたいですが、僕の場合のものです

function main() {
var jsonUrl = “http://gdd-2011-quiz-japan.appspot.com/apps_script/data?param=-2907654602213579550”;

//initialize
var ss = SpreadsheetApp.getActiveSpreadsheet();
var as = ss.getActiveSheet();
var oldSheets = ss.getSheets();
for(i=0;i


コメントする