切符の番号とかナンバープレートの4つの数字と＋−×÷を使って10を作るアレを解いてみる
切符にプリントされている４個の数字とか、ナンバープレートに書かれている４桁の数字を、四則演算のみを使って10にするという遊びあるじゃないですか。
そう、あれ。あれです。誰か名前を付けていてもよさそうなんだけど、特別名前が付いている訳でもなさそうなあれ。
どうも海外では、これと似たようなゲームを出題するTV番組があったらしく、そこからCountdown numbers gameという名前で呼ばれているらしいです。
ルールはもうちょっと複雑で、数字が6個だったり、10にするんじゃなくて、その都度違ったり、時間制限があるとか。
これを計算機で解く場合、おそらく一番単純な方法は、葉ノードが数字、接点が演算子の木を全通り出力 → 評価という流れかと。
そういうわけで、実装してみた。例によってJavaScriptです。
遊び方は見たまんま。
計算したい条件（ナンバープレートの数字と、作りたい10という数字）を入力すると、可能な計算式が全て出ます。4つの数字以上にも対応、途中計算で分数が出てくるものも解として出力します。
大昔に、auの携帯向けのフリーアプリで、まさにこの問題をプレイヤーに解かせるというゲームがあったのですが、困ったことに、自力で解けないときに回答が出てこない（すごいストレス）＆なんか解けそうに無い問題が出てくる（理不尽）という代物で、非常に不満だったのですが、これがあれば万事解決。
これを使えば暇なドライブでどうしても解けないナンバープレートを見つけたときに、「解なし」と自信たっぷりにいえる、その快感に酔いしれること請け合いです。
GWの単調なドライブのお供に是非。
追記
10 puzzle とか Make 10とかいうらしい。解く前にググれ、か。
モンテカルロ法とJavaScriptでπ
これはもう説明が全く不要な、コード書く人なら間違いなく通る、モンテカルロシミュレーションでπの値を計算しようという遊び。
これはとても楽しい。視覚化されると楽しさ10倍。というわけでわりと投げやりにJavaScriptで書いた。
ここであそべる
画像にあるサンプル点は全て1個1個がdivなので、1万サンプルとかやると真面目に死にますので気をつけて。
あと、計算誤差については何も考慮せず作ったので、ある程度の精度以上は出ません。というか、非常に精度が悪い。
電車内で暇に任せてiPod Touchで書いたコードに枝葉を死ぬほどつけたらなんかできたのでとりあえず公開。
迷路生成器と迷路解き器
解き器って。
折角迷路生成器を作ったなら、ソルバ（逃げた）も書いたほうが楽しい。というわけで作った。
生成はみんな大好き深さ優先、ソルバは普段あまりお目にかかりにくい幅優先。学生のお勉強にはもってこいですね。社会人のやることではない。ない。
加えて、生成器は生成の様子が分かるようにぐりぐり動くように改造されてしまった。
ここまでやったら次はA*か。
コードはびっくりするほど汚い！
どうもhatenaではiframeを日記に突っ込む方法があるらしいのでそれを貼り付けられれば一番いいのだけど、これに限って言えば描画をサボっていてかなり重いのでどの道無理。
Three-way quicksortをJavaScriptで書いた。
普通Quick Sortっていうと、ピボットが1つなんだけど、ピボット2つで区間を3分割して考えるのが3-way quicksortです。
分割された区間は、ある値よりも小さいか、同じか、大きいか、で分けられているだけで、それ以外は普通のquicksortです。
例によってJavascriptで書きました。本当に誰得。
さらに例によってデモを作った。
整列の様子を視覚的に分かりやすくたデモを作りたかったのですが、タイムアップで単純にソート前とソート後しか表示されません。
これじゃあ中でバブルソートやっていてもわからない。何のためのデモか。
これだけではうまみがあまり無いのですが、ソートの対象が数字ではなく文字列や配列である場合、3-wayをうまく使ったmultikey quicksortという手法を使うと高速な整列が可能になります。そのあたりはまあ、そのうち。
追記
Multikey-Quicksortは割合ベーシックな話なのでオワコンだと思っていたのですが、昨年、IBIS 2010で東大の鹿島先生のところの学生さんと話した際、だいぶ違う問題に転用していて、認識を改めたのを思い出した。
JavascriptでTrieデータ構造のVisualizationをやってみた
TRIEに対するオペレーションを視覚的に表示する謎のスクリプトを書いた。視覚化、といっても、要するにツリーを作るコンポーネント使っただけ。視覚化しなくてもTRIEは分かりやすいので誰得もいいとこなんですが、それはそれ。
こちらで遊べます =>"Trieのデモ"
見た目は、
こんな感じ。
YUIを使ってみた。牛刀をもって鶏を裂く。
ついでにtrieのコードもはっておく
new function(){ // private var nnodes = 0; Node = function( value ){ this.count = 0; this.value = value; this.leaf = " this.children = []; this.isEmptyWord = function( word ){ return word === undefined || word === null || word === ""; } this.nnodes = 0; //except root node this._insert = function( word, data ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ this.count++; this.leaf = data; return true; } } else { var ch = word[0]; var child = this.children[ ch ]; if( child === undefined ){ this.children[ ch ] = new Node( ch ); child = this.children[ ch ]; ++nnodes; } if( child._insert( word.slice(1), data ) ){ this.count++; return true; } else { return false; } } }; this._remove = function( word ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ return false; } else { this.leaf = null; return true; } } else { var ch = word[0]; var child = this.children[ ch ]; if( child === undefined ){ return false; } if( child._remove( word.slice(1) ) ){ if( child.count == 1 ){ delete this.children[ch]; } child.count--; --nnodes; return true; } else { return false; } } }; this._find = function( word ){ if( this.isEmptyWord( word ) ){ if( this.leaf === null ){ return null; } else { return this.leaf; } } else { var child = this.children[ word[0] ]; if( child === undefined ){ return null; } else { return child._find( word.slice(1) ); } } }; return this; } // public Trie = function(){ this.root = new Node( "/" ); this.insert = function( word, data ){ this.root._insert( word, data ); }; this.remove = function( word ){ if( this.root._remove( word ) ){ this.root.count--; } }; this.find = function( word ){ return this.root._find( word ); }; }; }
↑これは、trieとして必要な部分を抜いただけのものなので、動作確認してませんのであしからず。学校の課題とかには使わないほうがいいと思う。。。
最近jsのエントリが続いているのは、GUIが脳みそ一切使わなくても作れて楽だからです。
JavaScriptでDancingLinksアルゴリズムによる数独ソルバを作った
昨今のJSエンジンはすごい。とにかく速い。3Dとかもやれちゃう。
なんだかもう、前処理はクライアント側でやらせて、サーバはサボっててもいいんじゃないか。
どんなやつでもかかってこいという感じですか。まあ、一部ブラウザは除きますが・・・
そんなわけで、JavaScriptで何か重めの処理走らせてみよう。きっと超絶スピードでサクサクやってくれるはずだ！
というモチベーションの元、数独ソルバをjsで作ってみた。
数独をとかないと世界が破滅するようなシチュエーションで使ってみてください。
↓ここにあります。
http://kogecoo.sakura.ne.jp/scripts/dancing_sudoku.html
恐ろしいことにChromeでしか動作確認をしておりません。
以下駄文
書きなぐってポイ、という感じなので色々と不備があるかもしれません。
検算とか手でやったわけじゃないので、ちゃんと解けているかどうかは保障しません。。。
jQuery使っているのでリッチなブラウザ使ってください。コア部分は多分ECMA 3rdでも通じるくらい何もしていないので、誰か携帯用とか書きたければ書いてください。
数独の解を探すアルゴリズムは、Knuth先生が広告塔をやったDancing Linksというアルゴリズムを使いました。学生のときにJavaで書かされたものを書き直す形で最初はじめたのですが、最終的には原型をとどめていません。
Dancing Linksは、縦方向と横方向に双方向リンクをもつノードを2次元平面状に並べた構造で実現されていて、Exact Coverな問題に対するバックトラッキングの高速化をするアルゴリズムと知られていると僕は記憶しています。細かい話は元論文が非常に分かりやすいので、興味があればぜひ。
また、数独のExact Coverとしての解釈はWikipediaが、これまためちゃくちゃ分かりやすいので、こちらも興味があればぜひ。
ちなみにDancing Linksをwebを探すと実装がかなりたくさんあります。ちょっと前は全然無かったんだぜ…
java, c, c++, python, haskell...適用先として面白いんでしょうね。。。
追記
ipod touchの第4世代で動いた！けど画面が足りてない！
HTML5にフル対応させ（たようにみせかけ）る
HTML5が待ち遠しくて待ち遠しくて、各種ブラウザも徐々に対応はしてきているのだけど、もう待ちきれないよ！とお悩みの紳士淑女の皆様。
そんなHTML5フリークな皆様は、ブラウザのアップデートのたびに、HTML5testでスコアを確かめ、一喜一憂していることでしょう。
そんなあなたに朗報。HTML5にフル対応させるスクリプト書きました。
すいません嘘ですHTML5にフル対応した気分になれるスクリプトです。
Firefoxさんが、
こんなかんじに、
Operaさんも、
こんな感じに。
時代の先を行っちゃったぜ。
再現手順
１．Operaまたはgreasemonkeyの入っているFirefoxを用意
２．以下のリンクからダウンロード／インストール
３．HTML5testでHTML5フル対応したことを確認する
３．HTML5testでHTML5フル対応したように見せかけられてしまったことを確認する
４．にやりとする
●Zipが嫌ならこの辺
userscripts.org
まあ、つまりはユーザースクリプトです。
本当にすみませんでした。今は反省しています。
怒られるか、飽きたら消します。
