PlayNのeclipseの開発環境構築からサンプルプロジェクトの実行まで 
水曜日, 11月 30, 2011, 12:08 AM - プログラム
Google Developer Day 2011の2日後のEXP-Hackathonで触った
PlayNというゲームライブラリが思いのほか面白かったので
環境構築の方法をサイトのページにまとめてみた。

eclipseの開発環境構築からサンプルプロジェクトの実行まで

次はブランクプロジェクトの作成方法をまとめたい。

  |  0 trackbacks   |  このエントリーのURL   |  related link   |   ( 2.9 / 789 )

DevQuizのスライドパズルの解答 
月曜日, 9月 12, 2011, 09:16 PM - プログラム
GoogleがGoogle Developer Day 2011というイベントの開催にあたり、
参加権を掛けたDevQuizという問題をやってるので解いてみた。
普通のクイズの他にChrome ExtensionやAndroid、Google App Scriptを使った問題があります。
どれもエンジニアの人で、プログラムを書いて解かせないと解け無いような問題ばかりです。
その中のチャレンジ問題がかなり重い問題だったので、その解答についてです。

問題の概要


3x3〜6x6のスライドパズルが5000問をヒタスラ解くというものです。
5000問を通して手数に上限があるので、あまりダラダラとはできません。
手数をオーバーすると残りの問題を解いても採点されないので
なるべく少ない手数で解かなければいけません。

マイアプローチ


全部でソルバー1号、2号、3号の3つを作って5000問を解きました。
1号と2号は横型探索で、3号が正攻法で解くもので、
1号と2号で簡単な問題を粗方潰し、3号に難解な問題をとかせました。

ソルバー1号、2号(幅野郎)


特徴


・横型探索
・メモリに100万手を履歴として保持する
・100万手を超す履歴はOOMになるので評価関数にて低いものから破棄する
・次手の候補も多すぎる場合は評価関数にて低いものから破棄する
・過去に出現した手は履歴にマッチングさせることで検出して破棄する
・1時間で100問くらいしか解けないくらい遅い上にメモリを喰う

大雑把なアルゴリズム




工夫点


・メモリは2GBを与えた
・盤面はbyte配列で表現してメモリの消費量を削減
・履歴マッチングにはハッシュマップで計算量を削減
・ソルバー1号は評価関数にマンハッタン距離の合計を使用
・ソルバー2号は評価関数にマンハッタン距離×パネルの重要度の合計を使用
 (端っこのパネルの重要が大きくなるよう設定)
・AWSのラージインスタンスで7プロセスを実行して遅さを補った

実行結果


ソルバー1号と2号はどちらも4970問ほどを
それなりに短い手数で解いてくれました。

ソルバー3号


特徴


・人がパズルを解くときのように端っこから埋めて行きます。
・最初に各パネルに順位を付けて、その順に埋めて行きます。
・壁があっても解けるような順位付けをしています。
・1問1秒掛からない
・結果の手数に無駄が多い
・ソースが物凄い汚い(何)

順位付けのイメージ1





順位付けのイメージ2(ややこしい場合)




工夫点


・特に無し、解くこと最優先

実行結果


ソルバー1号と2号が解けなかった残り30問ほどを全部解いてくれました。

とまぁ、3つのソルバーで5000問全て無事解けました。
3号の結果の手数が多めでしたがソルバー1号と2号が手数をかなり余らせてくれていたので
合計手数も制限内に収まり、無事に5000問の全問を解くことができました。

ソースコード


ソースコードは以下からダウンロードできます。
ソースコードはこちら
eclipseのプロジェクトをzipにしたもので、インポートで取り込めます。
miscにある程度の説明書きも書いてますのでご参考までにどうぞ。

2011/09/17追記


GDD2011 Tokyo - devQuiz答え合わせ大会 in 関西にて詳細を発表しました。
資料はこちら

  |  0 trackbacks   |  このエントリーのURL   |  related link   |   ( 3 / 939 )

HTML5とSlim3を触って感じた技術の生まれ変わり 
月曜日, 3月 28, 2011, 12:10 AM - プログラム
ここ2ヶ月でHTML5とSlim3に触ったけど、
いずれも触っていて「良い」と感じた。
何が良いと感じたかというと
「欲しい機能が欲しいところに妥当な形である」というところに尽きる。

昔ながらの手法でWebアプリを作っていると、
当たり前の機能を当たり前のように実装するけど、
その実装方法にバッドノウハウを使わざるを得ないことがある。
つまり当たり前の機能なのに当たり前に実装できない。

