2010-04-24

チームラボ天下一武道会

チームラボ主催、今回で4回目、社外の方の参加を募るようになってからは2回目のプログラミングコンテスト「天下一武道会」に参加しました。今回は遠いお茶とみかんの県からリモート参加をしました。

課題は「オセロボットをつくれ！」そうはいっても、8x8のいわゆる「リバーシ」だけでなく、ところどころ置けないマスや変形盤面があるなどエクストリームなルールです。それだけではありません。自分の石の数が相手の1/5以下になったときに、ゲーム中1回だけ発動できる「全ての石をひっくり返す」という革命的な必殺技をルールに盛り込んだ、まさにX-Gameでした。定石もよく分からない中、これを1手あたり平均2秒で処理するbotを、3時間一本勝負で作らなければなりませんでした。しかも、作ったアプリケーションはWebからAPIを叩ける形にしなければなりません。

最初はEclipseのサーバーでいいかと思いましたが、作業場所は大学の研究室。大学のゲートウェイが通過できなかったので、GAE/Jを使うことにしました。パフォーマンスがよく分からない中、処理時間はどうか、転送量はどうか…などいろいろな不安点を抱えた中開発は進んでいきました。

取り急ぎソース。

クラス本体

大会のときに使ったソースはあまりに汚いので、書き直しました。
かなりいい加減だったし、冗長だったと思います。x-y座標を間違えてパッチワーク的に直した部分もありますし、角判定は4近傍しか見ていませんでした。

package net.dolpen.www.reverse;



public class Board {
	private int[][] bd = null,cl = null;
	@SuppressWarnings("unused")
	private int max_x,max_y,out_x,out_y,c_w=100,stat = 0;
	Board(String s,int r){
		Init(s);
		this.stat=r;
		Clone();
	}
	public void Init(String sin){
		String[] l=sin.split("\\.");
		max_x=l[0].length();max_y=l.length;
		out_x=max_x+2;out_y=max_y+2;
		bd=new int[out_y][out_x];
		cl=new int[out_y][out_x];
		for(int i=0;i<max_y;i++){
			for(int j=0;j<max_x;j++){
				switch(l[i].charAt(j)){
					case '0':bd[i+1][j+1]=0;break;
					case 'P':bd[i+1][j+1]=1;break;
					case 'E':bd[i+1][j+1]=2;break;
					default:bd[i+1][j+1]=3;
				}
			}
		}
		for(int i=0;i<out_y;i++)bd[i][max_x+1]=bd[i][0]=3;
		for(int j=0;j<out_x;j++)bd[max_y+1][j]=bd[0][j]=3;
	}
	private void Clone(){for(int i=0;i<out_y;i++)for(int j=0;j<out_x;j++)cl[i][j]=bd[i][j];}
	private boolean isCorner(int y,int x){x+=1;y+=1;return (!(bd[y][x+1]!=3 && bd[y][x-1]!=3) && !(bd[y+1][x]!=3 && bd[y-1][x]!=3) && !(bd[y+1][x+1]!=3 && bd[y-1][x-1]!=3) && !(bd[y+1][x-1]!=3 && bd[y-1][x+1]!=3));}
	public String Search(){
		int t,n=1000000,x=-1,y=-1;
		for(int i=0;i<max_y;i++){
			for(int j=0;j<max_x;j++){
				if((t=Count(n,i,j))==-1)continue;
				if(isCorner(i,j))t-=c_w;
				if(n>=t){n=t;x=j;y=i;}
			}
		}
		System.out.println(n);
		return y+","+x;
	}
	private int Count(int n,int i,int j){
		if(PutAll(i,j)<=0)return -1;
		int t=0;
		for(int p=0;p<max_y;p++){
			for(int q=0;q<max_x;q++){
				if(ReSeekAll(p,q)){
					t+=((isCorner(p,q))?c_w:1);
					if(t>n){Clone();return -1;}
				}
			}
		}
		Clone();
		return t;
	}
	private boolean ReSeekAll(int y,int x){
		for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++)if(i!=0||j!=0)if(reSeek(y+1,x+1,i,j)>0)return true;
		return false;
	}
	private int PutAll(int y,int x){
		int n=0;
		for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++)if(i!=0||j!=0)n+=Put(y+1,x+1,i,j);
		if(n>0){cl[y+1][x+1]=1;n++;}
		return n;
	}
	private int Put(int y,int x,int sy,int sx){
		if(cl[y][x]!=0)return 0;
		int n=-1;do{x+=sx;y+=sy;n++;}while(cl[y][x]==2);
		if(cl[y][x]==1){while(cl[y][x]!=0){cl[y][x]=1;x-=sx;y-=sy;}return n;}
		return 0;
	}
	private int reSeek(int y,int x,int sy,int sx){
		if(cl[y][x]!=0)return 0;
		int n=-1;do{x+=sx;y+=sy;n++;}while(cl[y][x]==1);
		return (cl[y][x]==2)?n:0;
	}

}

