2011-04-17

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が脳みそ一切使わなくても作れて楽だからです。

2011-04-12

JavaScriptでDancingLinksアルゴリズムによる数独ソルバを作った

javascript Programming algorithm

　昨今の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が、これまためちゃくちゃ分かりやすいので、こちらも興味があればぜひ。