例えば、フォーム要素のチェックボックスは1つしかないと
リクエストに値が乗らないからhiddenの隠し要素を埋め込んだり、
値の変更時に連動したい項目があるとき値という概念とは
直接関係のないonblurのイベントハンドラで処理したり、
サーバのイベントをブラウザにWebページに投げられないので
ポーリングさせたり、、、etc

このような、バッドノウハウによって支えられていた機能は沢山あるが、
それらがHTML5やSlim3ではバッドノウハウを使わずにすみ、
さらに妥当な手順で実装できることに気づかされる。


ここでちょっと話は変わる。
最近、新人を見ていると「先輩たちの下で技術を学びたい」という人がいる。
でも僕はそんなことよりHTML5やSlim3のように
新しく、不要な物が除去され、妥当な形になったものを学んで欲しいと思う。
なぜなら、この業界の先人たちが教えられることのほとんどは、
その人が実際に経験した問題に対してのバッドノウハウだからだ。
先人たちのバッドノウハウをより、新しい技術を学んで欲しい。
そのうえで「今当たり前になってるけど、昔はこうやって無理矢理に実装してたんだ」と
先人たちのバッドノウハウを歴史として見てくれればいい。


「枯れた技術+バッドノウハウ」と「新しい技術+バッドノウハウ」、
どちらから革新的なものが生まれるだろうか?
ハズレの場合もあるにせよ、まず後者になるだろう。
そして革新的なものが生まれてしばらくすると、
その「新しい技術」が「枯れた技術」となる。
そして「枯れた技術+バッドノウハウ」が新たな「新しい技術」になる。

今現在の「枯れた技術」も昔は「新しい技術」だった。
だからいつ学んでもいずれは古くなる。
だから今の新人達には「枯れた技術+バッドノウハウ」を学ぶ暇があれば、
「新しい技術」を学び、そのバッドノウハウを作って欲しい。

あと、もし普遍的な技術を学びたいのであるならば、
それこそ学校の情報工学の教科書でも読めばいい。
次々に新しくなる技術を眺め続けるよりそちらの方が確実だ。


というのが、古い手法で新しいことをしようとして、
バッドノウハウのオーバーヘッドに時間喰われて
イラっとしながら思ったこと。

  |  0 trackbacks   |  このエントリーのURL   |  related link   |   ( 3 / 792 )

OAuthでRequest tokenの取る 
金曜日, 2月 18, 2011, 10:48 PM - プログラム

OAuthでRequest tokenの取る



twitterの公式のドキュメントを見ながらOAuthを突いてみたけど、
oauth_signatureを作るのにえらい悩んだのでその備忘録。

事の発端になったtwitterのサイト
Authenticating Requests with OAuth

登場するもの


base string


送信するパラメータなどの一式を以下の擬似コードの様につなげたもの。
ただし、oauth_tokenとoauth_token_secretは含まない。

httpMethod + "&" +
url_encode( base_uri ) + "&" +
sorted_query_params.each { | k, v |
url_encode ( k ) + "%3D" +
url_encode ( v )
}.join("%26")


composite signing key


<consumerSecret>&<tokenSecret>
※:ただし、tokenSecretは発行されるまではブランク

oauth_signature


base stringをcomposite signing keyでサインしたもの。
サインの方法はいろいろあるようだけど、今回はHMAC-SHA1を使用した。


oauth_signatureの作り方


basestringの準備


以下のものを組み合わせて作る。
・httpMethod : POSTやGET
・ベースのURL
・oauth_callback : コールバック先のURL
・oauth_consumer_key : 自分のコンシューマキー
・oauth_nonce : 乱数のワンタイムパスワード
・oauth_signature_method : oauth_signatureの方法
・oauth_timestamp%3D1272323042%26
・oauth_version%3D1.0
こんな感じの文字列になる。
POST&https%3A%2F%2Fapi.twitter.com%2Foauth%2Frequest_token&oauth_callback%3Dhttp%253A%252F%252Flocalhost%253A3005%252Fthe_dance%252Fprocess_callback%253Fservice_provider_id%253D11%26oauth_consumer_key%3DGDdmIQH6jhtmLUypg82g%26oauth_nonce%3DQP70eNmVz8jvdPevU3oJD2AfF7R7odC2XJcn4XlZJqk%26oauth_signature_method%3DHMAC-SHA1%26oauth_timestamp%3D1272323042%26oauth_version%3D1.0


oauth_signatureを作成する


上記のbase_stringにサインする。
Linuxのコマンドでやるとこんな感じ。
echo -n <base_string> | openssl dgst -sha1 -binary -hmac <composite signing key> | base64

