えっ。Python での実装はもうあるじゃん…。まったくもって今更何を言いだすのか。
“There’s Only One Way To Do It” を掲げる Python にもかかわらず「その2」などとは。
とはいうものの、いかに Python といえども、やはりやり方をひとつに絞ることはできはしない。
比較的 Python らしい、ジェネレータを使用したやりかたは既に示されている。
そこで本記事では、もうひとつのやり方として元々の Haskell版 のクローンを Python で実装してみようと思う。
なお本記事では Python 3.2 を使用する。
何？ まだ Python 2 系を使ってる？ もう古いので早急に乗り換えを検討されるとよろしい。
Python で書いてみる
さて、目指すは Haskell 版のクローンである。同じく blocklist を定義しよう。
blocklist = {
1: {2: 3, 4: 7, 5: 9},
2: {5: 8},
3: {2: 1, 5: 7, 6: 9},
4: {5: 6},
5: {},
6: {5: 4},
7: {4: 1, 5: 3, 8: 9},
8: {5: 2},
9: {5: 1, 6: 3, 8: 7},
}こういった用途には Python では dict が担当してくれる。邪魔するボタンが key で、邪魔されるボタンが value だ。
Haskell ではリストを用いているために lookup には線形時間がかかるが、Python なら対数時間探索が期待できる。
(ただし対数時間は二分木での実装の場合。実際の内部実装はハッシュテーブルのようなので、定数時間かもしれない。)
もっとも今回の場合はたかだか 3 要素しかないので、オーバーヘッドにより Python の方が若干不利だと予想されるが、
要素数が増えるほど Python の方が有利になっていくはずだ。
その辺さておき、Python の interactive shell を起動してコード片をコピー＆ペーストしよう。
複数行あっても、余分な空行がなければ正しく認識してくれるので便利だ。
>>> blocklist[1]
{2: 3, 4: 7, 5: 9}
>>> blocklist[1][2]
3二回目は「今 1 のボタンに居るとき、2 のボタンが未選択なら、3 のボタンへは進めない」を意味する。
この添え字によるアクセスは構文がシンプルで大変良いのだが、
>>> blocklist[1][6]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 6key が見つからないとエラーになって面倒だ。そんな場合は get を用いる。第二引数には key が見つからなかった場合のデフォルト値を指定できる。
>>> blocklist.get(1, {}).get(6, 0)
0デフォルトを指定しなければ None になる。
さて、このことを未選択なボタン全てに対して調べていけば、邪魔されるボタンの一覧が手に入るのだった。
Haskell では map 関数を使用した。Python にも同等の map 関数があるが、ジェネレータ式が map の代わりをしてくれるのでそちらを使うことにしよう。
>>> list(blocklist.get(1, {}).get(i) for i in [2,3,4,5,6,7,8,9])
[3, None, 7, 9, None, None, None, None]これを未選択のボタンから「引け」ばいいのだが、そんなときは set の出番で、こういう用途に特化されたコンテナだ。
>>> set([1,2,3,4]) - set([2,3])
{1, 4}簡単だね。
>>> set([2,3,4,5,6,7,8,9]) - set(blocklist.get(1, {}).get(i) for i in [2,3,4,5,6,7,8,9])
{8, 2, 4, 5, 6}1 にいるとき、次にいけるボタンは 8, 2, 4, 5, 6 だ。なお見ての通り順序は保持されない。
というのも、set は集合演算に特化されていて、要素の個数や順序といった概念を管理しないからだ。
ま、今回は探索順序はどうでもいいので、そんなことは気にしない。気にする必要があれば、結果に sorted を掛けるといいだろう。
使いやすいように関数を定義しておこう。
def candidate(i, rem):
return rem - set(blocklist.get(i, {}).get(n) for n in rem)こんな関数定義でもコード片をコピー＆ペーストすれば問題なく認識してくれる。
定義を更新できたら動作を確認しよう。
>>> candidate(1, set([2,3,4,5,6,7,8,9]))
{8, 2, 4, 5, 6}
>>> candidate(1, set([2,3,4,6,7,8,9]))
{8, 9, 2, 4, 6}問題なさそうだ。あとはひたすらリストアップをすればよいのだった。
def nextList(i, sel, rem):
return sum(
(nextList(s, sel + [s], rem - set([s])) for s in candidate(i, rem)),
[sel] if 4 <= len(sel) else [])Haskell 版と全く同じだ。
第一引数が「今選択しているボタン」、第二引数が「今まで選択してきたボタン」、第三引数が「未選択のボタン」である。
今回は既に 4 ボタン以上選択済みの場合も考慮に入れてある。
Python の 3 項演算子は順序が独特だが、後置 if だと思えばよい。
sum 関数は、Haskell でいうところの concat 相当として使っている。
>>> sum([[1,2],[3,4]], [])
[1, 2, 3, 4]第二引数が「初期値」で、この部分に 4 ボタン以上選択済みだった場合の結果も入れ込んだ。
おかげで関数本体は 1 行だけである(横に長くなってしまったので折り返してはいるが)。
ところで Python の話をしながら突然 Haskell に戻るが、これを見せられれば当然、Haskell でも同等のことができることに気づく。
nextList :: Int -> [Int] -> [Int] -> [[Int]]
nextList n sel rem =
foldr (++) (if 4 <= length sel then [sel] else [])
[nextList s (sel ++ [s]) (rem \\ [s]) | s <- candidate n rem]実は終了条件としていた nextList _ sel [] = [sel] も不要である。
なぜならその場合も foldr の初期値に結果が入り、内包表記が空になることで同等の処理が達成されるからである。
話が逸れた。Python に戻ろう。まず nextList 関数の動作確認。
>>> for p in nextList(6, [1,2,3,4,5,6], set([7,8,9])): print(p)
...
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 8]
[1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 8, 9, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7, 9]
[1, 2, 3, 4, 5, 6, 9]
[1, 2, 3, 4, 5, 6, 9, 8]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]順序はバラバラだが、結果セットはあっている。だめなパターン […,7,9,8] および […,9,7,8] もちゃんと取り除かれている。
では全力で数え上げよう。
def allList():
return nextList(0, [], frozenset(range(1, 10)))コピー＆ペーストすればすぐに試せる。
>>> len(allList())
389112やったね。
コード全体
完成したコード全体は下記の通り。
#!/usr/bin/python3
blocklist = {
1: {2: 3, 4: 7, 5: 9},
2: {5: 8},
3: {2: 1, 5: 7, 6: 9},
4: {5: 6},
5: {},
6: {5: 4},
7: {4: 1, 5: 3, 8: 9},
8: {5: 2},
9: {5: 1, 6: 3, 8: 7},
}
def candidate(i, rem):
return rem - set(blocklist.get(i, {}).get(n) for n in rem)
def nextList(i, sel, rem):
return sum(
(nextList(s, sel + [s], rem - set([s])) for s in candidate(i, rem)),
[sel] if 4 <= len(sel) else [])
def allList():
return nextList(0, [], frozenset(range(1, 10)))
print(len(allList()))わずか 25 行。やるな、Python。
作った玩具で遊ぶ
さて、Haskell でやったのと同じように Python でも interactive shell で遊んでみることができる。
Haskell のようについ allList() を各場所に埋め込みたくなるが、
Python でそれをすると関数呼出し毎にリストの再構築を行うため、極めて効率が悪い。
従って、メモリは使用するにせよ、一回明示的に変数に代入すると良い。
>>> A = allList()準備完了。最初の 10 件を表示。
>>> for p in A[:10]: print(p)
...
[1, 8, 3, 2]
[1, 8, 3, 2, 9]
[1, 8, 3, 2, 9, 4]
[1, 8, 3, 2, 9, 4, 5]
[1, 8, 3, 2, 9, 4, 5, 6]
[1, 8, 3, 2, 9, 4, 5, 6, 7]
[1, 8, 3, 2, 9, 4, 5, 7]
[1, 8, 3, 2, 9, 4, 5, 7, 6]
[1, 8, 3, 2, 9, 4, 7]
[1, 8, 3, 2, 9, 4, 7, 5]順序がバラバラなのは、先に言及した通り、次へ遷移する要素を選択するために set を使っているためだ。
続いて、開始ボタン位置によるパターン数を数えてみよう。
>>> len(filter(lambda x: x[0] == 1, A))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: object of type 'filter' has no len()…おっと、ジェネレータに len は適用できない。ジェネレータの個数を数えるには下記のようなイディオムがあるらしい。
>>> sum(1 for _ in A)
389112なるほど。では改めて。
>>> sum(1 for x in A if x[0] == 1)
38042
>>> sum(1 for x in A if x[0] == 2)
43176
>>> sum(1 for x in A if x[0] == 3)
38042
>>> sum(1 for x in A if x[0] == 4)
43176
>>> sum(1 for x in A if x[0] == 5)
64240当然 Haskell 版と同じ結果が得られる。
同じく終わりも調べよう。
>>> for p in ((x, sum(1 for l in A if l[-1] == x)) for x in range(1,10)):
... print(p)
...
(1, 54374)
(2, 37144)
(3, 54374)
(4, 37144)
(5, 23040)
(6, 37144)
(7, 54374)
(8, 37144)
(9, 54374)同様の結果が得られているようだ。
開始と終了で数えるのも同じようにできる。
>>> max((((x,y), sum(1 for l in A if l[0] == x and l[-1] == y))
... for x in range(1,10) for y in range(1,10) if x != y), key=lambda a: a[1])
((5, 1), 9620)Haskell 版とは違い角のボタンが 9 ではなく 1 になっているが、いずれにせよパターン数は同じだ。
>>> min((((x,y), sum(1 for l in A if l[0] == x and l[-1] == y))
... for x in range(1,10) for y in range(1,10) if x != y), key=lambda a: a[1])
((1, 5), 2688)こちらも同様。角から初めて中央で終わるのは 2688 パターンだ。
ボタン数でパターンを数える。
>>> for p in ((x, sum(1 for l in A if len(l) == x)) for x in range(4,10)):
... print(p)
...
(4, 1624)
(5, 7152)
(6, 26016)
(7, 72912)
(8, 140704)
(9, 140704)そして最後、乱択。
>>> from random import randint
>>> A[randint(0, len(A) - 1)]
[5, 9, 2, 3, 1, 8, 4, 6, 7]もちろん実行ごとに違うリストが得られる。乱数生成は IO モナドに縛られない Python の方が手間が少ないのは違いない。
＃人気の記事
＃タグ
