進・日進月歩

2011年も最終日となりました。みなさんにとって2011年はどんな年だったでしょうか？ 私にとっては、やたら長かった学生という身分をようやく捨てることが出来まして、おそらく将来振り返ってみたらひとつの区切りの年として記憶に残るのではないかなと思います。

本当は反省とか書こうと思ったのですが、謝辞としてみました。というのは、今年は全く生産的なことをしていない一方で、数多くの皆様の力を大いに借りることとなり、これほど人のありがたみというものを感じた年も無かったからです。 本当に支えられました。ありがとうございます。

学生生活が終わりました

正直、大学院での生活については全く書くことがないのですが、卒業に際しては色々な人に協力をいただきました。

卒業に際して粟飯原さんに大変お世話になりました。 粟飯原さんには、参考になりそうな論文をいくつか紹介していただきました。 アイディアのディスカッションにも時間を割いていただき、半年という短期間でなんとかできたのは、粟飯原さんとのディスカッションがしっかりできたため明確なゴール設定が出来たからであると思います。 誰もが不可能だと言っていたのをねじ込めたのは、初期の計画段階での粟飯原さんの貢献が大きいです。

実験に際して、マシンリソースが足りなかったので、6台あった計算機を潰してパーツを集め、若干の投資をして計算専用機を組み立てました。 パーツの組み合わせには、父の意見を参考にさせていただきました。当時の個人向けPCとしては、かなり最高スペックに近い構成でくみ上げ、Ubuntuが3秒弱で起動するという爆速PCができたおかげで、大変実験がしやすくなりました。 今でもたまに使っています。 この実験環境が無ければ卒業はかなわなかったでしょう。

修論アイディアは複数あったのですが、その予備実験に際してピクシブのデータを少し使わせていただきました。 データ抽出に際して快くOKしてくれた青木さん、データ抽出に協力してくれたbokkoさん、ありがとうございました。

就職活動

就職活動は二回目だったのであまり苦労は無かったのですが、ykfさんから色々とアドバイスをもらったおかげで、割とあっさりと決まりました。 ありがとうございます。

なぜかあの会社には知人がゴロゴロいて内定後も色々と情報提供いただきまして、色々と参考になりました。 ドリームゲートの頃からの知人である秋間がいつのまにかあの会社に転職していたりもして、非常に参考になる情報をいただきました。

メンタル的な支え

ちょっと色んなことがありすぎて盛大に荒れていたのですが、色々な人に心配していただき立ち直ることが出来ました。

もうかなり長い付き合いになりつつあるもぐたんこと古川浩太郎には毎度やけ酒につき合っていただき、とても助かりました。多分一番何があったかを知っているのはもぐたんなのではなかろうかと思います。 ありがとうございます。

やすさんは、あまり表立って心配を口にはしなかったけれども、気遣いいただいたのをとても感じました。ちょくちょくご飯や飲みに誘っていただき面倒を見てくれました。うまく気分をスイッチすることが出来ました。ありがとうございます。

荒れてるのを察知してメッセージをくれた旧知の仲である大倉君や、海の向こうからfbでメッセージをくれた学部の頃大変お世話になった芳川さん、気遣いいただきありがとうございました。

namyuさんには直接心配の電話までいただき、色々と堅実なアドバイスをいただきました。ありがとうございます。

奈良にいた某女史、久しぶりにご飯を食べにいってくれた人、最終的に心の支えになってくれた人には本当に感謝しています。

ピクシブ

大学院時代はピクシブで大変お世話になりました。チームラボでアルバイトしていた頃からお世話になり続けている青木さんにご紹介いただき、ピクシブ本体のちょっとした直しやピクシブ百科事典の開発をさせていただきました。

2009年4月くらいに関わり始めた頃は、全体のPVが億に到達したかなという頃で、メンバーも10人くらいの会社でした。 それが、みるみるうちに大きくなり、今ではとてもきれいなオフィスを構え、メンバーも増え、海外展開を視野に入れた企業へと成長していました。 PVや会社の規模という側面を見ても、ここまで急成長した企業というのに関わらせていただいたのは人生で初めてで、とても貴重な体験をさせていただきました。

