MetropolisサンプラーをHTML5のcanvasで描いてみる

algorithm javascript Programming

MCMCの中でもGibbs samplerと並んで有名なMetropolis samplingをjsでやってみる。
HTML5のcanvasを使って視覚化もしてみる。


このへんであそべる

赤いところがAcceptされたサンプル、青いのがRejectされた動き
moreで1ステップとか2ステップづつ進むとニョロニョロ動いて楽しい。


対象は相関のない2変量ガウス（正規）分布。
乱数生成器はMath.random()なので、本当はサンプラーに使うべきではないですが、どの道モックなので気にしない。

切符の番号とかナンバープレートの4つの数字と＋−×÷を使って10を作るアレを解いてみる

algorithm Programming javascript

　切符にプリントされている４個の数字とか、ナンバープレートに書かれている４桁の数字を、四則演算のみを使って10にするという遊びあるじゃないですか。

そう、あれ。あれです。誰か名前を付けていてもよさそうなんだけど、特別名前が付いている訳でもなさそうなあれ。


　どうも海外では、これと似たようなゲームを出題するTV番組があったらしく、そこからCountdown numbers gameという名前で呼ばれているらしいです。
ルールはもうちょっと複雑で、数字が6個だったり、10にするんじゃなくて、その都度違ったり、時間制限があるとか。


　これを計算機で解く場合、おそらく一番単純な方法は、葉ノードが数字、接点が演算子の木を全通り出力　→　評価という流れかと。
そういうわけで、実装してみた。例によってJavaScriptです。



このへんであそべる


　遊び方は見たまんま。
　計算したい条件（ナンバープレートの数字と、作りたい10という数字）を入力すると、可能な計算式が全て出ます。4つの数字以上にも対応、途中計算で分数が出てくるものも解として出力します。



　大昔に、auの携帯向けのフリーアプリで、まさにこの問題をプレイヤーに解かせるというゲームがあったのですが、困ったことに、自力で解けないときに回答が出てこない（すごいストレス）＆なんか解けそうに無い問題が出てくる（理不尽）という代物で、非常に不満だったのですが、これがあれば万事解決。


　これを使えば暇なドライブでどうしても解けないナンバープレートを見つけたときに、「解なし」と自信たっぷりにいえる、その快感に酔いしれること請け合いです。


　GWの単調なドライブのお供に是非。




追記

　10 puzzle とか Make 10とかいうらしい。解く前にググれ、か。

モンテカルロ法とJavaScriptでπ

javascript algorithm Programming

　これはもう説明が全く不要な、コード書く人なら間違いなく通る、モンテカルロシミュレーションでπの値を計算しようという遊び。
これはとても楽しい。視覚化されると楽しさ10倍。というわけでわりと投げやりにJavaScriptで書いた。



ここであそべる



画像にあるサンプル点は全て1個1個がdivなので、1万サンプルとかやると真面目に死にますので気をつけて。
あと、計算誤差については何も考慮せず作ったので、ある程度の精度以上は出ません。というか、非常に精度が悪い。


電車内で暇に任せてiPod Touchで書いたコードに枝葉を死ぬほどつけたらなんかできたのでとりあえず公開。

括弧対応をとる

雑記 Programming

一瞬必要だったので。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;
}

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

迷路生成器と迷路解き器

algorithm javascript Programming

　解き器って。

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



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


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

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

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



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

迷路生成器

javascript algorithm Programming

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


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


このへんであそべる

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

題名なし

C++ 雑記

よくある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

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

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

C++ algorithm Programming

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

1. ソートして、大きい方からウインドウサイズ３で配列を見る。
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)
たのむからバブルソートはしないで。