JavaScript

JavaScriptによる総当たり検索

More than 1 year has passed since last update.


JavaScriptによる総当たり検索


打倒!覆面算

いきなりですが、自分は脱出ゲームや謎解きに、はまっています。

その中でたまに出てくる「覆面算」ってのが苦手です。

fukumen001.jpg

ルール

・同じ文字には同じ数字が入り、違う文字には違う数字が入る。

・最上位の文字には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ページ作ります。

Mack Calculation

fukumen002.jpg



fukumen003.jpg

できました!!


終わりに

これで脱出ゲームで、覆面算が出てきても大丈夫です。

これまで戦術だけであった脱出ゲームに戦略的に勝利する日はくるのか・・

さて、最後に企画倒れな求人広告案。総当たり検索ロジック組まないと解けないですが、

解くととあるドメインがでてきます。そこには求人広告を置いておく。

って案は、Googleの企画のまるパクリといわれて却下されました。

(ドメインをとってないので、解いてもなにもありません。)

fukumen004.jpg