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


2011年 10月 07日

私は 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 文が導入され、サブジェネレータが扱い易くなるため、
再帰呼び出しをしている部分がもう少しシンプルになるようです。