ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/

「女子大生とペアプロするだけの簡単なお仕事」でSSSをとるまでに考えたこと

Ruby POH

今回で二回目になる「POH!」

女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2

前回*1は「合理的かつきれいに書けば通る」ってレベルだったのですが、
少なくとも私の（わりと雑な）プログラミングレベルだと、
今回は相当突き詰めないと難しかったのです

せっかく苦労して解いたので、自分の中でも一度整理しておきたいので、
思考の過程を思い出せる範囲でメモしてみます...φ(･ω･｀)

まずは仕様通りに書く

問題を大雑把に整理すると、「あるサイズのオブジェクトが、
既存のオブジェクトと衝突しない座標の数を求めよ」ということです

言い換えれば、「オブジェクトを各座標ごとに動かしながら、
オブジェクトの範囲に何か障害物があるか？」ということになります

これを馬鹿正直に実装したのがこちら(´･ω･)っ

あらかじめ各座標に「オブジェクトがあるか？」を入れておき、
座標を動かしながら、オブジェクトの範囲を探索する、という方法です
これでもcase4までをパスしています

全部埋まっている行は調べるだけ無駄だよね・・・？

サイトにある「入力例1」を見てもらえばわかるのですが、
4行目から7行目は「1」で埋まっている、つまり探索するだけ無駄です

それをふまえて実装したのがこちらですが・・・

・・・大差はありません(´-ω-)

データ構造に情報を畳み込もう

最初のやり方の問題は、各座標における探索回数が、
「縦×横」、つまりは「O(n^2)」になっていることです

これを「座標個×オブジェクト数」繰り返すとなると、
相当に無駄が含まれます

そこで、あらかじめ「横にいくつ空いているか？」を計算しておく、手を思いつきました

元データ
1000
1101
1001

計算後データ
0321
0010
0210

こうすると、ある座標を見ただけで、
そこに横幅いくつのオブジェクトが入るかすぐわかるので、
縦方向の探索だけで衝突判定できますヽ(`･ω･´)ノ

この構造を起点に、いろいろな計算回数の無駄を省いたのがこちら

これでcase5を突破しました

縦も考えてみる・・・？

元のデータが「横軸のデータを縦に向かって読む」という構造だったため、
どうしても横ばかり考えてしまいましたが、
状況によっては「縦軸の方が効率がよい」場合があります

縦に向かって探索する場合、「横2×縦100」のオブジェクトに対し、
最悪100回の衝突判定が必要ですが、
これを横に向かって探索すれば2回で終わります

なので、「縦にいくつ空いているか？」のデータも計算しておき、
「縦か横で計算回数が少なくなる方」で判定していけば、
計算量を減らせるのではと推測しました

まあ、あまり効果がなかったんですけどねΣ(・ω・ノ)ノ

盤面じゃなく、チェックするオブジェクトの問題じゃない・・・？

ここまでやっていまいちな成果しか得られなかったので、
別なところにボトルネックがあると推測しました

例えば、盤面のサイズが普通であったとしても、
チェックする対象が1万件あり、しかもそれが「2x2」の同じサイズなんて場合、
いちど計算すればあとの9999件は同じ値を出せばいいのです

つまり、「メモ化」しろと(`･ω･´)

ver2とver3に対し、それぞれ「結果を記録」するロジックを入れたところ、
たいして変わらなかったので、複雑化していたver3を破棄し、
ver2をメモ化したものをベースに進めることに

最終的にはメモ化というより「存在するパターンだけ調べる」に変わり、
ついでにコードも整理してみたのですが、やっぱりいまいちですね(´-ω-)

まだチェックするオブジェクトに無駄があるよね・・・？

盤面より大きなオブジェクトは排除するにしても、
もっと細かいレベルでオブジェクトを排除できないかと考えました

縦と横の空きデータを作る時点で、
「縦横それぞれこのサイズまでしか入らない」というのはわかるので、
それを元に弾いてしまえばいいのではと

