Google Developer Day 2011 Japan Ignite: DevQuiz 解説
.app 1 .dev 1 #11WeeksOfAndroid 13 #11WeeksOfAndroid Android TV 1 #Android11 3 #DevFest16 1 #DevFest17 1 #DevFest18 1 #DevFest19 1 #DevFest20 1 #DevFest21 1 #DevFest22 1 #DevFest23 1 #hack4jp 3 11 weeks of Android 2 A MESSAGE FROM OUR CEO 1 A/B Testing 1 A4A 4 Accelerator 6 Accessibility 1 accuracy 1 Actions on Google 16 Activation Atlas 1 address validation API 1 Addy Osmani 1 ADK 2 AdMob 32 Ads
さんぷるクリプト: CでDevquiz２０１１スライドパズル
Devquizへの参加記念にソースコードを晒しておきます。 アルゴリズム １、IDA* 過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化 ２、双方向探索 ゴールから幅優先探索、前方からIDA*を実行しマッチング 実装中に他の方法で万点取れる目途が付いたので中途半端（というかまだ動いていなかった。。）になっています。 ３、端優先 人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。 ４、ステップ実行 指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。（それ以外のノードを捨てる） ５、半自動シミュレーション 上記で解けない問題が7問残った。この残った問題を半自動で解くためのヒントを元に解いていくシュミレーター。 *距離関数としてはブロックを考慮したマンハッタンディスタンス
DevQuiz 2011
今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。 スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。 以下，考えたこと等をメモしておきます。 基本的な考え方は，盤面をノードとしたグラフの探索で良いはず。 ノード数は，6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。 いかに沢山の探索をこなせるかと，無駄な探索を排除できるかがカギになるはず。 とりあえず，参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に，ずばりそのものスライドパズルが扱われている。 グラフの探索はA*で良さそうだ。 とりあえず，ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサ
GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた - Fire and Motion
基本的に自分用メモです．主に以下のtogetterまたは#gdd11jpのハッシュタグから情報を集めました．一応言語順にしてあります． http://togetter.com/li/187147 （勝手にリスト化してほしくないという場合はご連絡ください！） 追記：エントリーポスト時は9名分．9月12日18時で16名分に増加．22時に28名分，9月13日10時現在43名分です．大雑把な分類でJava:14名，C++:8名，C:6名，C#:1名，Python:6名，Perl:3名，Ruby:1名，Haskell:1名，PHP:1名，Go:1名，OCaml:1名 ． @komiya_atsushi さん 言語：Java コード置き場：https://code.google.com/p/k11i-gdd2011jp-slidepuzzle-solver/ 本人による解説：http://blog.k
DevQuizのスライドパズルのひねた解法 — KaoriYa
Google Developer Day 2011 Japanの参加権を得るために、DevQuizに参戦しました。 いや、正直途中から参加よりは参戦が目的になっていましたが… 9/12にDevQuizが終わりましたので、ちょっと振返ってみましょう。 Google Developer Day 2011 Japanの参加権を得るために、DevQuizに参戦してました。 いや、正直途中から目的が参加よりも参戦に変わってしまいましたが…9/12にそのDevQuizが終わりましたので、自分でもかなり面白かったスライドパズルのちょっと変わった解法をピックアップしてみます。 文中のわからない単語はググると良いでしょう。 正統派の解法 まず正統派の解法は総手数制限があることから「探索空間を張って最適解を求める」です。最悪全解答が最適解であることも想定しなければいけません(ただし少し解答が揃えばその心配は杞
DevQuizの解答(ソースコード)晒し スライドパズル編 #gdd11jp | 水嶋.jp
GoogleAppsScriptに続いてスライドパズルのソースコードも晒します CやJavaで挑戦する人が多かったようですが、僕はPythonで挑戦しました ソースコード中にも書いているのですが、こちらのページのサンプルコードを大いに流用しており、それに独自に改良を加えて完成させました # -*- coding: utf-8 -*- # このプログラムは次のサイトを参考にし、サンプルコードを一部利用しました # http://www.geocities.jp/m_hiroi/light/ import sys import string LETTERS = (string.digits + string.ascii_uppercase)[1:] # # pqueue.py : 優先度つき待ち行列 # # Copyright (C) 2006 Makoto Hiroi # # 葉の方向へ
DevQuiz：スライドパズルのソースコード(C言語) - Kishima's Hateda log
GDD2011のDevQuizのチャレンジクイズである、スライドパズルのソースコードを晒します。 たいへんぐちゃぐちゃなので、恥ずかしい…。 これで２日くらい５プロセス回すと、4500/5000くらい解くことができます。（自分の結果は4427/5000でした。合計してDevQuizの成績は144.3点でした） おそらく最短手が得られているはずです。 全問解答するためには、これに色々ヒューリスティックな改造をする必要があります。＞と思ったのですが、色々工夫するとヒューリスティック抜きでもいいところまでいけるようです。 アルゴリズムの方針としては、反復深化深さ優先を基本としてます。加えて終了局面を起点として幅優先で正解局面を展開してハッシュに溜めて、深さ優先の終了チェックに使用します。終了局面との距離には普通のマンハッタン距離を使用してます。それだけです。 他の方のツイートをみると、壁を考慮し
GDD2011 DevQuiz のスライドパズルに挑戦してみました
Google Developer Day 2011 に参加するために、DevQuiz に初めて挑戦してみました。ウォームアップクイズ、分野別クイズはさておき、一番やりがいのあった「スライドパズル」について、自分の戦略などを書き残しておこうと思います。 ソルバーのソースコードは、http://code.google.com/p/k11i-gdd2011jp-slidepuzzle-solver/ にて公開しています。 言語 回答期限までそこそこ時間があった →コーディングに多少時間がかかっても OK。 計算・空間効率を追求する必要がありそう →言語自体の実行性能が高いこと。またある程度、内部の挙動を把握できる、かつ効率化のポイントを把握していること。 などの理由により、開発言語は Java を選びました。 ソルバーの戦略ソルバーのプログラムは「ただひたすらにパズルを解く」ステージと、「利用可
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
Google DevQuiz 2011結果 - でこすけの日記
Cattakaの雑記 - DevQuizのスライドパズルの解答
Google Code Archive - Long-term storage for Google Code Project Hosting.