Hatena::ブログ(Diary)

satoru.netの自由帳 このページをアンテナに追加 RSSフィード

100929Wedday

[]gdd2010レポ@devquizの解説資料

まとめ

  • 中の人は半年前からdevquizの準備をしていたらしい
  • pacmanの元ネタ公募で投稿されたものを参考に、googlerがアレンジしたもの。最短経路では簡単すぎたので難しくしたらしい。
  • しりとりはロジックで解くのを想定してたが、何も考えないで連続アクセスして解く奴(俺)対策で、リトライ回数の制限とかを後から導入したらしい
  • 経路最適化は『鷲宮神社(らきすたの聖地のあれ)』をネタで入れていた。実際には他にもいろんなネタを仕込んでたけど、最終的に絞られた。
  • pacmanは『中国人郵便配達問題(Chinese postman problem)』という最短経路を求めるロジックで解くとエレガントらしい。
  • (でも今回のケースでは敵とかいるし、単純に最短ルートを求めるだけでは無理じゃねとかおもった)
  • pacman lv1の最高得点は41。325人が41点だった。
  • pacman lv2の最高得点は265、261、259、258の順。
  • pacman lv3の最高得点は581、578、552、554、553の順。
  • (TwitterのTLで@tet_rwさん581点の人の動作は公開されてた。会場では、具体的な最高得点の人の動きの解説はなし)
  • pacman lv3の1位〜3位は手動(シュミレーター作成派)で、他は自動探索派と言っていた。自動探索の人はすごす!と、googlerの人も褒めていた。
  • 質疑応答で『pacman lv3の解は最短か』との質問にgooglerは『まだ縮めれるかも』とか言ってた(けど、確証はなさそうだ)
  • 以下、資料の写真。本資料はgoogle.com/a/google.com/

全体の解説

f:id:satoru_net:20100928182920j:image

f:id:satoru_net:20100928182719j:image

f:id:satoru_net:20100928182804j:image

Auth

f:id:satoru_net:20100928183054j:image

経路最適化

f:id:satoru_net:20100928183138j:image

f:id:satoru_net:20100928183258j:image

しりとり

f:id:satoru_net:20100928183310j:image

f:id:satoru_net:20100928183422j:image

f:id:satoru_net:20100928183427j:image

f:id:satoru_net:20100928183445j:image

pacman

f:id:satoru_net:20100928183513j:image

f:id:satoru_net:20100928183604j:image

f:id:satoru_net:20100928183628j:image

f:id:satoru_net:20100928183642j:image

f:id:satoru_net:20100928183730j:image

f:id:satoru_net:20100928183735j:image

f:id:satoru_net:20100928183808j:image

f:id:satoru_net:20100928183840j:image

f:id:satoru_net:20100928184010j:image

f:id:satoru_net:20100928184033j:image

100814Satday

[]Super Hackers: PAC-MAN パックマソシュミレータ作ってみた

二日目、パックマンに挑戦中。

計算で解く人とかいるみたいだけど、

ロジック通りにパックマソをFlashで作ってみた。

いろいろおもしろい機能つけたし

応募期間が過ぎたら公開しようかなー。

1面

制限数が厳しいので、無駄な動作はできん面。

シュミレーターさえできちゃえば簡単。これくらいなら、計算でもできちゃうかも。

f:id:satoru_net:20100814181623p:image

2面

追いかけてくる系の敵機が少ないかわりに、敵の数が多い。

f:id:satoru_net:20100814181624p:image

3面

GOOGLE面かっこいい。

巨大すぐる。これは手動じゃないと無理だろうなw

f:id:satoru_net:20100814181625p:image

おまけ

無駄機能w

自分しかみないけどゲームオーバーになるとこんな画面になるようにしたw

f:id:satoru_net:20100814181626p:image

f:id:satoru_net:20100814184954p:image

というわけで、パックマソクリアー!

個人的には、しりとりの方が難しかったけど、採点はパックマンのほーが断然高くてビックリ。

100813Friday

[]Super Hackers:Shiritori

GoogleのDevフォーラム2010のQuizのお知らせが来たので早速やってみてるよ。


で、とりあえずShiritoriがおもしろそうなのでやってみてるんだけど、

要は用意された文字のリストを使って、googleのしりとりサーバと勝負して勝て!っていう課題。

なんか、HUNTERxHUNTERみたいでかっこいいなw


んで、普通にやると画面にボタンがあって、選ぶんだけど、ボタンぽちぽちボタンを押してても埒があかないので、

そうか『Super Hacker:Shiritori』とか言うくらいだし、スパハカーなら手動とかありえんよなwとか思って、

自動でしりとり応戦してくれるサーバを開発してみた。

googleしりとりサーバ vs しりとり応戦サーバの図

↓応戦中の図

たぶん、これを開発することがこの出題意図だよな。さすがググール。

サーバサーバがえいやえいや対決してるなんて、なんだかハイテク


結果、Lv1(スライム)とLv2(バラモス)は難なくクリアできたけど、

Lv3(ゾーマ)は10000回くらいトライしてるがまだ、クリアできね。ぐふ

たぶん、『ひかりのたま』的なアイテム使わないと勝てないように出来てるんだろうなー…