サーブレット

オーシンプルネー

package net.dolpen.www.reverse;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.*;

@SuppressWarnings("serial")
public class ReverseServlet  extends HttpServlet {
	@Override
	protected void doGet(HttpServletRequest req, HttpServletResponse res) throws ServletException,IOException {
		Board b = new Board(req.getParameter("board"),Integer.parseInt(req.getParameter("reverse")));
		res.setContentType("text/html; charset=UTF-8");
		PrintWriter out = res.getWriter();
		out.println(b.Search());
		out.close();
	}
}

感想

「革命」については「出場者は並みいる強豪なので、大差をつけられて負けることはあっても、こっちが革命されて痛くなるような場面はない」とか想定して、かなり適当な処理をしてあります。ほぼ使わないのと同義でしょう。
あと、数手先を読むなどの深い探索では、かかった計算時間に対してパフォーマンスがそれほどでないだろうと思い「そこに打ったら相手はどれくらい多くの場所におけるか、その中で危険な角(隅)はどれくらいあるか」というのをテーマにしました。うまくはまってくれたようです。
そんなこんなで1位を獲得できたので、とてもうれしかったです。次回があれば是非参加したいと思います。最後に、チームラボの皆様、ならびに参加者の皆様、本当にお疲れ様でした。

おまけ

そんなアルゴリズムですが、サンプル2(リバースを狙う夫)に負けます。
僕もこんなことは許されない、あってはならないと思いました。次回以降はこんなことにならないように頑張りたいです。

2009-06-09

dolpen

ジャレコが再生プロジェクトでRPG作るんで敵モンスター募集するぞ、と表明したので、自分が普段あまり使っていないアイコンを軽い気持ちで投げてみた。

これは縮小版：私のフォトライフには仲間っぽいのがいっぱいいますが、それらは色とか違うし別物です、ということにしておく。

今は亡きLinux-Zaurusのペイントソフトで書いた、最初で最後の作品だったりする。だから元画像は縦書きVGAなわけです。精度が悪くがたがただけど、上のように縮小すれば見栄えが悪くないのと、採用時にドッターが何とかしてくれるという文面を見て、どうせだめだろうけどネタという名の思い出や、少々の売名になればいいやとかそういう不純な気持ち満載で投稿。

http://www.jalecogames.co.jp/rebirth/therpg/monster/list.html

気がつくとかなりいい位置にいたので説明文をまじめに書き直す。某クエストの某スラ仏のような位置づけだったらいいよね、という感じで。

んで今日見てみたらものすごい勢いで延びていたのでページを開いてみると、社員だ不正だ、と書いてあっていろいろと凹んだ。よくわからないけどスーパーﾊｶｰみたいなのがいるらしいのか？これ以上こんなこといわれたら、私のガラスでできたハートが砕け散ってしまいそう。いぢめないで。周りの人がそれでも面白いと励ましてくれるので、まあこのままじっくりとフェードアウトしていってもいいんじゃないかなー、とも思う。

