前 5‒26 p ｜ 
もくじ i ｜ 次 6‒01 n 
1=4+4/4-4, 2=4/4+4/4, 3=(4+4+4)/4, ... のように4つの4を使って整数を作るパズルは古典的だが、今回は「うまい計算式を考える」という仕事をJavaScriptにやらしてみた。0～100までに対応する式が一気に自動構成されるのは壮観だ。しかも人間には考えつかないような奇妙な計算法をひねりだす。考えているのはプログラマだろうか、プログラムだろうか…
1分で100、2分で0～200まで到達
夢のもつれ
1=4+4/4-4, 2=4/4+4/4, 3=(4+4+4)/4, ... のように4つの4を使って整数を作るパズルは古典的だが、今回は「うまい計算式を考える」という仕事をJavaScriptにやらしてみた。0～100までに対応する式が一気に自動構成されるのは壮観だ。しかも人間には考えつかないような奇妙な計算法をひねりだす。考えているのはプログラマだろうか、プログラムだろうか……
パズルのやり方はご存じと思うが、次のようなものである。
0 = 4 + 4 - 4 - 4
1 = 4 + 4 / 4 - 4
2 = 4 / 4 + 4 / 4
3 = ( 4 + 4 + 4 ) / 4
4 = ( 4 - 4 ) × 4 + 4
5 = ( 4 + 4 × 4 ) / 4
6 = ( 4 + 4 ) / 4 + 4
7 = 4 + 4 - 4 / 4
8 = 4 + 4 + 4 - 4
9 = 4 + 4 + 4 / 4
10 = √4 × ( 4 + 4 / 4 )
この調子で数を順々に作ってゆく。左辺の数を得るための右辺の作り方は一通りとは限らないが、とにかくひとつのやり方を見つけるのがこのパズルだ。
2002年5月29日 追記: テーブルを作る目的に限れば、もっと高速化できる。高速化版を使うと、数秒以内に30までのテーブルを、30秒～1分程度で100までのテーブルを生成できる。
2002年5月30日 追記: 「4つの4」のデモをネスケ、モジラ、オペラでも動くようにしました。 これらのラムダ関数版は「高速化版」のさらに二倍程度で処理できます。（現時点で最速）
2002年6月10日 追記: 0～1000までの作り方を何と10秒以内にリストアップできるようになりました。詳細
注: もっと根本的に速いアルゴリズムあり。「「西暦・平成パズル」を解くアルゴリズム」参照。
「ふつう」のプログラムは式を与えて答を計算させるのであるが、このスクリプトは「式」そのものを生成する、というところが、おもしろさだ。
しかも、93 = 4 × ( 4 ! - (∑(√4)) / 4 ) のように、人間の常識では思いもよらないようなことを「考える」……。24から4分の3を引いて23.25。それを4倍すると93。という計算なのだ。
4つの4を使ってNを作るような式を検索する。getExpression() と canon() は、すぐあとで詳しく説明する。
var NUMBER = 4;
var found = 0;
function four4s( N ) {
if(typeof execScript == "undefined") return;
found = 0;
var expression, _expression, hack;
var param_max_pow = 8;
var param2max = 5;
for(var param=0; param<Math.pow(2,param_max_pow); param++ ) {
for(var param2=0; param2<=param2max; param2++ ) {
for(var op_code=0; op_code<Math.pow(4,3); op_code++) {
expression = getExpression( N, op_code, param, param2 );
_expression = '"' + expression + '"';
hack = 'if(' + expression + ') { ';
hack += ' found++; ';
hack += ' document.write("<p>" + canon(' + _expression + ') );';
hack += ' document.write("<\/p>");';
hack += '}';
execScript(hack);
if(found) return true;
}
}
}
document.write("<p><strong>" + N + "<\/strong> not solved.<\/p>");
return false;
}
ごらんのように、もし意味的に解釈すると「もし expression が正しければ expression を書き下せ」という意味になるような文字列 hack を形式的に生成して、次にその文字列を execScript(hack) で実質的に評価する。アイディアは、これに尽きる。ちょっぴり意味論的な遊びのにおいがする。
found がグローバル変数になっている理由は「execScript()が解釈する変数のスコープ」参照。
数値パラメータから実際の式にあたる文字列を生成する部分。これは、すべての考えうる可能性を尽くしていない。より広い可能性の範囲を検索すれば、より高い確率でパズルが解けるが、それは計算時間とのトレードオフになる。
function getExpression( target, _op_code, param, param2 ) {
var N1 = NUMBER, N2 = NUMBER, N3 = NUMBER, N4 = NUMBER;
// 演算子をとりあえず単なる文字として扱う
var operator = [ " + " , " - " , " * " , " / " ];
// 4進数で表現
var str = _op_code.toString(4);
while(str.length<4) str = "0" + str;
var op_code = new Array();
for(var i=0; i<4; i++) op_code[i] = str.charAt(i);
var op1 = operator[op_code[1]];
var op2 = operator[op_code[2]];
var op3 = operator[op_code[3]];
var str2 = param.toString(2);
var max = 7;
while(str2.length<=max) str2 = "0" + str2;
var p_code = new Array();
for(var j=0; j<=max; j++) p_code[j] = str2.charAt(j);
// (2)はルート4、(24)は4の階乗、(10)はΣ4すなわちΣn [n=1 to 4]
// (3)はΣ(2) で、ディスプレイのときそのような文字列に整形される
if(p_code[max-1]=="1") { N1 = "(2)"; }
if(p_code[max-2]=="1") { N2 = "(24)"; }
if(p_code[max-3]=="1") { N3 = "(10)"; }
if(p_code[max-4]=="1") { N4 = "(2)"; }
if(p_code[max-5]=="1") { N1 = "(10)", N3 = "(10)"; }
if(p_code[max-6]=="1") { N1 = "(3)"; }
if(p_code[max-7]=="1") { N3 = "(3)"; }
if(p_code[max]=="1") { N1 = "-" + N1;}
// いろいろな括弧の付け方を試す
var o=" ( ", c=" ) ";
var p1_="", _p1="", p2_="", _p2="", p3_="", _p3="", p4_="", _p4="";
if(param2==0) { ; }
else if(param2==1) { p1_=o, _p2=c; }
else if(param2==2) { p1_=o, _p3=c; }
else if(param2==3) { p2_=o, _p3=c; }
else if(param2==4) { p2_=o, _p4=c; }
else if(param2==5) { p3_=o, _p4=c; }
return target + " == " +
p1_ + N1 + _p1
+ op1 +
p2_ + N2 + _p2
+ op2 +
p3_ + N3 + _p3
+ op3 +
p4_ + N4 + _p4;
}
計算式が発見されたら整形する部分。
function canon( expr ) {
expr = expr.replace(/(\d+)/, "<strong>$1<\/strong>");
expr = expr.replace(/==/, "=");
expr = expr.replace(/\*/g, "×");
expr = expr.replace(/\(24\)/g, "4 !");
expr = expr.replace(/\(2\)/g, "√4");
expr = expr.replace(/\(10\)/g, "∑4");
expr = expr.replace(/\(3\)/g, "(∑(√4))");
return expr;
}
検索アルゴリズムは、たぶんもっと高速化できるはずだが（表を作る目的なら、むしろ全部の可能性で整数解になるものを記録し、あとから逆引きの表にしたほうが良いかも）、とりあえずこんなので動いた（一項で構成できるものを調べあげ、次にそれともうひとつの4に2項演算子を適用して構成できるものを調べあげ……といった方法で再帰的に4項で構成できるものを枚挙することも考えられる）。手元の IE6.0 SP1 for Windows 2000 で動作確認している。IEは、JavaScript で時間がかかりすぎると「計算を中止しますか？」（デフォルトで中止する）と何度も何度も尋ねてくるが、やり通すには「いいえ」と答えて続行する必要がある。
興味があるかたは、スクリプトをいろいろ直接いじってみてほしい。HTMLからの呼び出し方の例。
<!-- ライブラリをインクルード -->
<script type="text/javascript"
src="https://yosei.fi/demo/four4s/four4s.js"></script>
<!-- ソースの例 -->
<script type="text/javascript">
four4s(105); // 4つの4を使って105を作る式を検索する
</script>
2002-05-29 「JavaScript: 4つの4で遊ぼうよ」では、計算時間が何分もかかるクソ重いデモを公開しましたが……ざっと10倍高速化できました。
高速化といっても、最初のやり方が効率悪かっただけです。
最初のメモのなかにもありますが検索結果のテーブルを作って逆引きしたほうが速いです。
例えば、9の作り方を探すとき、スクリプトは次のように4回の試行を行います。
Step #1. Checking the expression 4 + 4 + 4 + 4 I got 16. Step #2. Checking the expression 4 + 4 + 4 - 4 I got 8. Step #3. Checking the expression 4 + 4 + 4 * 4 I got 24. Step #4. Checking the expression 4 + 4 + 4 / 4 I got 9.
このように9を探す過程でふずい的に16、8、24の作り方も発見されています。9を探すことが目的であれば、そういった副作用は雑音にすぎませんが、あとから一覧テーブルにしたいのだったら、16、8、24の作り方も記録しておいたほうがトク。最初のバージョンでは、9なら9単体を探すことに集中する関数をループさせて1～100などをそのつど Step #1 から検索していたので、たいへんムダだったわけです。
今回の方法。
var evaluated = 0;
function four4s_table( N ) {
var td = new Array( N+1 );
for(var i=0; i<=N; i++ ) td[i] = "";
var expression, hack;
var param_max_pow = 10;
var param2max = 5;
var found = 0;
// 表の各コマのデータ td を見つかりしだい記憶する
LOOPS: for(var param=0; param<Math.pow(2,param_max_pow); param++ ) {
for(var param2=0; param2<=param2max; param2++ ) {
for(var op_code=0; op_code<Math.pow(4,3); op_code++) {
expression = getExpression2( op_code, param, param2 );
hack = 'evaluated = ' + expression ;
execScript(hack);
// 使えないデータを飛ばす
if( evaluated != Math.floor( evaluated )
|| evaluated > N || evaluated < 0 )
continue;
// evaluatedは0以上N以下の整数値
if( td[ evaluated ] == "" ) {
var str = canon( evaluated + " == " + expression ) ;
td[ evaluated ] = str ;
found++;
if(found>=N+1) break LOOPS;
}
}
}
}
// 表を整形出力
for(var i=0; i<=N; i++) {
if( td[i] == "" ) td[i] = "<strong>" + i + ": No results found.<\/strong>";
_debug( td[i] );
}
}
例えば four4s_table(10) は、0～10の11個の数の作り方を調べあげて一覧表にします。11個のデータを保存するために、まず長さ11の配列を確保し、そして技術的には必要ないのですが、全部、長さ0の文字列 "" で初期化しときます。
LOOPS: では getExpression2() 関数が3つのパラメータを元に数式の右辺だけを生成します。最初のバージョンの getExpression() では両辺を == で結んだものを生成して真偽値を評価してました（目標となる左辺値が固定されていたため）。今回のバージョンでは、左辺は自分で計算します。すなわち
evaluated = その式
という文字列hackをまず単なる記号列として機械的に構成し、次に、それを内容的に評価します。evaluated には右辺を評価した結果の数値が入ります。これが整数でなかったり、探す目的の最大値Nを越えていたり、負の数のときは、要らないので捨てます。なお負の数のときには
evaluated *= (-1);
expression = " - ( " + expression + " )";
とすれば役立つデータに変換できますが、これをやってもたいして速くなりません。
……と思ったのですが、負の数の「利用」とほかの簡単な見直しを組み合わせることで計算時間を半分にできるのでした。ラムダ関数版には、この改善もとりいれられており、手元の環境では、当初6分以上かかった100までの計算が12秒に短縮されています。
例えば getExpression() が 4 + 4 + 4 - 4 という expression を返した場合、スクリプトは
evaluated = 4 + 4 + 4 - 4
という文字列をスクリプトとして評価します。だから evaluated に 8 が入ります。そして8の作り方も捜索範囲だとします。このときスクリプトは、配列tdの8番 td[8] を見に行きます。もしそこに空文字列が格納されているとしたら、スクリプトは、自分はまだ8の作り方を知らないのだ、と気づいて、td[8] に文字列
4 + 4 + 4 - 4
ないし、それと等価の情報を含む文字列を格納します。逆に、すでにtd[8] に 値があるなら、自分は8の作り方ならもう発見している、ということなので、スクリプトたんは「8は、もうあるからいらん」と思って、さっさと忘れて次に行くわけです。
新しい作り方を発見するたびに、スクリプトたんは初期値が0の変数 found を1増加させます。ですから found が N+1 に達したなら、捜索範囲の全部の数のレシピが見つかったことを意味します。上の例では、td[0] ～ td[10] がすべて埋まったわけです。だから、break LOOPS; で3重ループを一気に離脱、あとは配列td を用いて表を出力するだけです。テーブルを作る段階でもしtd[i]が空であれば、それはループを全部まわってもiの作り方を発見できなかったことを意味しますから、iの欄は未発見と表記しなければなりません。getExpression2()エンジンは、以前のgetExpression()より強力で、200までのすべての自然数に対応する式をそこそこ効率的に生成できます。
今回の高速化バージョンの全ソースは、four4s_2.js で見ることができます。
この発想を一般化することによって、もちろん、5つの5を使うとか、1, 2, 3, 4 を使うとか、いろいろパズルを拡張できます。また、例えば、偽春菜から名前を変えたソフトのようなものに組み込むことによって、ひとつのゴーストが「4を4つ使って400を作る方法って分かる?」と尋ね、それに応じてべつのゴーストが「検索します。しばらくお待ちください……」というふうに考えて答えを見つけるような印象的なデモにも発展させることができるかもしれません。
パズルの答の一覧表データベースを持っていて調べるのでなく、その場で動的に解を探すところがポイント。
このようなアルゴリズムを作ることを単に「パズルを強引に速く解くためのずるい手段」としか感じられないかたもおられるかもしれません。そのような感受性では、ディープブルーのプログラマたちも単にチェスで勝ちたかっただけ、イライザのプログラマはチャット相手をだましたかっただけ、としか思えないでしょうし、形式的、機械的、無機的に文字列を構成し、次にその文字列の「意味」を自分（その文字列を生成したスクリプト自身）でエバリュエートする、というスリルも理解できないことでしょう。ですが、それが人間にとっての自然な認識なのかもしれません。
単にパズルの答が知りたいだけなら、時間をかけて0～1000でも計算したものをスタティックに保存しておいて、クエリーに対してそれをそのまま返すほうが速くて的確です。が、このささやかな実験の妙味は、得られるパズルの「答」じゃなく、その場でプログラムたんがいっしょうけんめい考えて答を探す、というプロセスのほうです。極端な話、ある整数に対してパズルが解けないとしても、解なしと結論するにいたる思考プロセスに興味があります。べつの角度からいえば、このアルゴリズムは「4つの4」に特化したものではなく、いろいろに応用できる柔軟性の高い発想を含んでるわけで、そのポテンシャルがおもしろいとも言えるでしょう。
たしかに昔のプログラム／ロボットは、どれも人間に役立つための人間の道具にすぎなかったのかもしれません。
このメモでは、「4つの4で遊ぼうよ」の found 、「「4つの4」高速化の説明」の evaluated が、特定の関数の内部でしか使われないのに、なぜわざわざグローバルになっているのか？を説明します。これらの変数は、見かけ上、特定の関数の内部でしか使われていないものの、その関数のローカル変数として宣言すると、致命的エラーが発生します。
1 + 2というのはJavaScriptの式であり、値は3であるが、"1 + 2"は5文字（'1', ' ', '+', ' ', '2'）からなる単なる文字列である。
document.write( 1 + 2 ); // 3という数字が出る document.write( "1 + 2" ); // 「1 + 2」という文字列が出る
同様に、document.write( 1 + 2 ); は関数（命令）だが、"document.write( 1 + 2 );"というコードは単なる文字列である。MSIEのJScriptでは、次のようなハックが使える。
var str = "document.write( 1 + 2 );" // ただの文字列 document.write( str ); // 上の文字列をエコー execScript( str ); // 上の文字列を意味的に解釈して「3を書け」を実行（3が出る）
このように、execScript は形式的なシニファンの世界（「現実」）と、それを解釈するシニフィエの世界（「幻想」）との、２世界を連結する道をひらく。本質的には Lispでいうラムダ関数とみるべきだろう。
これらの２世界のあいだで通信を行うさいには、変数のスコープに注意が必要だ。次のコードは、いっけんまともだが、実際には機能しない。
function test() {
var x = 5;
var str = "document.write( x );";
execScript( str ); // エラー
}
test();
x は test() のなかで定義されているローカル変数である。そして str も同じ関数のなかで定義されているローカル変数である。しかし、str のなかにある記号 x が解釈されるときの文脈はグローバルである。もしグローバル変数 x が別に定義されているのでない限り、execScript() の世界における document.write は未定義の変数 x を書き出そうとしてアクセスに失敗し例外を発生させる。上のコードでは、execScript() の世界から関数 test() のローカルな現実が見えない ―― execScript() は見かけ上、ローカルに呼び出されているにもかかわらず。
関数のなかで生成される値を execScript() の世界に持ち込みたいときの通信経路は、次のいずれかを利用することになる。第一はグローバル変数経由。
var global_x;
function test() {
var x = 5; // 初期値
// x に関する処理
global_x = x; // グローバル変数に入れる
var str = "document.write( global_x );"; // うまく行く
}
同じことだが、最初から x をグローバルにしても良い（関数の外に書くか、var宣言をやめる）。この方法だと、幻想世界と現実世界の両方から同じものを操作できる。
第二の方法は、幻想世界のタネstrを現実世界で構築する段階で、通信文を入れてしまう。
function test() {
var x = 5; // 初期値
// x に関する処理
var str = "document.write( " + x + ");"; // うまく行く
}
幻想世界で生成された結果を現実で利用するにはグローバル変数経由で通信を行うか、さもなければ、（どちらからどちらの場合についても）「むこう」の世界で行ったほうが見通しが良い処理をがんばって「こっち」ですませて、通信内容は単なる記号列の伝達になるようにする。「4つの4で遊ぼうよ」「「4つの4」高速化の説明」のコードでは、両方の例がある。いっけん妙なグローバル変数も、このことに関係している。
シニフィエの世界への通信は、どのみち記号列を渡すだけ（それを解釈させる）なので原則として第二の方法も有効であるが、逆向きの通信は第二の方法だと、ややこしい。通信というより、要するに最終的な出力まで「むこう」でやってもらう、ということになる。ごく単純な場合をのぞいて、グローバル変数を使う第一の方法が良いだろう。
逆向きの通信においては、幻想世界がグローバルに置かれていることの結果として、次の方法も、いっけん意外かもしれないが、うまく行く。
function test() {
var str = "var x = 1 + 2";
execScript( str ); // グローバルスコープでx=1+2を宣言したのと同じ
document.write( x ); // ここからも3が見える
}
ただし、test()内でローカルにxを使うと、夢幻の x にアクセスできなくなってしまう。次のもつれた例を観察せよ。
function test(){
var x = "var x = 1 + 2; document.write(x);";
execScript( x ); // 3を書き出す
document.write( x ); // 「var x = 1 + 2; document.write(x);」という文字列
}
test();
execScriptが解釈する文字列は、グローバルの文脈で解釈されるので、既存のグローバル変数を上書きできる（場合によっては「汚染」してしまう）。決して仮言的に実行され実行後ただちに破棄されるものでなく、最も強いスコープで現実に恒常的に書かれたのと同じ作用を持つ。
var x = 50;
function test() {
var x=10; // これでグローバルのxにはアクセスできなくなるようだが...
x++; // アクセスされるのはローカル変数
document.write( x ); // 11
var str = "var x=1+2; document.write( x );";
execScript( str ); // 3
document.write( x ); // 11 に戻る。安心した?
}
document.write( x ); // 50
test(); // 自分自身のローカルな作業変数xを持つ
document.write( x ); // ところがどっこい3
要するに、夢幻の世界 execScript() は いっけん test() が見るプライベートな夢のようだが、夢のなかであなたが行ったことは、普遍の世界のできごとになってしまう。本来 test() 自身からは触ることができないx にまでさわれてしまう。このことを逆用すると、ローカル変数のスコープに妨害されてアクセスできなくなったグローバル変数を無害に参照することもできる。
var x = 50;
function test() {
var x = 10; // グローバルのxが見えなくなる
var hack = "var _tmp=x";
execScript(hack); // 見かけ上、何も起こらない
document.write("Local x = " + x ); // 10
document.write("Global x = " + _tmp ); // execScriptの瞬間のグローバルxの残像
}
test(); // 10と50
x++;
test(); // 10と51
hack の内容しだいでは、外の世界の x に影響を与えることすらできるが、逆に、hack がどうあがいてもローカルの x には手出しできない。リンク先の次のコードで、found がグローバルなのは、そのため。hack が found で受け取った情報を関数の残りの部分で使いたい。
_expression = '"' + expression + '"';
hack = 'if(' + expression + ') { ';
hack += ' found++; ';
hack += ' document.write("<p>" + canon(' + _expression + ') );';
hack += ' document.write(" <em>param=" + ' + param + ');';
hack += ' document.write(" , param2=" + ' + param2 + ');';
hack += ' document.write(" , op_code=" + ' + op_code + ' + "<\/em><\/p>");';
hack += '}';
また文字列 hack の構成がやけにもつれているのは、夢の世界で行うほうが見通しが良い足し算を、現実側ですまそうとしてるからだ（文字列 expression の両端に文字としての引用符をつけた文字列 _expression との足し算など）。グローバル変数に格納して「むこう」で整形してもらうこともできるが、param などはループ制御用のごくプライベートな変数であるから、これをグローバルにいじれるようにすると、何かの拍子にわけの分からない副作用で悩むことになるだろう。
直観に反するとも思われる点は、execScript() が関数ではなく、グローバル配列のような、特殊なオブジェクトであると理解すると納得がいくだろう。結果として、異なる関数内の異なる execScript() で解釈される異なる文字列は、実際には、互いに通信できる。
function earth() {
document.write("<p>This is the Earth.<\/p>");
var hack = 'if(typeof(message)!="undefined")'
hack += 'document.write("<p>I got message: " + message + "<\/p>");';
hack += 'else document.write("No message...");';
hack += 'var lonely="Hello, little star.";';
execScript(hack);
}
function little_star() {
document.write("<p>This is the Little Star.<\/p>");
var hack = 'if(typeof(lonely)!="undefined")';
hack += 'document.write("<p>I got message: " + lonely + "<\/p>");';
hack += 'else document.write("No lonely...");';
hack += 'var message="Are you doing fine?";';
execScript(hack);
}
earth();
little_star();
earth();
上の例では、関数 earth と関数 little_star がそれぞれ自分だけのローカル変数 hack を持っていて、execScript にたくす。結果として、 earth と little_star は、非常に遠回りな方法ながら互いに通信を送りあう。最初にearth を呼び出すと、メッセージは無い、と言う。earth は execScript 内で lonely に文字列 "Hello, little star." をセットする。
今度は little_star が呼ばれる。このとき little_star の hack は earth から発信された "Hello, little star." という通信文を認識できる。そして message に文字列 "Are you doing fine?" をセットする。
ふたたび earth が呼ばれたとき、先ほどとまったく同じ hack が解釈されるにもかかわらず、今度はメッセージが届いている、と言って、little_star がセットした message を出力する。
念のためにいうと、execScript() が直接とる引数の文字列は、まったくローカルである。
var a='document.write("outer space")';
function test() {
var a='document.write("inner space")';
execScript(a);
}
test(); // inner space
グローバルであるのは execScript() の引数でなく、 execScript() が引数を解釈したときにそこに意味的に現れる変数のコンテキストだ。
