にほ録

作業記録です。

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

Androidのアンロックパターンは389,112通り

2010-11-13 13:36:58 | Weblog

Androidのアンロックパターンは、写真のような画面で、点を一筆書きで結んでいくというもの。
可能な結び方は次の通り。

a) 縦か横か斜めで隣接している場合
b) 桂馬飛びでつながる場合
c) すでに通過済みの点を飛び越えてつながる場合 (未通過の点を飛び越えようとすると、その点が先につながってしまう)

各点に、下記のように番号をつけて点の結び方の例を示すと、
789
456
123

a) 7-8, 7-4, 7-5など
b) 7-2, 4-3など
c) 8-9-7, 5-6-8-2など

こういったつなぎ方で、一筆書きで、4つ以上の点を結ぶというのがアンロックパターンのルール。

有効なパターンが何通りあるかプログラムで数えてみた。で、結果はタイトルの通り、389,112通り。
つまり、5桁から6桁の暗証番号と同じ安全性ということ。

内訳は以下の通り。
長さ4: 1624
長さ5: 7152
長さ6: 26016
長さ7: 72912
長さ8: 140704
長さ9: 140704

それぞれが8の倍数になっているのは、1つのパターンに対して、90°ずつ回転して4パターン、左右反転してから90°ずつ回転して4パターンと、合計8パターンが作れるから。

同じ計算をしている人がここ↓にもいた。
http://beust.com/weblog2/archives/000497.html

おいらのプログラムは下記の通り。
「C言語による最新アルゴリズム事典」(奥村晴彦著)の順列生成を参考にした。この本いいわ。



<script type="text/javascript">//
// 1~9の数字が使われたかどうか。
// used[1]~[9]を使う。used[0]はtrueにしておく。
var used = new Array(10);

// 順列を入れる箱。
// p[0]~[8]を使う。
var p = new Array(9);

// カウンタ。
// valid[4]~[9]を使う。
var valid = new Array(10);

// middle
// 7 8 9
// 4 5 6
// 1 2 3
var middle = new Array(10);
for(var i = 1; i
  middle[i] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
}

middle[7][9] = middle[9][7] = 8;
middle[7][1] = middle[1][7] = 4;
middle[7][3] = middle[4][6] = middle[1][9] = middle[2][8] = middle[3][7] = middle[6][4] = middle[9][1] = middle[8][2] = 5;
middle[9][3] = middle[3][9] = 6;
middle[1][3] = middle[3][1] = 2;

function put(pos, k, len) {
// 場所posに数値kを入れる
  p[pos] = k;
  if(pos == len - 1) {
    count(len);
  }
  else {
    used[k] = true;
    for(var j = 1; j
      if(!used[j] && used[middle[k][j]]) {
        put(pos + 1, j, len);
      }
    }
    used[k] = false;
  }
}

function count(len) {
  valid[len]++;
}

function show() {
  for(var i = 1; i
    used[i] = false;
    valid[i] = 0;
  }
  used[0] = true;

// l: 順列の長さ
  for(var l = 4; l

// m: 最初の箱に入れる数値
    for(var m = 1; m
      put(0, m, l);
    }

  }

  for(var i = 4; i
    var s = 'Length ' + i.toString() + ': Number of valid patterns is ' + valid[i].toString() + '.
';
    document.getElementById('ans' + i.toString()).innerHTML = s;
  }

}
// ]]></script>







thinking...


 


ジャンル:
ウェブログ
コメント (1)   この記事についてブログを書く
この記事をはてなブックマークに追加
« Subversionのリポジトリバッ... | トップ | Androidのアンロックパターン... »
最近の画像もっと見る

1 コメント

コメント日が  古い順  |   新しい順
プログラムについて (butchi)
2012-02-09 00:06:04
パターン数が気になって飛んできました。
プログラム中のfor文が全部
for(var i = 1; i
みたいに途中で切れちゃってるんですが、これで正しいんでしょうか?
ちょっと修正版の方は正しく動きました。

コメントを投稿

Weblog」カテゴリの最新記事

関連するみんなの記事

トラックバック

この記事のトラックバック  Ping-URL