その中で、私は主にピクシブ百科事典の開発をほぼ全面的にさせていただきました。これまでも上場企業のウェブサイトを部分的に作るなどしていたのですが、単純にPVという観点ではピクシブ百科事典がダントツでした。

ピクシブ百科事典を作るにあたって、多くの経験をさせていただきました。ピクシブ百科事典は0からPHPで書かれており、開発に際してはCakePHPやRuby on Railsなどのソースを読み、それぞれのいい点悪い点を整理しながらフレームワークを書きおこしました。 それぞれのフレームワークのベストプラクティスを抽出しつつ、ピクシブの業務にそったアーキテクチャを作るという経験はとても貴重な体験でした。 そうした中で、Kamipoさんには多くの欠陥を指摘していただきました。2年半たった今では、相応に安定した構造に進化させることが出来ました。ありがとうございます。 卒業騒ぎがあり、その影響で多少心残りな点があるのですが、今ではメンテナンスを引き継ぎ私の手を完全に離れました。

膨大なPVをさばくWebサイトでは、正しくMySQLのインデックスを貼ることはもちろんのこと、KyotoTycoonやSolrなど要所要所で正しいソフトウェアを選択することが求められます。 そうした要素技術の検証などもいい経験となりました。

インフラチームの店本さん飯田さんには大変お世話になりました。とてもインフラチームは忙しいにも関わらず、要望にいつも迅速に答えていただき大変助かりました。

一緒にアルバイトしていた溝部くんはとても積極的な人で、みるみるうちにプログラミングを習得していき、今では自分のwebサイトを企画し開発するレベルにまで到達していました。初期の頃のピクシブ百科事典のモバイル版は彼がさくさくっと作ってしまったもので、その吸収力の高さには驚くばかりでした。 この積極性には大変私も影響を受け「俺ももうちょいがんばらないとなー」と感じさせられました。

その他にも、数多くのメンバーにお世話になり、多くの勉強をさせていただきました。本当にありがとうございます。 色々と私的な部分でトラブルを抱えてしまったため、今年はあまり貢献できず、ほとんど放置か丸投げ状態にしてしまいすみませんでした。今後も大きく発展していくことを祈っています。

終わりに

卒業した10月以降も多くの人にお世話になりました。そのほとんどはまだ現在進行形なので特に書くことはしないですが、これからも楽しいことをし、皆様の役に少しでも立てれば嬉しいと思います。 今年は本当に「色々な人に助けていただいた一年」というのが相応しい年でした。ほんとうにありがとうございます。みなさまの応援に応えられるよう、今後もがんばっていきたいと思います。

修士時代にやったことその2。

実はちょこちょこwebサイトを作っているのですが、修士の間中ずっとアルバイトでお世話になっていた会社でとあるサービスのPHP部分をほぼまるごと作っていました。blame見てみたら、27,075行中22,869行コミットしていたので、84%くらいのPHPコードをほぼ１人でコミットしてた計算になります。 それなりにブランド力のある企業の関連サイトなので、それなりのPVと人が使ってくれており、2chでも時々炎上していて、なかなかに貴重な体験でした。

最近安全なプログラミングについてはよく話題になりますが、安全なアーキテクチャ・無駄の少ないアーキテクチャについてはあまり話題になっていない様に思います。 その点をふまえつつ、行った工夫などをちょこちょこ書いてみたいと思います。

普通といえば普通な部分が多いのですが、最近はみんなrailsとかcakePHPとか使ってしまうので意識されてない部分もきっと多いんじゃないでしょうか。

デプロイはリポジトリ経由で

デプロイとは、開発したプログラムをサーバに配置して実際に利用できる様にすることを言います。 個人でウェブを作ってる人などは、scpやftpなどでレンタルサーバにフィアルをアップロードしたりするんじゃないでしょうか？ ざっくり言うとそれがデプロイです。