個人的にはウサニンジンがかわいいと思う。よくid6番の速さであんなに丁寧に書けるな、とも思った。その技術の1%でもいいからほしいですね。ともあれ、ジャレコの皆様にはゲーム作成をがんばっていただきたい。<<追記>>社長がツールなどの投票方法に情熱を感じるそうなので、6/10の時点で不正だなんだと叩いてる人たちに対して、そんなに不正してほしいなら本当の情熱を見せてやろうというのも考えていましたが、ツール(スクリプトでなく)ができた時点で満足してしまって、どうでもよくなって消したので、結局なにもしてない。Vipあたりで祭りが勃発したら気が変わるかもしれませんけどね。などと燃料投下して売名してみる。今は傍観。<<さらに追記>>ドルペンの名前の由来なんですが、もともとは頭の部分がちょうどシロイルカのように、くちばしが柔らかい感じのイメージがあったのでイルカとペンギンを足した安易な命名にしました。なんという適当さ。

2009-05-17

GENOウィルスのチェックプログラム(簡易版)を書いてみた

Vista使いでUAC厨の私には全く関係の無い話のような気がするが、いつUACを突破する亜種が出るかは分からない。sqlsodbc.chmのファイルサイズで判定できるようなので、そんなときのためにこんなバッチファイルを書いてみた。以下のプログラムをテキストファイルにコピペして、拡張子をbatにしてダブルクリックで実行すれば、コマンドを勝手に実行し、最後にレポート書いて停止するものだ。有効利用してください。あと、バッチに関しては素人なので改造してくれるとうれしいなぁ。
ttp://3rd.geocities.jp/tdnskbn/dat/genochecker.zip<追記>最新版はこのソースの原型くらいしかのこってないくらい変わってます。容量が大きく見づらいのでzipから入手してください。直接リンクできないのでアドレスバーにペーストしてください。
sqlsodbc.chmをいじらない亜種が出ているという未確認情報があるんで、そいつは検出できないと思う。とりあえず94.247.*.*をブラウザとセキュリティソフトで弾いて様子を見るしかなさそうだ。情報が来たらまたスクリプト書き直すかもしれない。これってJSRedir-Rって名前だったよね･･･GENOで定着しちゃったけど。

2009-05-09

ケブンッリジだがいく

いんろなところでみけかるよなっにうて
ちょっとおしろもいとおもったので
ぶしょんうのたんごのもじをラダンムになからべえる
プラログムをつくってみたよ。

http://3rd.geocities.jp/tdnskbn/misc/shuffle.htm

にせんばんじおさつれかまですか？

10分でできた。日本語を並べ替えるときは、「ちょっ」や「しゃ」などの組み合わせをばらばらにしないほうが自然だと思ったので、それらを1セットとして扱うようにしたところが、優れてるかは別として、別のジェネレータと違う点であるかもしれない。

だから実は「ケンブリッジ」をこのジェネレータで並べ替えても「ケブンッリジ」にならないから、タイトルに偽りがあるような気もするけどねー

（追記）この記事を最初に書いたとき、間違えて原文を書いてしまったのは秘密。

2009-03-28

さよなら回転体-Ideapad S10eをSSDに換装する-

Lenovoに直接S10eを注文したはいいものの、配送目安を過ぎても全く音沙汰がないどころか、実際に届く数日前に購入後アンケートが届くなど、明らかにケンカ売られてるような対応でやきもきしている間に、安売りで32GBのSSDと2GBのメモリを衝動買い。いろいろな妄想をしているとやっとのことで本体が到着したので早速いじることにした。

