括弧対応をとる

一瞬必要だったので。corr_tableをいじればどんな組でも可。括弧の交差はダメ。

var corr_table = { '(' : ')', '[' : ']' };
function checkBrackets( t ){
	var stack = [];
	for( var i = 0; i < t.length; ++i ){
		for( var j in corr_table ){
			if( t[i] == j ){
				stack.push( j );
				break;
			} else if( t[i] == corr_table[j] ){
				if( stack.pop() != j ){
					return false;
				} else {
					break;
				}
			}
		}
	}
	return stack.length == 0;
}

ん?はてダってカテゴリつけないとだめなん・・・?

迷路生成器と迷路解き器

 解き器って。

 折角迷路生成器を作ったなら、ソルバ(逃げた)も書いたほうが楽しい。というわけで作った。



例によってこの辺で遊べる


生成はみんな大好き深さ優先、ソルバは普段あまりお目にかかりにくい幅優先。学生のお勉強にはもってこいですね。社会人のやることではない。ない。

加えて、生成器は生成の様子が分かるようにぐりぐり動くように改造されてしまった。
ここまでやったら次はA*か。

コードはびっくりするほど汚い!



どうもhatenaではiframeを日記に突っ込む方法があるらしいのでそれを貼り付けられれば一番いいのだけど、これに限って言えば描画をサボっていてかなり重いのでどの道無理。

迷路生成器

 そんな分野があるなんて。


楽しすぎるぜ。というわけで作った。


このへんであそべる

ごくごく単純な深さ優先探索。recursive backtrackerとかなんだかかっこいい名前で呼ばれている。必殺技みたいだ。
やっぱりこの手のものは視覚的に見えると楽しいなあ。

題名なし

よくあるnext_permutationのサンプル

#include<iostream>
#include<vector>
#include<algorithm>

void printvec( std::vector<int> &v){
        for( int i = 0; i < v.size(); ++i ){
                std::cout << v[i] << " ";
        }
        std::cout << std::endl;
}

int main(){
        std::vector<int> v, e;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        printvec( v );
        while( std::next_permutation( v.begin(), v.end() ) )
                printvec( v );

        return 0;

出力

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

ループを変えてみる

        for( int i= 0; i < 12; ++i ){
                std::cout << std::next_permutation( v.begin(), v.end() ) << " ";
                printvec( v );
        }

出力

1 2 3 
1 1 3 2 
1 2 1 3 
1 2 3 1 
1 3 1 2 
1 3 2 1 
0 1 2 3 
1 1 3 2 
1 2 1 3 
1 2 3 1 
1 3 1 2 
1 3 2 1 
0 1 2 3 

おお、覚えていらっしゃるのか。

複数の数字から3つ選んで三角形になるかどうかを調べるとかいう話

とある本に書いてあったオマケ話。多分こう。

1. ソートして、大きい方からウインドウサイズ3で配列を見る。
2. 一番大きい辺が残りの2辺の和より大きければ三角形を作らない。そうじゃなければ終わり。
3. 一番大きい辺と比べて、次に大きい辺と次の次に大きい辺を取ってきたというのに、それを足しても一番大きい辺にはかなわないんだから、残りの奴らには太刀打ち出来ないだろう。なので諦めて次行ってみよう。

#include <cstdlib>

int cmp( const void *a, const void *b ){ return ( *( int* ) b - *( int* )a ); }
int page21_nlogn( int n, int *a ){
	qsort(a, n, sizeof(int), cmp);
	for( int i=0; i < n-2; ++i ){
		int s = a[i] + a[i+1] + a[i+2];
		if( s - 2 * a[i] > 0 )return s;
	}
	return 0;
}

これならO(n logn)
たのむからバブルソートはしないで。

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世代で動いた!けど画面が足りてない!

Aptana Studio 3とPydevのハイライティング

 IDEマンセー言っている割に、最近コード書くときはもっぱらvimサクラエディタです。こんばんわ。

 そんな僕も時代の流れに乗ってAptana Studio 3を触ってみました。まあ、eclipseaptana 2も触ってはいたわけですが。

 3になって、デフォルトのカラーテーマが黒背景・白文字でとてもよろしいのですが、Pydevと共存させたときに、背景黄色、文字白。見えないよ。
 この設定探すのにすごい時間がかかった。apntanaが悪いわけじゃないんだけど、配色関係の設定は、Preferenceのあちこちに分散しているので探しにくかった。


のでメモ。


Preference -> General -> Editors -> Text Editors -> Annotations -> Occurrence (Pydev )


1時間も探したよ。

HTML5にフル対応させ(たようにみせかけ)る

 HTML5が待ち遠しくて待ち遠しくて、各種ブラウザも徐々に対応はしてきているのだけど、もう待ちきれないよ!とお悩みの紳士淑女の皆様。
そんなHTML5フリークな皆様は、ブラウザのアップデートのたびに、HTML5testでスコアを確かめ、一喜一憂していることでしょう。


 そんなあなたに朗報。HTML5にフル対応させるスクリプト書きました。
すいません嘘ですHTML5にフル対応した気分になれるスクリプトです。


Firefoxさんが、

こんなかんじに、


Operaさんも、


こんな感じに。



 時代の先を行っちゃったぜ。



再現手順

 1.Operaまたはgreasemonkeyの入っているFirefoxを用意
 2.以下のリンクからダウンロード/インストール
 3.HTML5testHTML5フル対応したことを確認する
 3.HTML5testHTML5フル対応したように見せかけられてしまったことを確認する
 4.にやりとする



●ダウンロード
FireFox用
Opera用



●Zipが嫌ならこの辺
userscripts.org


 まあ、つまりはユーザースクリプトです。
本当にすみませんでした。今は反省しています。
怒られるか、飽きたら消します。