その当時、アプリケーションのデプロイはリポジトリ経由で行われていませんでした。ざっくり言うとrsyncでサーバに配置していました。 趣味でプログラミングをしているだけであればあまり問題になりませんが、複数人開発を行っていると様々な問題が出てきます。

• バグの特定

  自分が行った変更は大体覚えているので大丈夫だと思いますが、自分が知らないうちに行った 他人の変更を追跡するのは難しいです。diffをとったり、変更した人を大声で探しまわったり、 結構大変です。 バグが起きたとして、変更が行われた日時が記録されていないと、どの変更が原因だったかを 特定するのに職人の勘によるデバッグ大会を行うはめになります。 これは時間も労力もかかっていいことありません。

  この点、必ずリポジトリにコミットした後、それをデプロイする様に管理すれば、 原因の特定は容易になりますし、最悪バージョンを差し戻せば早期の復旧が望めます。

• プログラムの変更の追跡

  プログラムをリポジトリ経由でデプロイするようにしないと、割りと頻繁にコミット忘れが起きます。 リポジトリを経由すれば、コミット忘れがあると動作がおかしくなるので、 すぐにコミット忘れに気づくことができます。 結果的に、プログラムの変更の追跡がきちんと可能になり、 バグの普及や原因の特定を素早く行える様になります。

コミットログとかが適切に残されていないと、 詳しい人が頑張るしか無くなるという状況が多々発生します。 頑張れば直るのであまり気にされないことが多いですが、それによって 無駄に失われる労力や時間などを考えるとかなりもったいないです。 しかし、きちんとコミットログさえ残されており、変更が追跡可能にさえなっていれば、 素早いバグの原因特定が可能になるはずです。

現在では、私が作ってる範囲は、capistranoをベースにしたデプロイ方法で運用されています。 （他はよく知らない）

DB接続はベタで書かない

プログラムのリソース管理を手動でやると大変という話です。

それまでのプログラムは、mysql_connectがべた書きされていました。こんな感じ。

// php

// ...some logic...

$link = mysql_connect(HOST, USER, PASS);
mysql_query($sql, $link);
mysql_close($link);

// ...some logic...

この書き方をすると、プログラムが長文になってきた場合、重複してコネクションを張ろうととしたり、無駄に開いたり閉じたりしてリソースの無駄遣い天国になってしまう場合があります。 例えば次のような形です。

// php

// some_require.php

$link = mysql_connect(HOST, USER, PASS);
mysql_query($sql, $link);
mysql_close($link);

// main.php
require_once("some_require.php");

$link = mysql_connect(HOST, USER, PASS);
mysql_query($sql, $link);
mysql_close($link);

これは非常に単純な例ですが、色々なファイルでDBコネクションを張ったり切ったりすると、 人力での管理は中々に困難です。 そこで、DBの接続を管理するクラスMysqlDAOManagerを作って、DB接続を管理する様にしました。

// php
$dao = MysqlDAOManager::getInstance("some db");

$stmt = $dao->prepare("SELECT * FROM table WHERE type_flag >= 0 ORDER BY updated_at DESC LIMIT ?, ?");
$stmt->bindValue(1, $offset, PDO::PARAM_INT);
$stmt->bindValue(2, $count, PDO::PARAM_INT);

$stmt->execute();

MysqlDAOManager::getInstance() によってDB接続が管理され、プログラム中のどこで呼んだとしても接続はひとつしか作られません。 様々なファイルをrequireやincludeする時に起こりがちな失敗を防ぐことができます。

関数やクラスをラップしたり継承したりする

システム全体で使う外部のクラスや関数はラップして使う様にしています。 例えばPDOなどを利用する場合直接PDOを使わずに、それを拡張したクラスを利用します。

// php
class MysqlDAO extends PDO
{
    // ... some code ...
}