ideapadのSSD換装の記事では、だいたいTrueImageなどのディスククローン機能を使っているようだが、残念なことに私はソフトを持っていない。これだけのためにソフトを購入するのも馬鹿みたいなので、すべてをUbuntu上で行うことにした。私は異常な自信家なので、この作業をするにあたってHDDのバックアップを取っていない（本当はバックアップ用のHDDのGセンサが壊れて、自分自身の動作振動で自動停止を繰り返して使えなかったため）が、もしこの記事を見て同じことをする場合は絶対にバックアップを取ってほしい。なお、この記事は成功を保証するものではない。自己責任で試してもらいたい。

必要なものはUbuntu8.10(Verは違ってもいいかもしれない)のLiveCDとCDドライブ、SATA->USBのHDDケースだけ。私は以前に作ったLiveUSBがあるのでそれを利用した。そのうち大容量のSSDに換装したくなるに決まっているので、そのためにも以下に方法を記しておくことにする。

Ubuntuをブートして、そこからGPartedを起動する。
Windowsの入ったNTFS パーティションをSSDの容量より少し小さめに縮小する。縮小していた部分はそのままでも、図のように新しいパーティションを切ってもいい。右端にリカバリ領域があるが、SSDの容量によっぽどの余裕がない限りは移さなくてもいいだろう。

このときハードディスクの先頭に未フォーマット領域っぽいものがある。これが非常にネック(後述)。こいつのせいで実は何時間もの時間を無駄にしたのだがそれはまた別のお話。

先頭から512bytes*16065セクタ空けて(HDDと同じように)パーティションコピーする。必要ならコピー先パーティションの後ろの部分を拡張してSSDを無駄なく使えるようにしてしまおう。

最終的にこうなっていればよい。GUIのアプリケーションはとっても楽だ。

GPartedの作業はここまで。次にターミナルを起動しての作業になる。ddで細かい作業をするので、各コマンドの実行前後にはよく確認、熟考すること。

まず、HDDからSSDにブートストラップローダを移す。
sudo dd if=/dev/(HDD) of=mbr.bin bs=512 count=1
sudo dd if=mbr.bin of=/dev/(SSD) bs=446 count=1
447バイト目以降はSSDのパーティションテーブルなので、上書きしないように注意。

さて、謎の16065セクタだけれども、ここはブートストラップローダが読み込む拡張領域らしい。起動時に出てくる「リカバリはF11を押せ」などのメッセージ表示もここに入ってるみたい。詳しくはバイナリ読んでみないとわからないけど。ともかく、ここもちゃんと移植しないことにはうまく起動しないようである。

では、SSDの第一セクタ、ブートストラップローダ+パーティションテーブルのバックアップを取っておく。
sudo dd if=/dev/(SSD) of=mbr2.bin bs=512 count=1
次に、HDDの0から16064セクタまでをSSDに移す。
sudo dd if=/dev/(HDD) of=/dev/(SSD) bs=512 count=16065
これだと、パーティションテーブルがHDDのものになってしまうので、さっきのバックアップをもう一度上書き。
sudo dd if=mbr2.bin of=/dev/(SSD) bs=512 count=1
要するに、HDDの0から16064セクタまでのうち、パーティションテーブル以外ををSSDに移すことになるわけだ。
念のため、mbr.bin(HDD用)とmbr2.bin(SSD用)はUSBドライブか何かに保存しておくとよい。

Ubuntuをシャットダウンし、内臓HDDをSSDに換装して電源投入、チェックディスクが走って再起動されれば終了。おめでとう。HDDのバックアップをとっているなら別の何かに流用してもいいし、していないのならSSD リカバリ用として大切に保管しておこう。下手するとメーカーからリカバリメディアを高いお金で購入する羽目になる。

lenovo quickstart 終了から30秒程度でXPが起動する。加えてメモリも2GBにし、512MBをRamdiskにし、ブラウザのキャッシュやテンポラリ領域をここに指定した。体感速度は恐ろしく早く、ブラウジングもとても快適である。携帯時や使用中の振動も気にしなくていいことと、省電力や静音性も良くなったので非常に満足である。

追記：ベンチマーク

