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ページ作ります。

Mack Calculation

↓

できました！！

終わりに

これで脱出ゲームで、覆面算が出てきても大丈夫です。
これまで戦術だけであった脱出ゲームに戦略的に勝利する日はくるのか・・

さて、最後に企画倒れな求人広告案。総当たり検索ロジック組まないと解けないですが、
解くととあるドメインがでてきます。そこには求人広告を置いておく。
って案は、Googleの企画のまるパクリといわれて却下されました。
（ドメインをとってないので、解いてもなにもありません。）