こうすることの利点は、メソッドの挙動を変えたり、PDO以外のクラスを使うことになったときの修正の量を減らすことができる点です。 実際、以前はPDOではなく独自の方法を使っていたのですが、PDOへの変更を比較的スムーズに行うことができました。

またデバッグコードを仕込むなどの工夫も容易に行えます。

// php
class MysqlDAO extends PDO
{
    public function prepare($statement, $driver_options = array())
    {
        return parent::prepare($statement . "/* debug sql */", $driver_options);
    }
}

上の例では、prepared statement を作る時に、SQLの末尾にデバックコメントをつける例です。 こうした実装をしておくと、全てのSQLを置換する代わりに、メソッドをオーバーライドすることで簡単に挙動を変えることができます。

Rakeを使ったテスト環境構築の自動化

簡単にテスト環境が構築できる様にRakeで一定の自動化を行っています。 具体的には、

• CSSファイルの生成（sassを使っているため）
• jsの文字列置換（本番のURLをテスト用に置換する）
• tmpディレクトリの作成

などを行っています。

ビジネスロジックをモデルクラスにまとめる

いわゆるMVCモデルでのコーディングを心がけましょうという話です。

私が作っているwebサイトでは、携帯・PCなどさまざまな形態で見られるのですが、 ロジックは大体PC版を基本としてPC版のモデルを継承・拡張して再利用して作られています。 そのため、サイト全体に影響するような変更が容易に行えますし、 新しいデバイスに対応するのも比較的容易になっています。

まとめ

行われてる施策は基本に忠実なものが多いのですが、 こういった基本をしっかり抑えることで結構な省エネが出来ています。 XSS対策やjQueryの活用など、各論がネットでは多く話題になるような気がしますが、 webサイト構築全般を見通した設計を試みることでかなりの省エネが可能になるような気がしますし、 バグの早期発見や早期対処も可能にすることができる様に思います。

個人的な考えでは、人間は必ずミスをしますし改善しても中々直らないものだと思っています。 だからこそ、サイトのアーキテクチャそのものにミスを防ぐ仕組を入れ込み、 ミスを最小化していくことが重要なのではないかなぁと思います。

その他にも色々な小さな工夫がちりばめられているのですが、 それは思い出したら追々書き足すかもしれないです。

修士時代に研究としてやったことのひとつ。 研究というよりも、単に作っただけだったりもするので、なんとも研究としては香ばしい感じなんですが（汗）。 個人的には、役立ちそうなのに色々な理由であまり応用されてないテクニックのひとつだと思います。（個人的な考えでは、Web作りたい人達とこういう技術すきな人の間にビックリするほどの溝があるからかなーと思ってる）

Webサービスのような閉じた世界の中での画像の検索を便利にするためにはどうしたらいいかが、基本的なテーマです。

概要

Webサービスになっているレベルの検索は、おおまかに言えば自然言語処理的な検索か、転置インデックスによる検索、類似画像検索が多いです。 例えば、Google画像検索は、画像周辺の文字と画像を関連づけて検索できる様にしていて自然言語処理的な検索と言えます。 flickrやpixivでよく使われている検索機能はタグやカテゴリなどに基づくもので、転置インデックスをベースにした検索方法です。 類似画像を探してくるサービスは最近たくさんあるみたいで、単純に似たような見た目の絵を探してきてくれます。

これらの検索は大変便利なのですが、pixivのような閉じたサービスに対して使うには、少しずつ欠点があります。 閉じたサービスでは、画像周辺に十分なテキストが与えられているとは限らないので、Google画像検索の方法では検索が困難です。タグによる検索でも、ユーザが必ずしも十分なタグを与えているとは限らないため、必ずしも便利ではありません。例えばライオンの画像に「動物」としか書いていないことがよくあります。 類似画像検索は、似た画像を収集することはできますが、「猫」という言葉で検索することはできません。

こうした問題を解決するために色々なアプローチがされているのですが（割愛）、中山さんの研究をベースにやってみました。 一応修論では、理屈こねくり回してますが、研究とか何それおいしいの・・・・

