JavaScriptによる総当たり検索

  • 8
    いいね
  • 0
    コメント

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