TIM Labs

Python で Android の指リストパターンを数え上げる

| コメント(0) | トラックバック(0)
私は iPhone ユーザーなので Android のスクリーンロックはほとんど使ったことがないのだけど、
偶然このブログで Haskell で Android の指リストパターンを数え上げる という記事を読んで、
Python で同様のコードを書いてみようと思いつきました。
ブログのネタが無いので人の褌で相撲をとってやろう、ということです。
Haskell 版では lookup 関数を使ってブロックリストの参照をしているのですが、
Python では該当する関数がないため遷移元と遷移先の数字の組(tuple)をキーにして
ブロックリストを表現することにしました。

また、Haskell での遅延評価を実現するために、
Python では yield 文を使ったジェネレータを生成することにしました。


上記を踏まえて Python で作りなおしたものは以下のようになります。

#!/usr/bin/python

BLOCKERS = {(1, 3): 2, (1, 7): 4, (1, 9): 5,
            (2, 8): 5,
            (3, 1): 2, (3, 7): 5, (3, 9): 6,
            (4, 6): 5,
            (6, 4): 5,
            (7, 1): 4, (7, 3): 5, (7, 9): 8,
            (8, 2): 5,
            (9, 1): 5, (9, 3): 6, (9, 7): 8}


def fingerlist(selected = ()):
    if len(selected) >= 4:
        yield selected

    for i in set(range(1, 10)) - set(selected):
        if len(selected) > 0:
            transit = (selected[-1], i)
            if transit in BLOCKERS and BLOCKERS[transit] not in selected:
                continue

        for p in fingerlist(selected + (i,)):
            yield p


for p in fingerlist():
    print p


なお、Python 3.3 では yield from 文が導入され、サブジェネレータが扱い易くなるため、
再帰呼び出しをしている部分がもう少しシンプルになるようです。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/266

コメントする

このブログ記事について

このページは、tk0miyaが2011年10月 7日 14:40に書いたブログ記事です。

ひとつ前のブログ記事は「Haskell で Android の指リストパターンを数え上げる」です。

次のブログ記事は「遅延評価とメモ化は別物(LINQ編)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。