チョンボ王Hさんのファーストチョンボ〜外伝〜
【結論】
毎日ブログを書いている人間は、一つの出来事を顕微鏡で拡大してみる悪癖が身に付く。
これは、良く言えば一つ一つの事象をしっかり分析できる人。
悪く言えば話が長いおじさん。(個人の見解です💦)
コードを日本語で説明するのは大変。
【目次】
はじめに
今回もファーストチョンボネタの続きです。
「ダイヤル式のロッカーのパスワードが分からなくなったのをなんとか開けることができた」と一言で終わる話を、前編、中編、後編の3回に分けるだけでも大分カサ増しをしている自覚はあります。
にも関わらず、外伝まで書く理由は「俺、プログラマーだよ😤」アピールをするために書いた記事に載せたソースが殆ど役にたたなかったからです😭
よって、汚名を返上するためにずうずうしく、外伝まで書いていきます。
(…恥の上塗りをしてるだけの気もしますが😅)
前回のロジックの失敗点
前回のロジックは、0000〜9999を次の順番になるように並び替える方針で実装しました。
- 0だけで構成される暗証番号
- 0から1回だけダイヤルを動かした[1,9]も追加した、[0,1,9]で構成される暗証番号
- 0から2回だけダイヤルを動かした[2,8]も追加した、[0,1,9,2,8]で構成される暗証番号
- 0から3回だけダイヤルを動かした[3,7]も追加した、[0,1,9,2,8,3,7]で構成される暗証番号
- 0から4回だけダイヤルを動かした[4,6]も追加した、[0,1,9,2,8,3,7,4,6]で構成される暗証番号
- 0から5回だけダイヤルを動かした[5]も追加した、[0,1,9,2,8,3,7,4,6,5]で構成される暗証番号
基本的にはこの考えであっている認識なのですが、一つ重大なミスをしています。
それは、手順1の0000で構成される暗証番号をベースにしている点です。
私がチョンボをした原因は、ダイヤル式ロッカーの以下の仕様を認識していなかったからです。
ダイヤル式のロッカーでは、ダイヤルが1と0の中途半端な位置にある場合は暗証番号は確定していません。
その状態でロックをかけた後にダイヤルを1か0に変更した段階でパスワードが確定します。
この仕様を考慮に入れると、手順1は0000ベースではなく、自分が設定したつもりの暗証番号ベースにすべきでした。
効率よくパスワードを試す方法
判明したロジックの失敗点を元に0000〜9999を並び替える手順について考えていきます。
暗証番号が(n1,n2,n3,n4)で構成され、想定したパスワードが2019だった時のダイヤルを回した回数と数字を表したのが下表になります。
| 0回 | 1回 | 2回 | 3回 | 4回 | 5回 | |
|---|---|---|---|---|---|---|
| n1 | 2 | 1,3 | 0,4 | 9,5 | 8,6 | 7 |
| n2 | 0 | 9,1 | 8,2 | 7,3 | 6,4 | 5 |
| n3 | 1 | 0,2 | 9,3 | 8,4 | 7,5 | 6 |
| n4 | 9 | 8,0 | 7,1 | 6,2 | 5,3 | 4 |
この表をもとに、n1の並び替えの優先度は表したのが下表になります。
| 並び替えの優先度 | ダイヤルを回す回数 | 数字の組み合わせ | 数字の種類 |
|---|---|---|---|
| 高い | 0回 | 2 | 1 |
| 1回 | 2,1,3 | 3 | |
| 2回 | 2,1,3,0,4 | 5 | |
| 3回 | 2,1,3,0,4,9,5 | 7 | |
| 4回 | 2,1,3,0,4,9,5,8,6 | 9 | |
| 低い | 5回 | 2,1,3,0,4,9,5,8,6,5 | 10 |
今回は省略しますが、n2からn3も同様の表を作成します。
そして、ダイヤルを回す回数が少ない数字の組み合わせが上位に来るように並び替えます。
例としてダイヤルを1回まわす数字の組み合わせは、
n1が[2,1,3]、n2が[0,9,1]、n3が[1,0,2]、n4が[9,8,0]
になる数字の組み合わせをを網羅すればいいことになります。
網羅するには、n1〜n4は各々3種類づつなので、3進数で表すことでき、4桁あります。
よって、0から81(3の4乗)までの10進数を3進数に変換し、n1からn4のリストに従って変換してあげれば網羅できます。
ダイヤルを2から5回まわすケースも同様です。
- ダイヤルを最大2回まわして表現できる数字は5種類なので5進数
- ダイヤルを最大3回まわして表現できる数字は7種類なので7進数
- ダイヤルを最大4回まわして表現できる数字は10種類なので9進数
- ダイヤルを最大5回まわして表現できる数字は10種類なので10進数
ここまでで、ダイヤルを0から5回まわしてできる数字を求めることはできました。
次に、求めた数字で並び替える必要があります。
並び替えの優先度はダイヤルをまわした回数が少ない数字ですが、次の点に考慮する必要があります。
ダイヤルを最大(n)回まわしてできる数字の組み合わせは、ダイヤルを最大(n+1)回まわしてできる数字にも含まれる。
上記を考慮して並び替えるために、今回は次のようなアプローチを取りました。
- 0000〜9999はダイヤルを最大5回まわしてできる暗証番号を網羅している。
- ダイヤルをまわす回数をn回とした時、nを4から1づつ減らして0になるまで次の処理を行う。
- ダイヤルを最大n回まわしてできる暗証番号をリストの先頭に移動させれば、ダイヤルを最大(n+1)回まわしてできる暗証番号の優先度は下がる。
完成したソース
以下になります。
参考情報
さいごに
もっと効率が良くかつ簡潔なロジックはあるのかもしれないですが、これが今の私の実力です。
因みに、このブログを書くの費やした時間が以下になります。
- アプローチを思いつくのに2日
- 具体的なコードに落とし込むのに3時間
- ブログにまとめるモチベーションを上げるために4時間
- ブログにまとめるのに2時間
この作業時間で毎日ブログ更新している自分を褒めたたえたくなる一方で、この程度のロジックは一瞬で実装してまとめれるレベルになりたい😭
