Android 機にはロック機構として暗証番号やパスワードの他に、指リストというヤツがある。
テンキー状に9個のボタンが配置され、そのボタンを一筆書きでなぞって繋いでいく。
最低 4 個のボタンを繋ぎ(最大はもちろん 9 個)、そのパターンによって認証するシステムだ。
パターンというのは人間にとってそれなりに覚えやすくもあり、
Android 機を使っている人は端末ロックを指リストにしている人も多いだろう。
指紋跡でパターンがバレる、なんて話もあるにはあるが…、
それはさておき、純粋にパターン数として、どのくらいあるのだろうか？
9 個のボタンの単純な組み合わせであれば、Σ(i=4 to 9) P(9,i) = 985,824 通りで、約 19.9 bit。
しかし指リストは選択順によって選択できないパターンが存在する。
例えば、指リストのボタン位置をテンキーに見立てたとして、 4 -> 6 -> 5 の順では選択できない。
なぜなら、4 -> 6 で一筆書きでなぞろうとしたら、 5 の位置を通らざるを得ないからだ。
従って、上記パターンは数えすぎであり、もっと少ないはずである。
別の方法で数え上げた方が良さそうだ。
選択したボタンから、次に移ることができるボタン数を調べていくのがいいだろうか。
さすがにこれだけの数を人間が数え上げるのは無茶があるので、計算機にやらせよう。
まあこんなものは Perl でも Python でも Ruby でも Javascript でも、
いっそのこと C でも C++ でもいいのだが、こんなことをするのにうってつけの言語がある。
Haskell だ。
本記事では GHC を使う。実行結果も載せておくことにはするが、
ぜひ手元に GHC をインストールして実際に試してみて欲しい。
Haskell で書いてみる
方針は先ほど出した、「今選択しているボタンから、次に移ることができるボタンを調べる」でいこう。
まず、現在選択しているボタンから、次に移ることができなくなるパターンを列挙しておく。
import Data.List
import Data.Maybe
blocklist :: Int -> [(Int, Int)]
blocklist 1 = [(2,3),(4,7),(5,9)]
blocklist 2 = [(5,8)]
blocklist 3 = [(2,1),(5,7),(6,9)]
blocklist 4 = [(5,6)]
blocklist 5 = []
blocklist 6 = [(5,4)]
blocklist 7 = [(4,1),(5,3),(8,9)]
blocklist 8 = [(5,2)]
blocklist 9 = [(5,1),(6,3),(8,7)]
blocklist _ = []先頭の import 宣言は、それぞれのモジュールに定義されている関数を後ほど使うため、先に書いてある。
本記事は blog なので、お料理番組よろしく「準備済み」なノリだが、実際にはもちろん必要になる度に書き足せばよい。
blocklist 関数は、現在のボタンを引数に受け取り、移行できなくなる原因のボタンと、
移行できなくなる先のボタンをタプルにまとめたリストを返す。
例えば、今 1 のボタンにいるとしよう。その場合、まだ 2 のボタンが未選択であれば、直接 3 のボタンに進むことはできない。
そのことを (2,3) として記述してある。左が「邪魔をするボタン」右が「邪魔されて進めなくなるボタン」だ。
ひとつ注意したいのは、「邪魔をするボタン」が既に選択済みであれば、そのボタンはもう邪魔しない、ということだ。従って、2 -> 1 -> 3 のようなフローは選択可能である。
さて、先のコードを fingerlist.hs とでも名前をつけて保存して、ghci に取り込もう。
Prelude> :load fingerlist.hs
[1 of 1] Compiling Main ( fingerlist.hs, interpreted )
Ok, modules loaded: Main.
*Main> blocklist 3
[(2,1),(5,7),(6,9)]こうやって手軽に確認できるのが Haskell の良いところだ。
では、次は「現在選択しているボタン」と、「まだ未選択のボタンの一覧」から、「次に選択可能なボタン一覧」を取得する関数を作ろうと思う。
が、その前に、邪魔されて進めないボタン一覧を確認しておこう。
今 1 を選んだとして、残っているのは 2 から 9 まで全てとする。
1 を選んでいるとき、2 のボタンが生きていたら、3 は選択できない。
そのことを、lookup 関数で調べよう。
lookup は (key, value) のペアのリストに対して key を指定して、その key が見つかったら Just を、見つからなかったら Nothing を返す関数だ。Just のときは、実際に見つかった value がその後ろにくっついている。
*Main> lookup 2 (blocklist 1)
Just 3
*Main> lookup 6 (blocklist 1)
Nothingふむ。1 を選択しているとき、2 のボタンは 3 へいくのを邪魔するが、6 のボタンはどこへいくのも邪魔しない、と言っている。
このことを、未選択なボタン全てに対して調べていけば、邪魔されるボタンの一覧が手に入るはずだ。
そんなときは map を使う。最近の言語はどれもこれを備えているので、関数型言語を知らなくても使ったことがあるだろう。
ある関数を、与えられた一覧全てに適用していく関数だ。
*Main> map (`lookup` blocklist 1) [2..9]
[Just 3,Nothing,Just 7,Just 9,Nothing,Nothing,Nothing,Nothing](`lookup` blocklist 1) という表記は見慣れないかもしれない。
まず、Haskell は全ての関数はバッククオートで括ることで「演算子」として使用できる。
*Main> 2 `lookup` blocklist 1
Just 3
*Main> 6 `lookup` blocklist 1
Nothing単純に書き方の順序が変わっただけだが、この場合はこっちの方が読みやすいかもしれない。
そして、(`lookup` blocklist 1) は、与えられるべき左側の引数を与えていない、いわば「穴あき」の状態だ。
しかし Haskell ではこれも関数なのである。というかぶっちゃけ Haskell ではおおむねなんでもかんでも全部関数である。
そして map 関数は、この「穴あき」の関数に、後ろのリストから値をひつずつ取り出してその値を穴に埋め込み、その結果の一覧を返した、というわけだ。
この「関数を関数のまま持ち歩く」感覚はなかなか楽しい。
しかしこの Just やら Nothing やら、このあたりのものが少々邪魔だ。
欲しいのは邪魔されて進めないボタンである [3,7,9] が欲しいのであって、Just だかなんだかではない。
そんなときは、map の代わりに Data.Maybe で定義されている mapMaybe を使おう。
mapMaybe 関数は、map 結果が Just になるものだけを集めてくれる。
*Main> mapMaybe (`lookup` blocklist 1) [2..9]
[3,7,9]望みのものが手に入った。
念のため、邪魔するボタンが選択済みの場合も確認しておこう。今、 5 -> 1 と進んできて、[2,3,4,6,7,8,9] が未選択だとする。
*Main> mapMaybe (`lookup` blocklist 1) [2,3,4,6,7,8,9]
[3,7]5 のボタンが選択済みなので、9 には進めるようになった。
さて、話を戻そう。欲しかったのは、「次に進めるボタンの一覧」だった。
これは単純に、未選択のボタンから進めないボタンを取り除けばいい。
それは Data.List モジュールで定義されている (\\) 演算子が行ってくれる。
*Main> [1,2,3,4] \\ [2,3]
[1,4]見ての通りだ。では先ほどの mapMaybe と組み合わせてみよう。
*Main> [2..9] \\ mapMaybe (`lookup` blocklist 1) [2..9]
[2,4,5,6,8]
*Main> [2,3,4,6,7,8,9] \\ mapMaybe (`lookup` blocklist 1) [2,3,4,6,7,8,9]
[2,4,6,8,9]上の例は 1 にいて 2 から 9 が未選択のとき、次にいけるのは 2,4,5,6,8 だと言っている。あってるね？
下の例は、 5 -> 1 ときたとき、次にいけるのは 2,4,6,8,9 だと言っている。これも問題なさそうだ。
では関数を定義しよう。
candidate :: Int -> [Int] -> [Int]
candidate i rem = rem \\ mapMaybe (`lookup` blocklist i) remファイルを保存して、ghci で :reload と打てば、読み込みなおしてくれる。
*Main> candidate 1 [2..9]
[2,4,5,6,8]
*Main> candidate 1 [2,3,4,6,7,8,9]
[2,4,6,8,9]便利になった。
ここまでくれば、あとは延々 candidate でリストアップしていけばよい。
nextList :: Int -> [Int] -> [Int] -> [[Int]]
nextList _ sel [] = [sel]
nextList n sel rem = concat [nextList s (sel ++ [s]) (rem \\ [s]) | s <- candidate n rem]nextList 関数は、第一引数が「今選択しているボタン」、第二引数が「今まで選択してきたボタン」、第三引数が「未選択のボタン」だ。
再帰的に呼び出しを行い、全てのありうるパターンを列挙する。
一行目は、いわゆるループ終了条件だ。未選択のボタンが空になったら終了。
今まで選択してきたボタンパターンを返す。
二行目はリスト内包表記を使っているが、Python と類似のものだ。
パイプ記号の右側で次に移動可能なボタンを s に受け取り、左側で各々の s に対して自分自身を呼び出す。
自分自身を呼び出すときの引数は見たままだ。
s がまさに今選択したボタン、(sel ++ [s]) で今まで選択してきたボタンに今選択したボタンを加え、(rem \\ [s]) で未選択ボタンから今選択したボタンを取り除いている。
そして最後に、内包表記を使っているためリストの入れ子になってしまうのを concat 関数で平坦に戻している。
*Main> concat [[1,2],[3,4]]
[1,2,3,4]これでリストアップ関数が手に入った。正しく動いているのか試してみよう。
*Main> nextList 6 [1,2,3,4,5,6] [7,8,9]
[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,8,7,9],[1,2,3,4,5,6,8,9,7],[1,2,3,4,5,6,9,8,7]]今まで、1,2,3,4,5,6 と選択してきて、今 6 にいる。残ってるのは 7,8,9 だ。
その場合は、[…,7,8,9],[…,8,7,9],[…,8,9,7],[…,9,8,7] の 4 通りが残っている、と言っている。
ダメなパターン […,7,9,8] および […,9,7,8] が正しく取り除かれていることもわかる。
では、全件力ずくで数え上げてみようではないか。
初期値は、現在選択しているボタンはないので、ダミーの 0 を入れておこう。
選択済みのボタンは空、未選択のボタンは 1 から 9 全てだ。
allList :: [[Int]]
allList = nextList 0 [] [1..9]ghci で :reload する。
*Main> length allList
14070414万パターンほどらしい…と言いたいところだが、ちょっと待って欲しい。抜けていることがある。
今リストアップしたのは、9 個のボタン全てを使うパターンだけだ。
実際には、指リストは最低 4 個のボタンをなぞれば、そこで指を離してもパターンとして認識される。
そのことを組み入れよう。次のように nextList 関数を修正する。
nextList :: Int -> [Int] -> [Int] -> [[Int]]
nextList _ sel [] = [sel]
nextList n sel rem =
(if 4 <= length sel then [sel] else []) ++
concat [nextList s (sel ++ [s]) (rem \\ [s]) | s <- candidate n rem]終了条件は変わらず。
ただし、「今まで選択してきたボタン」が 4 個以上あったら、まずそれをパターンに加えてから次のパターンを探しに行くようにした。
if は他の言語でもお馴染みだ。
*Main> length allList
389112というわけで、気になる答えは 389,112 通り。
*Main> logBase 2 (fromIntegral it)
18.56982594735497約 18.5 bit だということがわかった。
コード全体
完成したコード全体は下記の通り。
import Data.List
import Data.Maybe
blocklist :: Int -> [(Int, Int)]
blocklist 1 = [(2,3),(4,7),(5,9)]
blocklist 2 = [(5,8)]
blocklist 3 = [(2,1),(5,7),(6,9)]
blocklist 4 = [(5,6)]
blocklist 5 = []
blocklist 6 = [(5,4)]
blocklist 7 = [(4,1),(5,3),(8,9)]
blocklist 8 = [(5,2)]
blocklist 9 = [(5,1),(6,3),(8,7)]
blocklist _ = []
candidate :: Int -> [Int] -> [Int]
candidate i rem = rem \\ mapMaybe (`lookup` blocklist i) rem
nextList :: Int -> [Int] -> [Int] -> [[Int]]
nextList _ sel [] = [sel]
nextList n sel rem =
(if 4 <= length sel then [sel] else []) ++
concat [nextList s (sel ++ [s]) (rem \\ [s]) | s <- candidate n rem]
allList :: [[Int]]
allList = nextList 0 [] [1..9]
main :: IO ()
main = print $ length allListなくても動く型宣言も丁寧に書いたが、それでもわずか30行。
それなりにすっきりしたコードになっていると思うが、どうだろうか。
ところで nextList は、リスト自身がモナドであることを利用して下記のような do 構文でも書ける。
nextList _ sel [] = [sel]
nextList n sel rem =
(if 4 <= length sel then [sel] else []) ++
do s <- candidate n rem
nextList s (sel ++ [s]) (rem \\ [s])このほうが命令型言語に慣れている人は読みやすいかもしれない。
作った玩具で遊ぶ
さて、もともとの目的は達成したのだが、先のコードはずいぶん「ごり押し」をしている。
目的はパターンを数えるだけだったのに、全てのパターンをリストアップしているのだ。
つまり、allList 関数は40万弱のパターンを全部持っている。
ということは、GHCi 上で玩具にして遊べるということだ。
せっかくなので遊んでみよう。
*Main> mapM_ print $ take 10 allList
[1,2,3,4]
[1,2,3,4,5]
[1,2,3,4,5,6]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8,9]
[1,2,3,4,5,6,8]
[1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,8,7,9]
[1,2,3,4,5,6,8,9]最初の 10 件を take 関数で取り出してみた。
ところで、Haskell は遅延評価がどうのこうのというのを耳にしたことがあるだろう。
その効果はこんなときにしっかり現れる。
allList 関数は理論上確かに40万弱のパターンを含んでいるのだが、take により10件目までしか計算せずに終了する。
実にちゃっかりしていることである。
他にもこんな風に遊べる。開始ボタン位置によるパターン数を数えてみよう。
*Main> length $ filter ([1] `isPrefixOf`) allList
38042
*Main> length $ filter ([2] `isPrefixOf`) allList
43176
*Main> length $ filter ([3] `isPrefixOf`) allList
38042
*Main> length $ filter ([4] `isPrefixOf`) allList
43176
*Main> length $ filter ([5] `isPrefixOf`) allList
64240やはり、中央の 5 から始めるとパターン数は多くなる。角から始めるとパターン数が少ないのは、2手目で他の角にいけないせいだ。ちなみに、この isPrefixOf でのフィルタリングでもちゃっかり遅延評価をするらしく、先頭のボタンが違ったらそれ以降の計算は行われないようだ。どこまで lazy なんだ。
同じように終わりも簡単に調べられる。
*Main> mapM_ print $ map (\x -> (x, length $ filter ([x] `isSuffixOf`) allList)) [1..9]
(1,54374)
(2,37144)
(3,54374)
(4,37144)
(5,23040)
(6,37144)
(7,54374)
(8,37144)
(9,54374)5 で終わるパターンは少ない。
中央はなにかと「通り道」なので、どうしても途中に含まれがちなのだろう。
各辺の中央もその傾向があるのが分かる。
最初と最後がバレても多数のパターンが残るのは、中央開始で角終了ということか。
*Main> :{
*Main| maximumBy (\(_, a) (_, b) -> a `compare` b) $
*Main| map (\(x, y) -> ((x, y), length $
*Main| filter ([y] `isSuffixOf`) $ filter ([x] `isPrefixOf`) allList)) $
*Main| [(x, y) | x <- [1..9], y <- [1..9], x /= y]
*Main| :}
((5,9),9620)9620 パターンだそうだ。
*Main> :{
*Main| minimumBy (\(_, a) (_, b) -> a `compare` b) $
*Main| map (\(x, y) -> ((x, y), length $
*Main| filter ([y] `isSuffixOf`) $ filter ([x] `isPrefixOf`) allList)) $
*Main| [(x, y) | x <- [1..9], y <- [1..9], x /= y]
*Main| :}
((1,5),2688)逆に角から初めて中央で終わるパターンが一番少なく、2688 パターンになる。
ボタンの個数でパターン数を数えたりもできる。
mapM_ print $ map (\x -> (x, length $ filter ((x ==) . length) allList)) [4..9]
(4,1624)
(5,7152)
(6,26016)
(7,72912)
(8,140704)
(9,140704)ボタンを 4 個しか選ばないと、1624 通りしかない。5 個選んでも数字 4 桁より少なくなってしまう。
6 個選べば数字 4 桁よりは多いが、それでも数字 5 桁の方がパターン数は多い。
任意の数字を選ぶよりも制限が多いので仕方ないのだが。
8 個選ぶ場合と 9 個選ぶ場合の数は同じだが、これは当然で、残された 1 個を選ぶか選ばずに終了するかだけだからだ。
殆どの人は 9 個全て選ぶパターンを登録しているように思うが、意表をついて最後の 1 個を残すパターンでロックするのもありかもしれない。
指リストパターンをどうするか迷ったら、乱数に決めてもらうのはどうだろう。
*Main> :m +System.Random
*Main System.Random> print . (allList !!) =<< (getStdRandom $ randomR (0, length allList - 1))
[5,8,2,6,4,9,1,7]実行ごとに違うリストが取得できる。fingerlist.hs の main 関数はコレにしておいても良いかもしれない。
＃人気の記事
＃タグ