最終的には、画像データだけから「これは猫っぽい」「これは4コママンガっぽい」とかを判定して、検索を出来る様にしています。 タグ付けとかいらないし、似たような雰囲気の画像探せるし、これは便利に違いない。

理屈

ごちゃごちゃした理屈はたくさんあるのですが、割りと書くのが面倒なので省略。

画像の内容を考慮した上での画像クラスタリング

ウマくいったやつだけピックアップしてみました。 例えば、「タイガーアンドバニー」「切り絵」クラスタ。

タイガー&バニーで、しかも、切り絵っぽいイラストばかりウマく集まっていますね。

次に4コマクラスタ。

これもうまくいってます。 これらの画像には「4コマ」とか「タイガーアンドバニー」とかタグがつけられていなくても探せるのが特徴です。 また、単純に「タイガーアンドバニー」だけじゃなく、「特に切り絵を探したい」といったことにも使えるわけです。

検索

「ドット絵」で検索した結果が面白かったので掲載。

「ドット絵」じゃないものも混ざってますが、色々なドット絵が探せています。 繰り返しですが、「ドット絵」というタグがついていなくても検索できます。不思議ですね。

まとめ

色々あったので、やっつけ仕事で作った検索なんですが、思いのほかうまく動いています。 実運用には多少のチューニングが必要なんですが、個人的には割りと便利だなーと思っています。

特に、「タグがついていないから検索できなくて残念・・・」とか「上手な絵だけ探したいのに、ノイズが多くて」とかそういう画像検索ニーズに答えて行けるような技術になるのではないかなーと思います。 また単純に「見た目が似ている」だけではなくて、「画像の中身の類似性もそれとなく考慮」することができるので、似た雰囲気の猫さんとかを探すのにも役立って行くと思います。

というわけで、大学院時代にやったことその1でした。

さしあたり感想など。やったこととかは近々書く。 その1: 画像検索をしよう

大学院2年間半で学んだことというのは、よくも悪くも人間関係というものは大切だなーということでした。 学部時代までがどちらかというと人間に恵まれすぎていたのか、今度は人間関係の非常にめんどくさい部分を多く見れたような気がします。

そんな中、留年が決定したタイミングで割りとまとまった金額の超短期仕事をたまたまふってくれた友人（これで半年生きれたw）や、わりとヤケグソ気味に飲み歩いていた時にお付き合いいただいた方々、大学関係ないのに実験機材やら資金やら具体的な研究アドバイスをくれた方々、「お前ちょっと顔出せ。強制な。」とあまりにも病んでたのを気にかけて半強制呼び出し飲み会をやってくれた人達、おかげさまでなんとか生きてます。正直、この恩は出世払いでも返せない気がします・・・・

某所では、「はらじゅんはウチのせいで留年したのではないか」と心配している方々がいるようですが、実際の所それほど関係ありません。

今回は遊んでたわけでもなんでもなく、割りと素で留年してしまったので、結構しんどかったです。 正直次に打つべき1手すら見えてこないような状況で、暗中模索とはこのことかなぁという感じでした。 昨年は、完全に実験が行き詰まってこけてしまい、指導教員にも「知らない」と言われる始末で、タイムアウト。 同じ轍を踏むわけにも行かないので、今年は中途半端に他人を頼るのをやめて、始める前に論文を書ききるところまでの計画をみっちり立てて、実験機材やらソフトウェア・手法・お金に関することまで全て決めてからスタートしました。 最初からやっとけば良かった。

裏では結構あれてましたが、表では割りと淡々とやるべきことをこなし、地震があったり就職超氷河期でフリーダム人生な状況でも割りと無難に内定を頂き、なんやかんや中の上くらいの人生をゆるゆると歩んでおります。