ずっと壁になっていた、case6をついに突破しましたヽ(`･ω･´)ノ

さらに、「ある横幅を基準に考えて、縦幅を小さい順に探査したときに、
ある高さで答えが0ならば、それ以降の縦幅を計算するのは無駄」と気づきました

つまり、「横2×縦3」のオブジェクトが入らない状況で、
「横2×縦4」のオブジェクトは絶対に入りません
そこを削ればいいのではと

case6突破時点の11sから8sに縮まりました（ ﾟдﾟ）o彡ﾟ

そして深淵へ・・・

ここからはひたすら細かいチューニングを繰り返しました
オブジェクトの生成を抑えてみたり、
最終的には足し算の回数まで気にしてみたりΣ(ﾟДﾟ)ｶﾞｰﾝ

case6で4sまで縮まったものの、ここで完全に行き詰まりました・・・(´-ω-)

ちゃんと調べてみる

ここでいったん立ち止まり、わかっている問題を整理してみました

  • ループが多い
    • もっと単純な探査ができないか？
    • つまり、「計算する次元」を落とせないか？
  • データ構造が複雑
    • 構造が複雑だから、探査に時間がかかる

「衝突」という言葉を使っていますが、
ここまでくるとまさに、ゲームの当たり判定の話だと思いまして、
こちらの本の衝突判定をじっくり読んでみました

ゲームプログラマになる前に覚えておきたい技術

ゲームプログラマになる前に覚えておきたい技術

2次元を1次元ベクトルに落とし込む方法とか、
いろいろ書いてありまして、これをふまえて実装してみたのですが、
case4以降でエラーになってしまいました(´･ω･`)

1行の判定を1回の計算で済ませる

「効率の良い衝突判定」を調べていくうちに、ふと思い当たるものがありました
「bit演算でええやん」、とΣ(ﾟДﾟ)ｶﾞｰﾝ

b：盤面のある行
o：オブジェクトのある行

b:1001
o:0011
b & o = not 0 => 衝突

b:1001
o:0110
b & o = 0 => OK

b:1001
o:1100
b & o = not 0 => 衝突

このように、例えば「幅2」を表すbit列をずらしながら、
その列のbitパターンとand演算を行い、
「0」になるか否かという、実にシンプルな判定になります

データの構築もただのArrayになりますし、
判定ラインも横に対してのみ考えれば良くなります

さらに、横のパターンだけ「オブジェクト列に存在する値」にしつつ、
縦の探索方法を変えました

「何回連続して衝突しなかったか？」＝「そこに入る最大の縦サイズ」であり、
それより小さいものは全て入るはずです

コードの動きを具体的に書いてみますと・・・

盤面
1000
1001
1101
0001

探査するパターン
0110

1行目
1000 & 0110 => 0

counter += 1
h[1] = 1

2行目
1001 & 0110 => 0


counter += 1
h[1] = 2
h[2] = 1 

3行目
1101 & 0110 => not 0


counter = 0
h[1] = 2
h[2] = 1  


4行目
0001 & 0110 => 0 

counter += 1
h[1] = 3
h[2] = 1  

=> 横2×縦1は3個、横2×縦2は1個入る

普段bit演算は使わないというか、個人的に苦手なので避けていたので、
これに思い当たるまでにだいぶ遠回りしましたね・・・(´-ω-)

そんなわけで、無事に全てのTest caseを突破しました∠( ﾟдﾟ)／

一応まとめ

ご覧の通り、最終的なコードはver5までと比較にならないほどシンプルです
やはり、効率の良いコードはシンプルに落ち着くのだと思います *2


for "https://paiza.jp/poh/paizen"


普段、ここまでチューニングを要求されるシステムは担当してませんし、
どちらかといえば可読性を優先してコードを書いているつもりですが、
たまにはこういうコードも面白いですね

次回も期待しています(`･ω･´)ノ

追記

どうも判定には「S」どころか「SS」や「SSS」もあるそうなのですが、
個人的には「S」だけ取れれば十分です(((((( ;ﾟДﾟ)))))

さらに追記

ちょっといじったら「SSS」に・・・(；　д )　ﾟ　ﾟ

カウントアップのところって、
カウンタがリセットされるときで十分だよな・・・と思っただけなのですが

つまり、カウンタが3まで行ってリセットされるとすると、
縦1は+3、縦2は+2、縦3は+1・・・となっているはずです

そのように数行書き換えただけなのですが、
それでカウントアップの計算回数が劇的に変わったと思われます

*1: 前回のコードと結果はこちら(´･ω･)っ https://gist.github.com/parrot-studio/7763295

*2: とはいえ、それは「結果」なのであって、最初から効率の良いコードが書ければいいのですが、普通はそこまで簡単ではありません。だからこそ、思考の過程を残しておくことで、「次回」に生かせるのではないかと。（Gitのような）「コード管理」についても、「履歴」という「思考の過程」を残せることが、重要なメリットだと思っています