#JavaScriptによる総当たり検索
##打倒！覆面算
いきなりですが、自分は脱出ゲームや謎解きに、はまっています。
その中でたまに出てくる「覆面算」ってのが苦手です。
ルール
・同じ文字には同じ数字が入り、違う文字には違う数字が入る。
・最上位の文字には0は入らない。
この場合は、M=1ではないかってとこから解きだすのでしょうが・・・
ここはプログラマー的に考えます。
とりうるパターンは10の階乗通り・・・・
10! = 3,628,800
総当たりでやっても全然いけそうです。
やってみよう！
##Cでやってみた
0~9までの総当たりをループするプログラム
X=1;
for(j[X]=1;j[X]<=Max-X;j[X]++){
p[j[X]] = 1;
X=2;
for(j[X]=1;j[X]<=Max-X;j[X]++){
for(k=1,m=1;k<=j[X];m++) if(p[m]==0) k++;
p[m-1] = X;
X=3;
for(j[X]=1;j[X]<=Max-X;j[X]++){
for(k=1,m=1;k<=j[X];m++) if(p[m]==0) k++;
p[m-1] = X;
X=4;
for(j[X]=1;j[X]<=Max-X;j[X]++){
for(k=1,m=1;k<=j[X];m++) if(p[m]==0) k++;
p[m-1] = X;
・・・・
ちょっと待てよ。このまま10層まで書くのはエレガントではない・・・
Google先生にお知恵を拝借。
typedef int ITEM;
typedef ITEM* Iterator;
//*x と *y を交換する
void iter_swap(Iterator x, Iterator y){
ITEM t = *x;
*x = *y;
*y = t;
}
//first以上 last未満の範囲を反転する
void reverse(Iterator first, Iterator last){
while( first != last && first != --last){
iter_swap(first, last);
++first;
}
}
//次の組み合わせに入れ替える
bool next_permutation(Iterator first, Iterator last){
Iterator i = last;
if(first == last) return false;
if(first == --i) return false;
while(1){
Iterator i1, i2;
i1 = i;
if(*--i < *i1){
i2 = last;
while(!(*i < *--i2));
iter_swap(i, i2);
reverse(i1, last);
return true;
}
if(i== first){
reverse(first, last);
return false;
}
}
}
こんな感じで、関数宣言
int main(){
const int N = 4;
ITEM data[] = { 1, 2, 3, 4 };
do{
printf("%d,%d,%d,%d\n",data[0],data[1],data[2],data[3]);
}while(next_permutation(data, data+N));
return 0;
}
原理は1,2,3,4で表せる次に大きな数に入れ替える関数です。
このアルゴリズム作った人、天才です。
void main(){
const int N = 10;
ITEM d[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
do{
/* ここに計算が成り立つかの判定分を入れる ≪上記サンプルとは別の問題≫ */
if( d[0]*1000 + d[1]*100 + d[2]*10 + d[3]
+ d[4]*1000 + d[3]*100 + d[5]*10 + d[6]
== d[0]*10000 + d[1]*1000 + d[5]*100 + d[3]*10 + d[7]
&& d[0] != 0)
{
printf("D=%d E=%d B=%d T=%d S=%d A=%d R=%d H=%d\n",d[0],d[1],d[2],d[3],d[4],d[5],d[6],d[7]);
}
}while(next_permutation(d, d+N));
}
結果、1秒以内で十分総当たりいけました。
##JavaScriptでやってみた
総当たりという重い処理を、JavaScriptでやるという矛盾はおいて置くと、
何より手軽のが良いです。ブラウザがあれば、それだけで実行できます。
var item = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
//*x と *y を交換する
function iter_swap(x, y){
var t = item[x];
item[x] = item[y];
item[y] = t;
}
//first以上 last未満の範囲を反転する
function reverse(first, last){
while(first != last && first != --last){
iter_swap(first, last);
++first;
}
}
function next_permutation(first, last){
var i = last;
if(first == last) return false;
if(first == --i) return false;
while(1){
var i1, i2;
i1 = i;
if(item[--i] < item[i1]){
i2 = last;
while(!(item[i] < item[--i2]));
iter_swap(i, i2);
reverse(i1, last);
return true;
}
if(i==first){
reverse(first, last);
return false;
}
}
}
後はmain関数で
do{
//判定文
}while(next_permutation(0, 10));
さすがに重い。10秒以上かかりますね。
##外出先でやる為
後は、パソコンなくてもできるように、Webページ作ります。
↓
できました！！
##終わりに
これで脱出ゲームで、覆面算が出てきても大丈夫です。
これまで戦術だけであった脱出ゲームに戦略的に勝利する日はくるのか・・
さて、最後に企画倒れな求人広告案。総当たり検索ロジック組まないと解けないですが、
解くととあるドメインがでてきます。そこには求人広告を置いておく。
って案は、Googleの企画のまるパクリといわれて却下されました。
（ドメインをとってないので、解いてもなにもありません。）