「せっかく半年自由なんだからなにか一念発起したら？」的なことを色々言われるのですが、正直メンタル面で疲れてしまっていて、のんびり趣味や旅行にでも使おうかなーと。 幸いにも実験に必要なほとんど全てのものを自分でそろえているため、色々な実験も自分の環境で出来るし、近々sakuraのクラウドも出るらしいということで、その辺を使って個人的に色々なものを作って行きたいと思います。 一応大学院入った当初の目的だった「機械学習やデータ解析を触ってみる」という部分は個人的に達成しているので、その辺とwebサービスをくっつけて行けたら面白いかなーと。

そろそろ単純な大工仕事で作れるサービスは飽和してきています。誰でも作れるので、大量発生大量死したなかで、生き残って行くものがでてくるというのが現在のwebサービスである気がします。高確率で死ぬわけで、そこに参加したい気はしません・・・・・ 生き残っているものをみると、世界的に見れば携帯ゲームですらデータ解析が行われていますし、検索なんかも機械学習やデータ解析の塊です。 facebookがさりげなくやってるedge rankやらもデータ解析の賜物です。 これから生き残って行くサービスはこうした大工仕事以上の技術力が必要とされているというひとつの例だと思います。 しかし一方で、そうした技術の中で実際に応用されているのは一部です。 ここにちょっとしたギャップがあります。

ビジネス領域でもデータ解析を生かそうという動きは結構あります。 ここ10年でオラクルやらIBMが色々統計解析の会社を買収しまくっていますね。 これは中々に興味深い動きです。語りだすと長くなるので省略。

そういった、新たに一般化してきたITの力ををつかって、楽しく生きて行こうと思います。

先日の記事で スライドパズルの解き方について書きましたが、おまけでwebgameについてもちょっとだけ書きたいと思います。単なるおまけです。

webgameは何なのかというと、早い話がjavascriptで動く神経衰弱です。 ヒント通りに解くと、自動的に札をめくらせるChrome Extensionを作って総当たりさせるというのが趣旨のようです。 しかし、このヒントは華麗にスルーしましょう。 明らかにjsで動いていますから、男なら黙ってソースを読みます。ページのソースを見てみましょう。

// html
<script> 
<!--
$(function() { conc.setup(["0b0","bb0","00b","b00","bb0","b00","0b0","00b"]); });
//-->
</script> 

なんてことでしょう。答え書いてあるじゃないですか・・・・・ この答えをそのまま利用するブックマークレットを作りました。

// javascript
javascript:arr=eval($("script")[2].text.match(/\[.*\]/)[0]); ans = []; for (v in arr) { ans.push([v, "0x"+arr[v]-0]); } and = ans.sort(function(a,b){return a[1] - b[1];}).map(function(v){$("#card"+v[0]).click()})

これをツールバーに登録してぽちぽち押して行けばあっという間にクリアです！

おまけでした。

Google Developer Quiz 2011に挑戦してみたのでそのまとめをしてみたいと思います。 書いたコードはgithubにアップロードしてあります。 最終結果はこんな感じになりました。

苦戦するとすればチャレンジクイズだと思うので、その方針を簡単に。

チャレンジクイズの内容はいわゆる15パズルを解くという問題です。 ある盤面が与えられた時に、できるだけ短い手数で解くのがポイントになります。 基本的に、次の方針で考えました。$A^*$サーチに近いかもしれない。

• 短い手が知りたいので、幅優先を基本とする
• 一度検討した盤面を二度検討しない様に、検討した盤面は記録しておく
• 500万盤面検討して答えが出なければスキップする
• ゴールからの遠さを示すコスト関数を作って、コストの小さい盤面から検討する
• 手数が長いと意味が無いので一定以上の長さになったら打ち切る

まず、実際に単純な幅優先探索で実装してみました。これが全く答えが出ない・・・・。 結果的に、だいたい10〜100手程度で答えが得られるのですが、最小の10手でも膨大な数になります。 上下左右の移動ができるので、10手の場合だと$4^{10}=1048576$となり、あっというまに500万盤面の1/5です。これでは全く話になりません。

そこでコスト関数を設定して、ゴールまでのコストが低くなる手を優先する様に変更しました。コスト関数をソースから抜粋。

