題名なし

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


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

greasemonkeyでグローバルスコープの汚染をしたい

 表題がおかしい。


 greasemonkeyスクリプトはブラウザで表示しているwindowのスコープとは別なスコープで動きます。
これは、greasemonkeyスクリプトで使用している名前と、サイト側で使っているjavascriptの名前が衝突しないようにするための工夫ですね。
逆に、サイト側の名前空間を汚染したいよう、というときはどうすればいいんだろう。

with( unsafeWindow ){}


これでscriptを囲むだけ。unsafeWindowって名前すごいね。


Operaのユーザースクリプトの場合は不要みたい。それもどうなんだろう。

documentオブジェクトの挙動を変える

 あー、getElementByIdの動作変えたいなーとか、createElementの動作変えたいなー、という要求は多いかと思います。あ、javascriptの話ですよ。
 そんな変テコなことを考えるあなたにはこれ。インスタントdocument wrapping、もしくはdocumentのプロパティの上書き。そのまんま。


 どうするかっていうと、documentのオリジナルのプロパティをそのまま上書きするだけ。ただ、既存の動作も残したい場合はちょっと面倒。


 所望のプロパティのオリジナルを一時的に保存し、上書きする。意図としてはthisがdocumentなので、callでdocumentを指定。


 こうすることで、わりと直感的なdocumentのオーバーライドモドキができます。
以下はdocument.createElementでdivを作ろうとするとspanができて、spanを作ろうとするとdivができるという、ヘンチクリンなコード。オーバーライドでやっちゃいけないことの代表例w

var temp = {}
temp.createElement = document.createElement;
document.createElement = function( arg ){
	switch( arg ){
		case 'div':
			return temp.createElement.call( document, 'span' );
			break;
		case 'span':
			return temp.createElement.call( document, 'div' );
			break;
	}
	return temp.createElement.call( document, arg );
}
</html>


window.documentでも同様なことができる(はず)


HTMLのサンプルはこちら。

<html>
	<head>
	</head>
	<body>
		<div id="foo"></div>
		<script type="text/javascript">
			var temp = {}
			temp.createElement = document.createElement;
			document.createElement = function( arg ){
				switch( arg ){
					case 'div':
						return temp.createElement.call( document, 'span' );
						break;
					case 'span':
						return temp.createElement.call( document, 'div' );
						break;
				}
				return temp.createElement.call( document, arg );
			}

			document.getElementById( 'foo' ).appendChild( document.createElement( 'div' ) );
		</script>
	</body>
</html>


見た目には変化ないですが、先述した動作をしとります。domインスペクタで見ると良いかと。
使い道は全く不明ですが。


こんなヘンテコな遊びに付き合ってくれた友人に感謝。

スマートフォンへの懸念

 特に日本では、だと思うのだけど、これまでの携帯電話のブラウザと同じような感覚で
みんなiPhoneとかAndroidフルブラウザ使っている(あたりまえだ)。
これにちょっと警鐘を。今更僕が言うまでもないのですが。


 わりと最近認識されてきたっぽいですが、セキュリティ面でかなり懸念があります。
正確には、バージョンの古さが問題なのです。まあ当たり前ですが。
そりゃあ当たり前で、バージョンアップにはバグフィックスも含まれている、
逆に言うと新しいバージョンがリリースされたときには、古いバージョンにあった、
問題が認知されてしまっているわけです。セキュリティ面も含めた、です。


 組み込み機器はアップデートのしにくい世界、これはかなり致命的になるわけです。
Androidで言えば、メーカーのアップデートの頻度等をみるとわかるかと思います。
コストすごいしね。


 そんなわけで、脆弱性を抱えた端末は、巷にゴロゴロ転がっていて、
たとえばWebKitで過去に認知された問題等を突けば攻撃できる、
というような状況に既になっているような気がします。
それについては、iPhoneにしても状況は全く一緒だと思います。


 たとえばAndroid ver.x向け攻撃コード、なんてのがこういうのが認知された瞬間作られてしまうわけですよね。
 ここまで言えば、「あー、今あれが狙い目だなー」とかみんな考えるんじゃないでしょうか?


 これまでのガラケーは、わりとクローズドなコンテンツの世界だったり、
jsがまともに動かなかったりで、逆に助かって(?)いたのだけど、時代はフルブラウザ


 スマートフォンブームに乗ろうと日本のキャリアも熱心ですが、そのあたりは握りつぶしているんでしょうか。
結局ユーザーが気をつけるしかないっすかね。


 実はセキュリティパッチだけは頻繁に自動であてていたり?なんていう期待をしちゃあいけないような気がします。


 スマートフォンもってないんですけどね、僕。