MetropolisがGibbsと並んで有名って言うなら、Gibbsもやってみなければいけない。 というわけでやってみた。 ここであそべる おおー。たのしい。 ただ、無相関の2変量ガウスでこれをやっても楽しさ半減ですね…

MCMCの中でもGibbs samplerと並んで有名なMetropolis samplingをjsでやってみる。 HTML5のcanvasを使って視覚化もしてみる。 このへんであそべる赤いところがAcceptされたサンプル、青いのがRejectされた動き moreで1ステップとか2ステップづつ進むとニョロ…

切符にプリントされている４個の数字とか、ナンバープレートに書かれている４桁の数字を、四則演算のみを使って10にするという遊びあるじゃないですか。そう、あれ。あれです。誰か名前を付けていてもよさそうなんだけど、特別名前が付いている訳でもなさそ…

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

解き器って。 折角迷路生成器を作ったなら、ソルバ（逃げた）も書いたほうが楽しい。というわけで作った。 例によってこの辺で遊べる 生成はみんな大好き深さ優先、ソルバは普段あまりお目にかかりにくい幅優先。学生のお勉強にはもってこいですね。社会人の…

そんな分野があるなんて。 楽しすぎるぜ。というわけで作った。 このへんであそべるごくごく単純な深さ優先探索。recursive backtrackerとかなんだかかっこいい名前で呼ばれている。必殺技みたいだ。 やっぱりこの手のものは視覚的に見えると楽しいなあ。

とある本に書いてあったオマケ話。多分こう。1. ソートして、大きい方からウインドウサイズ３で配列を見る。 2. 一番大きい辺が残りの２辺の和より大きければ三角形を作らない。そうじゃなければ終わり。 3. 一番大きい辺と比べて、次に大きい辺と次の次に大…

普通Quick Sortっていうと、ピボットが1つなんだけど、ピボット2つで区間を3分割して考えるのが3-way quicksortです。 分割された区間は、ある値よりも小さいか、同じか、大きいか、で分けられているだけで、それ以外は普通のquicksortです。 例によってJava…

TRIEに対するオペレーションを視覚的に表示する謎のスクリプトを書いた。視覚化、といっても、要するにツリーを作るコンポーネント使っただけ。視覚化しなくてもTRIEは分かりやすいので誰得もいいとこなんですが、それはそれ。 こちらで遊べます =>"Trieのデ…

昨今のJSエンジンはすごい。とにかく速い。3Dとかもやれちゃう。 なんだかもう、前処理はクライアント側でやらせて、サーバはサボっててもいいんじゃないか。 どんなやつでもかかってこいという感じですか。まあ、一部ブラウザは除きますが・・・ そんなわけ…

以前、スペルミスや「もしかして」系の機能の裏で動く技術としてわりと知られているLevenshtein距離についてちょっと書いてみました。 今回はそれと同様な用途に用いられがちなJaro-Winkler距離。 Jaro-Winkler距離というのは、Levenshtein距離同様に文字列…

某所のパズルでまさにこれを使う問題が出たので2年ぶりくらいに実装してみる。 ●レーベンシュタイン距離 ２つの文字列があるとき、片方からもう片方に変換したい。 文字の置換・挿入、削除の３つの操作が可能なとき、一連の操作の最も少ない回数のこと。 Goo…

大昔に買ったはいいものの，全然読んでいなかったSegiwickのAlgorithm in Cをぱらぱら見てて思ったんですが， 日本語第1巻で，ユークリッドの互除法に触れてますよね． ユークリッドの互除法って，gcd(a, b)なら n_0 = a mod b n_1 = b mod n_0 n_2 = n_0 mo…

まあ要は必要になったから，勉強がてらソートのアルゴリズムを実装しまくっているんですね． というわけでおまけ． template<class T> void Sort<T>::insertion_sort(T target[], int length) { T key = 0; for(int i=1; i<length; ++i) { key = target[i]; int j=i-1; while(j>=0 && target[j] > key) { target[j+1] = target</length;></t></class>…

ちょっと分けあってソートについて調べています． いやはや，奥が深いんですな． 僕は中の下程度の知識しか無いし，今更そんなもん必要じゃないだろと思って大した勉強をしたことが無いんですが． これまでbubble, insertion, selection, quick, heap, shell…

三角形の行列を下にたどり，通った数字の最大値を求める． ご丁寧に，問題18では行列が小さいからbrute forceでもいけるけど， 問題67は同じ問題だけど行列がでかいからキツイぜ，とか書いてある． これは面白い．当然一般的な解法をここで考えて二つとも解…

とか何とか言って（16番の続き），17番． one, two, three...one thousandまでの文字数をカウント． うっわ，ひどい．問題も，僕のコードも． natural f17() { natural sum = 0; map<int, int> lnum; map<int, int> part; part.insert(make_pair(1, 3)); //one part.insert(make_</int,></int,>…

Project Euler，一体何のマラソンなんだかよく分からなくなってきました． 16番は2の1000乗の各桁を足すというもの． Cとかだと組み込み型ではオーバーフローするから工夫が必要だよね，とかそういうことなのかなぁ？ 微妙に出題の意図が分からない． きっと…

Project Eulerというサイトがあるらしい． 要は，数学チックな問題がいっぱいあって，プログラミングして解きましょうという問題集のサイト． PKU Judge Onlineみたいな感じです． こういうのハマるので困ります． 自分は低脳なので一つ一つ解くのに時間が掛…

三角数で約数が500より多い（つまり5001以上）ものはいくつ？ まあ，三角数を求めるところは工夫の余地無い気がしますが， 約数を探すところで，ナイーブに1から順番に割れるかどうか？みたくやったらすごく遅くて回答出る前にこっちの我慢の限界． 最適化す…

普通，変数x, yの中身を交換しようとした場合，テンポラリ変数を使って int x=1, y=2, temp; temp = x; x = y; y = xというようにするしかないとずっと思っていた．ところが世の中にはXOR trickというものがあるらしい． x^=y; (1) y^=x; (2) x^=y; (3)なん…