// cpp

int estimate_cost(const node &n1, const node &n2, int w, int h) {
    int cost = 0;

    // (1) マンハッタン距離に基づく、答えとの距離の差
    for (int i=0; i<w*h; i++) {
        if (n1.board[i] == '=' || n1.board[i] == '0') continue;

        for (int j=0; j<w*h; j++) {
            if (n1.board[i] == n2.board[j]) {
                cost += abs((i%w) - (j%w)) + abs(i/w - j/w);
                break;
            }
        }
    }
    // (2) 答えとの距離と、現在の手数/2を合算してコストとする
    return cost + n1.operation.size() / 2;
}

簡単に説明すると、（1）でマンハッタン距離の要領で答えの盤面と現在の盤面との距離を擬似的に求めて、（2）でそこまでの手数の1/2と合算して、コストとしています。 盤面間の距離は、単純に答えからの遠さを表していて、これが小さい盤面を優先することで効率的に答えに近づけることができます。 実際に、手数の長ささえ気にしなければ盤面間の距離のみをコストとした方が早く解けます。

そのまま手数の長さを足すと、手数の長さが聞きすぎてこれもウマく答えを出すことができません。 実際1/2したり1/3したりするとわかりますが、盤面間距離と手数の長さの割合をかえると、幅優先よりになったりコスト優先（深さ優先的）になったりします。 言い換えると、メモリを犠牲にして最短手を求めるかメモリを節約する代わりに長めの手を求めるか、というようなトレードオフになっています。 色々とやってみたけっか、1/2するのが私にとっては折り合いが良かったです。

これでも、割りと4×4程度ならサクサク解けていたんですが、大きいのだとうまくいきません。 そこで、ザクッと長い手を切ってしまうことにしました。

// cpp
if (n1.operation.size() > w1*h1*4) continue;

盤面の幅w1と盤面の高さh1を乗じて4倍した値よりも長ければ、打ち切りです。 幅と高さを考慮に入れてるのは、「大きさに合わせて打ち切りの値かえた方が自然かなぁ」と思った程度で特に根拠はありません。 4も実行経過をみて消費メモリが1GBにおさまる程度のところに設定しているだけで根拠ありません。

こんな感じで、ちょこちょこ改善改善とやって行った結果、macbookでだいたい8時間計算して9割程度が解ける様になりました。 で、結果が冒頭の通りです。

nokunoさんのまとめによると、どうやら反復深化法で解いている人が多かったらしいです。 反復深化法って初めて聞いた・・・・ 結果的にはコストに深さ（手順の長さ）を含めているので、完全に同じではないにしても似たような結果が出るのではないかなぁという気がします。

今回は、コスト関数の係数を数種類試すのと、打ち切りの値をちょっといじる程度の工夫しかしていないのですが、それだけでも劇的に改善することが見て取れてちょっと面白かったです。 たぶん、コスト関数の設計をもう少し検討して行けば早く短く解ける様になるんじゃないかなーという気がします。

最後に、今回の点数分布について載せておきます。ほとんどの人はチャレンジ問題やらずにすませてるみたいですね・・・・

追記メモ：参加者達

• Google Developer Day 2011のDevQuizをやってみました
• GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました
• 全部解けてる！すごい。 GDD2011 DevQuiz スライドパズル

しばらく更新していなかったのだけど、 更新していなかった理由はwordpressのwysiwygが気に入らなくて、 書くのがおっくうだったからだったりします。

やはり$ \TeX $とかの構造化されたテキストの方が個人的には 書きやすいので色々検討した結果、Markdownが書きやすそうなので それを使うことに。

そしてパーサーをちょっといじって、 $\TeX$とソースコードを載せやすい様に改造してみました。

アクセス解析見ると前のブログにもなぜかちょこちょこアクセスがあるので 残しておくことにします。

というわけで、今後ともよろしくお願いします。

新: http://blog.gijutsuya.jp/hrjn/

旧: http://blog.gijutsuya.jp/harajune/