実際に実行すると、こんな感じの文字列になる。
$ echo -n 'POST&https%3A%2F%2Fapi.twitter.com%2Foauth%2Frequest_token&oauth_callback%3Dhttp%253A%252F%252Flocalhost%253A3005%252Fthe_dance%252Fprocess_callback%253Fservice_provider_id%253D11%26oauth_consumer_key%3DGDdmIQH6jhtmLUypg82g%26oauth_nonce%3DQP70eNmVz8jvdPevU3oJD2AfF7R7odC2XJcn4XlZJqk%26oauth_signature_method%3DHMAC-SHA1%26oauth_timestamp%3D1272323042%26oauth_version%3D1.0' | openssl dgst -sha1 -binary -hmac 'MCD8BKwGdgPHvAuvgvz4EQpqDAtx89grbuNMRd7Eh98&' | base64 

8wUi7m5HFQy76nowoCThusfgB+Q= ←これがoauth_signature

というわけでoauth_signatureとして「8wUi7m5HFQy76nowoCThusfgB+Q=」が作成できました。


Request tokenを取得する


上記で取得したoauth_signature含めた文字列を
ヘッダのAuthorizationに入れて使ってリクエストを投げると
oauth_token、oauth_token_secret、oauth_callback_confirmedが返ってくる、、、らしい。
今日はできなかったのでここまで。

OAuth oauth_nonce="QP70eNmVz8jvdPevU3oJD2AfF7R7odC2XJcn4XlZJqk", oauth_callback="http%3A%2F%2Flocalhost%3A3005%2Fthe_dance%2Fprocess_callback%3Fservice_provider_id%3D11", oauth_signature_method="HMAC-SHA1", oauth_timestamp="1272323042", oauth_consumer_key="GDdmIQH6jhtmLUypg82g", oauth_signature="8wUi7m5HFQy76nowoCThusfgB%2BQ%3D", oauth_version="1.0"


  |  0 trackbacks   |  このエントリーのURL   |  related link   |   ( 3 / 789 )

VMWareで開発環境を作って圧縮して配布する 
土曜日, 9月 4, 2010, 11:18 AM - プログラム
複数人で開発をすると開発環境を整えるのが大変なので
VMWareで開発環境を一式作って配布したらいいんじゃないかと模索した。

今回作ったのはAndroid用の開発環境でこんな構成です。
・Ubuntu 10.04 LTS
・Eclipse 3.5 Galileo + ADT
・Android SDK
一式インストールして、リポジトリの設定をして、
VMの仮想ディスクのサイズを見ると5.6GB、
DVDに入らないしでかすぎる・・・orz
仮想ディスクの使用量は4GBも無いから、もう少し小さくなって欲しい。

調べてみるとvmware-vdiskmanagerの-kオプションを使うとディスクを小さくできるらしい。
# vmware-vdiskmanager -k AndroidDev.vmdk

実行結果は・・・5.6GB、変わってねぇ・・・orz

よくよく考えてみるとOSのディスクの使い方の都合上、
ファイルは削除されても領域にはデータは残っている。
これらをクリア(0埋め)してあげないと仮想ディスクのサイズは小さくなれないようだ。

というわけでクリアした。
cat /dev/zero > zero.fill;sync;sleep 1;sync;rm -f zero.fill

やってることはディスクを使い切るように
データが全て0な巨大なファイルを作成して削除するだけ。
改めてvmware-vdiskmanagerの-kオプションで実行すると4.4GBまで小さくなった。
これでDVD一枚に収まりそうだ。


でも流石にこのまま配布するのもなんなので、ZIPで圧縮することにした。
で、圧縮しようとしたらエラーになった。
$ zip -r AndroidDev.zip AndroidDev/AndroidDev.vmdk
zip warning: name not matched: AndroidDev/AndroidDev.vmdk

zip error: Nothing to do! (test.zip)

なんか「name not matched」とかでてるけど名前は間違ってないんだけど・・・、
とやってると、実はzipの2GBの容量制限に引っかかってたらしい。
エラーメッセージが間違ってんじゃん・・・(´・ω・)
なのでzipは辞めにして、7-Zipで圧縮したら無事圧縮できて1.3GBまで小さくなった。

あとはこれを仲間内で使うためにWebにアップしたいのだが、
こんな巨大なファイルを何処に置くかで悩む、と。
とりあえず低価格のオンラインストレージを模索中。

つかれた・・・(つ・ω・)つ

参考
How To Shrink VMware Virtual Disk Files (.vmdk)
  |  0 trackbacks   |  このエントリーのURL   |  related link   |   ( 3 / 1009 )


Next