もとのHDD(5400rpm/160GB)
シーケンシャル R55.81/W51.10
ランダム512k R26.94/W24.33
ランダム4k R0.471/W0.992

TS32GSSD25S-M
シーケンシャル R114.6/W78.39
ランダム512k R107.3/W44.57
ランダム4k R11.31/W1.773

JM800QSU-2GのRamdisk
シーケンシャル R766.7/W776.0
ランダム512k R665.7/W621.9
ランダム4k R24.74/W23.43

CrystalDiskMark 試行5回/100MB(MB/s)

全体的に貧乏臭い記事でごめんなさい。
(追記:結構キーワードで飛んでくる人が多いので、図をいくつか入れてみました。後撮りなのでちょっとアレだけれども…)

2009-02-01

Googleの全危険指定を解呪するスクリプト

取り急ぎ

検索したらアドレスバーに

javascript:(function(){a=document.getElementsByTagName("a");for(var i=0;i<a.length;i++){a[i].setAttribute("href",a[i].getAttribute("href").split("http://www.google.co.jp/interstitial?url=").join(""));}})()

をアドレスバーに貼り付けてエンター
グリモンは知らないから誰かよろしく。<追記>再現用スクリプト。あくまで形だけ。

javascript:(function(){document.getElementsByTagName('nobr')[1].firstChild.innerHTML="";a=document.getElementsByTagName("span");for(var i=0;i<a.length;i++){if(a[i].className=="m")a[i].innerHTML="";}b=document.getElementsByTagName("h3");for(var i=0;i<b.length;i++){if(b[i].className=="r" && (b[i].innerHTML.indexOf(">のニュース検索結果",0)==-1))b[i].innerHTML+="<br><a href='#' style='font-size:small;'>このサイトはコンピュータに損害を与える可能性があります</a>";}})()

2008-12-31

Ubuntuの、ちょっと変わったLiveUSBをつくってみた

手元に8GBのUSBメモリがあったので、気軽に使える環境でも作ろうと思い、Ubuntuを導入することを考えた。ちょうど8.10の日本語リミックスCDというものができたらしいので、それを使ってみることにした。
CDからブートし、パーティションを切っていく。8GBのうち、前6GBをWindowsから参照できる共有ストレージ部分、1GBをOS部分、一番後ろの1GBを設定保存などの部分に当てることにした。
LiveUSBを作れるウィザードができたらしいので使ってみると、これはOSのパーティションの空き部分を、設定保存領域としてファイルで確保できるそうな。何となくOS本体と同じパーティションに読み書きする部分を作りたくなかったので取り合えず領域の確保をしないでLiveイメージを2番目のパーティションに作成した。
その後、3番目のパーティションに「casper-rw」のラベルをつけてext2でフォーマットし、再起動。もちろん再起動時にはpersistentオプションを付け足すことを忘れない。日頃の行いが良かったのか、正しく設定保存用のパーティションが正しいところにmountされていた。
毎回起動時にオプション追加するのもだるいので、/cdrom/syslinux/text.cfgを編集。新らしくラベルを設定し「casper-rwを適用してLiveイメージから起動するよ」という意味の英語メッセージ（恥ずかしくて書けないが）とともにブートオプションを設定してデフォルトにする。日本語ファイルも合わせて変えたかったが変な（制御用）バイナリがくっついているテキストなので面倒になりやめた。

そんなこんなで、しっかり起動して使える。以前のように「USBドライブにインストール」するわけではないので、別のPCでも使える（はずだ/未確認）し、誰かにちょっと使わせてあげる時も、ブートオプションを選ぶことで自分の環境をいじらせることなく貸せるので、多分便利だと思う。データが壊れても、OS部分と一緒にフォーマットしなくていいので、自力復帰ができる。唯一の不安要素は、設定保存用のext2のパーティションが壊れやすそうなことだけれども…

だいぶ長く使えそうなものになったので、こうして作り方をメモしておいて、大事に使おうと思う。