Google Treasure Hunt 2008[2]
2問目も正解した．
特定条件を満たすパスのファイルを読んで特定行の数字を使って計算するという内容．
os.walk()してフィルタリングするだけなので結構楽だった．
TopCoderのPlugin設定
TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed
を参考に設定してるのだけれどなんかC++のファイルにJavaのコードが生成されるよ!
デフォルトの言語設定とかがどこかにあるのかな?
Google Treasure Hunt 2008
Official Google Australia Blog: Google Treasure Hunt
面白そうだったのでやりはじめました。
現在は1問目を正解して、2問目の回答を提出した後の結果待ち状態。
1問目はRobot Puzzle。長方形のグリッド上のロボットを目的地まで移動させる経路は何通りあるかという問題。
絵に目を引かれるかも知れないけど、問題自体を分解して考えればシンプルなものに帰着する。
Hunting -> Hunt
OS XでPython-3.0a5をビルド
そのままだとX-MAC-JAPANESEが無いと言われてモジュールのバイトコンパイル中(?)にエラーで止まってしまう。
X-MAC-JAPANESEはファイル名などに使うためのApple独自のUTF-8拡張だそうで、Pythonはこれを正しく取り扱えない模様。
http://weblog.metareal.org/2007/09/09/fixup-python-locale-problems-by-apple-darwin-patch/
これを参考にしてAppleから10.5.2版のパッチを落として当ててみたらビルドできた。
http://www.opensource.apple.com/darwinsource/10.5.2/python-30.1.2/
python-30.x.xと23.x.x、16.x.xという数種類のパッチ群があるが、それぞれ3.0、2.3、1.6ベースのパッチだと適当に予想。
python-30.x.xを落としてきたらうまくいったようだ。
以下パッチ。Python-3.0a5のトップフォルダに
patch -p1
して下さい。
diff -Naru Python-3.0a5.orig/Lib/locale.py Python-3.0a5/Lib/locale.py
--- Python-3.0a5.orig/Lib/locale.py 2008-05-13 07:51:03.000000000 +0900
+++ Python-3.0a5/Lib/locale.py 2008-05-13 07:51:26.000000000 +0900
@@ -494,7 +494,7 @@
"""
_setlocale(category, _build_localename(getdefaultlocale()))
-if sys.platform in ('win32', 'darwin', 'mac'):
+if sys.platform in ('win32', 'mac'):
# On Win32, this will return the ANSI code page
# On the Mac, it should return the system encoding;
# it might return "ascii" instead
diff -Naru Python-3.0a5.orig/Modules/_localemodule.c Python-3.0a5/Modules/_localemodule.c
--- Python-3.0a5.orig/Modules/_localemodule.c 2008-05-13 07:51:10.000000000 +0900
+++ Python-3.0a5/Modules/_localemodule.c 2008-05-13 07:51:26.000000000 +0900
@@ -32,7 +32,7 @@
#include <wchar.h>
#endif
-#if defined(__APPLE__)
+#if 0
#include <CoreFoundation/CoreFoundation.h>
#endif
@@ -353,7 +353,7 @@
}
#endif
-#if defined(__APPLE__)
+#if 0
/*
** Find out what the current script is.
** Donated by Fredrik Lundh.
@@ -631,7 +631,7 @@
{"strxfrm", (PyCFunction) PyLocale_strxfrm,
METH_VARARGS, strxfrm__doc__},
#endif
-#if defined(MS_WINDOWS) || defined(__APPLE__)
+#if defined(MS_WINDOWS) || 0
{"_getdefaultlocale", (PyCFunction) PyLocale_getdefaultlocale, METH_NOARGS},
#endif
#ifdef HAVE_LANGINFO_H
iflatten
先日何故いきなりCPS変換（で言葉はあっているのだろうか）をやり始めたかというと，
http://aspn.activestate.com/ASPN/Mail/Message/python-tutor/2302231
をみてコールスタックを消費しないflatten関数の動きを理解したかったから．flatten関数はネストしたリスト（ツリー構造）を単一のツリーにする関数．Schemeなんかでは再帰で書けるけど，末尾再帰最適化の無い言語でやるとちょっと大きなツリーでもスタックオーバーフローを起こしてしまう．それをトランポリンスタイルにして避けようというのが上記URLの話．
CPS変換はSchemeのコンパイラ書く時なんかに使えるようなので，成り行きとはいえ勉強して得した気分．
ところで普通のリストに変換するのもいいけど，Pythonならやっぱりジェネレータにして1パスでツリーを走査してしまいたいと思いますよね．
ということで書いてみた．はじめトランポリンで書こうと思ったが途中でツリーの走査がアセンブラ（というかマシン語？）の実行とほとんど同じであることに気づき，リストのイテレータを命令ポインタとして考えて，コールスタックに相当するものを用意すればループで普通に書けるのではないかと思い至った．
つまり，
リスト == ルーチン
リストの中のリスト == サブルーチン
と考えると以下のような手順で処理できる．
1. リスト走査中にリストに出会ったら，今のイテレータをスタックにプッシュして新しいリストを走査する．
2. リスト走査中にリスト以外に出会ったらyieldする．
3. リストの走査が終わったらスタックから元のイテレータをポップして残りを走査する．
4. あるリストの走査終了時にスタックの中にリストが無いなら終わり．
以下が結果のiflatten関数．この前に2バージョン程あったが現段階ではこれが一番綺麗に思う．
def iflatten(tree): it = iter(tree) stack = [] while True: try: e = it.next() if isinstance(e, (list, tuple)): stack.append(it) it = iter(e) else: yield e except StopIteration: if stack: it = stack.pop() else: break
上記のURLから頂いてきたテストコードもちゃんと通る．
if __name__ == '__main__': import sys def make_evil_list(n): result = [] for i in xrange(n): result = [[result], i] return result evil_nested_list = make_evil_list(sys.getrecursionlimit()) assert range(sys.getrecursionlimit()) == [i for i in iflatten(evil_nested_list)]
昔から思っているのだが，StopIteration例外で反復を止めるのって微妙な仕様じゃない？
ジェネレータの実装上の都合のような気がしているが該当部分を詳しく調べていないのでよく分からない．
ループが止まるのが例外的な現象だと思えってことなのか．
TrampolineとCPSとPython
TrampolineとCPSについて調べたことの一応のメモ．
理論的な側面はともかくやりかたはなんとなく分かってきた気がする．
http://en.wikipedia.org/wiki/Continuation-passing_style
を参考にして書いてみた．
CPS
Direct style
import operator as op def pyth(x, y): return pow(op.add(op.mul(x, x), op.mul(y, y)), 0.5) pyth(3, 4) # => 5.0
Continuation passing style
def pyth_cps(x, y, k): def mul_cps(x, y, k): return k(x * y) def add_cps(x, y, k): return k(x + y) def pow_cps(x, y, k): return k(pow(x, y)) return mul_cps(x, x, lambda x2: mul_cps(y, y, lambda y2: add_cps(x2, y2, lambda x2py2: pow_cps(x2py2, 0.5, k)))) pyth_cps(3, 4, lambda x: x) # => 5.0
もうちょっとPythonらしく（したつもり）．
継続渡し版演算子関数を展開してしまっている．
美しい...か？
def pyth_cps2(x, y, k): def k0(x2): def k1(y2): def k2(x2py2): return k(x2py2 ** 0.5) return k2(x2 + y2) return k1(y * y) return k0(x * x) pyth_cps2(3, 4, lambda x: x) # => 5.0
Trampoline
これでいいのか？
def pyth_trampoline(x, y, k): def k0(x2): def k1(y2): def k2(x2py2): return lambda: k(x2py2 ** 0.5) return lambda: k2(x2 + y2) return lambda: k1(y * y) return lambda: k0(x * x) pyth_trampoline(3, 4, lambda x: x)()()()() # => 5.0
次は再帰関数でやる．
def fact(n): if n: return n * fact(n - 1) else: return 1
def fact_cps(n, k): mul_cps = lambda x, y, k: k(x * y) sub_cps = lambda x, y ,k: k(x - y) def k0(b): if b: def k1(m): def k2(l): return mul_cps(n * l, k) return fact_cps(m, k2) return sub_cps(n, 1, k1) else: return k(1) return k0(n)
def fact_trampoline(n, k): mul_trampoline = lambda x, y, k: lambda: k(x * y) sub_trampoline = lambda x, y ,k: lambda: k(x - y) def k0(b): if b: def k1(m): def k2(l): return mul_trampoline(n, l, k) return fact_trampoline(m, k2) return sub_trampoline(n, 1, k1) else: return lambda: k(1) return lambda: k0(n) def bounce(t): i = 1 while callable(t): print 'loop:', i i += 1 t = t() return t >>> t = fact_trampoline(5, lambda x: x) >>> bounce(t) loop: 1 loop: 2 loop: 3 loop: 4 loop: 5 loop: 6 loop: 7 loop: 8 loop: 9 loop: 10 loop: 11 loop: 12 loop: 13 loop: 14 loop: 15 loop: 16 loop: 17 120
Google App Engineでwikiっぽいのを作りました．
今更どうということもない代物ですが，CodeReposのコミット権を頂いたので置いておきました．
http://coderepos.org/share/browser/lang/python/gae_wiki
認証とかは簡単にできそうだけど，特に意味がなさそうなので省略．
List+CRUDな操作ができます．URL設計その他諸々は全く自信なし．
一応WikiName対応で自動的にリンクが張られます．中ではstring.replace()しまくりだったりして色々不味い仕様なのだが気にしないことにしている．