追記:翌日

ヤタ!応戦サーバから、『カチマシタ』と勝利報告のメールがww

f:id:satoru_net:20100814020821p:image

さて、次はパックマソやるかなー

追記

gdd2010jpも終わったので『しりとり応戦サーバ』のソース公開します。

Cookie部分はセッション情報なども入ってる為、コメントアウトしてます。

#!/usr/bin/perl

use LWP::UserAgent;
use Jcode;
use Data::Dumper;
use LWP::UserAgent;
use HTTP::Request::Common qw(POST);
use strict qw(vars);
use POSIX;

my $COOKIE = qq{xxxx}; ## 中身はセキュリティー的な問題で内緒
my $sub_section = 2;
my @pettern;
my $try = 0;
my $count = 0;

while(1){
	my $question = get_question();

	my $answer = (sort {rand($b)<=>rand($a)} @{$question->{answers}})[0];
	
	p("Question:[$question->{question}] / Answer:[$answer]");

	&do_answer($question->{hash}, $answer );
	my $res = get_question();

	p("[$try][$count]try");
	$count++;
	p("status:[$res->{status}]") if($res->{status});

	if($res->{status} eq "lose"){
		p("Reset");
		$try++;
		do_reset($res->{hash});
	} elsif($res->{status} eq "win"){
		p("Finish!!");
	} else {
		p("Next!");
	}

	sleep 1;
}

sub p{
	my $word = shift;
	my $date = POSIX::strftime("%H:%M:%S",localtime);
	print "$date:$word\n";
}

sub do_answer{

	my ($hash,$word) = @_;
	my $question = &get_question();

	# リクエストの生成
	my %form = (
	            'answer0' => $word,
	            'problem' => 'shiritori',
	            'sub_section' => $sub_section,
	            'hash' => $hash,
	            'submit_button' => '選択',
	           );

	my $req = POST("http://gdd-2010-quiz-japan.appspot.com/problems/submit", [%form]);
	$req->referer("http://gdd-2010-quiz-japan.appspot.com/problems?problem=shiritori&sub_section=$sub_section");
	$req->header("Cookie",$COOKIE);

	my $ua = LWP::UserAgent->new;
	my $res = $ua->request($req);
	
	
}

sub do_reset{

	my $hash = shift;
	my $question = &get_question();

	# リクエストの生成
	my %form = ('problem' => 'shiritori',
	            'sub_section' => $sub_section,
	            'hash' => $hash,
	            'reset_button' => 'ゲームをリセット',
	            'answer0' => 'reset',
	           );

	my $req = POST("http://gdd-2010-quiz-japan.appspot.com/problems/submit", [%form]);
	$req->referer("http://gdd-2010-quiz-japan.appspot.com/problems?problem=shiritori&sub_section=$sub_section");
	$req->header("Cookie",$COOKIE);

	my $ua = LWP::UserAgent->new;
	my $res = $ua->request($req);
}

sub get_question{

	my $ua = LWP::UserAgent->new;

		$ua->agent('Mozilla/5.0 (Windows; U; Windows NT 6.0; ja; rv:1.9.2.8) Gecko/20100722 Firefox/3.6.8 ');
		my $req = HTTP::Request->new(GET => "http://gdd-2010-quiz-japan.appspot.com/problems?problem=shiritori&sub_section=$sub_section");
		   $req->referer("http://gdd-2010-quiz-japan.appspot.com/problems?problem=shiritori&sub_section=$sub_section");
		   $req->header("Accept-Encoding","gzip,deflate");
		   $req->header("Cookie",$COOKIE);

		return parse_question(($ua->request($req))->content);
	
}

sub parse_question{

		my $res = shift;
		my $status;
		
		if($res =~ /勝ち/){
			$status = "win";
		} elsif($res =~ /負け/){
			$status = "lose";
		}

		my $flag;
		my @con;
		my @ans;
		my @hist;

		my $flag1;
		my $flag2;

		for(split /\n/,$res){
			$flag=1 if(/辞書/);
			$flag=0 if(/履歴/);
			if($flag){
				push @con,$_;
			}

			$flag2=1 if(/履歴/);
			$flag2=0 if(/回答/);
			if($flag2){
				push @ans,$_;
			}
		}

		my %hist;
		@con = map {m@<li>(.*)</li>@ ; $1 } grep {m@<li>@} @con;
		@ans = map {m@<li>(.*)</li>@ ; $1 } grep {m@<li>@} @ans;

		for(@ans){
			$hist{$_}=1;
		}
		
		my ($hash) = (grep {/hash/} split /\n/,$res)[0] =~ m@value="([^"]+)"@;
		
		my $question = $ans[-1];
		my @answers = grep {(get_word($_))->{st} eq (get_word($question))->{en} } grep { !$hist{$_} } @con;

		return {status=>$status, answers => \@answers, history=>\@ans, question=> $question, list=>\@con,hash=>$hash };
}

sub get_word {
	my $word = shift;
	my ($st) = $word =~ m@^(.)@;
	my ($en) = $word =~ m@(.)$@;
	
	return {st=>$st,en=>$en};
}

©satoru.net
Mail Twitter