ぱろっと・すたじお

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

「デザイン」は難しい

サービス ccpts

別に役に立つ話ではなく、ほとんど愚痴というか言い訳なのですが・・・Σ(・ω・ノ)ノ

先日公開した「チェンクロパーティーシミュレーター」のデザインを大幅に変更しまして


リリース後も機能追加にあわせて頻繁に修正はしていたのですが、
基本的なところから考え直したのは初めてです

当初はデータ（各アルカナの属性情報）が少なく、
「少ないなりにどうごまかすか？」と考えていたのですが、
データがメンテされてきたので、「必要な情報をわかりやすく」に変更したかったのです


変更後がこちら(´･ω･)っ

「おい、たいして変わってないじゃないかщ(ﾟДﾟщ)」と思われるかもしれませんが、
それは結果であって、ここに落ち着くまで二転三転したわけですよ

大前提として「サマリーの情報を増やす」というのがあって、
それだと元のUIでは検索結果が縦に伸びすぎるので、
ページ送り的なものが必要だろうと*1

で、ページ送りとか横スクロールのライブラリをいろいろ試したわけです

それぞれプロトタイプを作ってみた結果、
「filpsnap.js」がシンプルで私の好みに合っていたし、
違和感も少なかったのです

しかし、これを適用すると「ドラッグアンドドロップ」で表示がおかしくなるのです
できることはできるのですが、copyした要素が裏に回ってしまうという・・・(´-ω-) *2

仕方なく、シンプルなページ送りを自分で実装したわけですが、
次にやりたかったのが「スワイプでページ送り」です

せっかくタブレット対応をうたっているのだから、
やっぱりスワイプで切り替えしたいじゃないですかщ(ﾟДﾟщ)

スワイプ自体はすでに使っている「hammer.js」でいけます

問題は、スワイプのイベントを（検索結果エリアに）セットすると、
ドラッグイベントが覆い隠されることでしてΣ(ﾟДﾟ)ｶﾞｰﾝ

海外のフォーラムでもこの問題が挙がっていました

javascript - Draggable code not working with hammer.js - Stack Overflow

結局、ページ送りボタンを大きめにすることで別の対応を入れました
今さら「ドラッグアンドドロップで編集」という概念を変えたくないので、
妥協せざるを得ないところで(´-ω-)


そもそも、「デザイン」って妥協の連続だと思うわけですよ

自分の中に「理想のUI」はあるけど、それを表現するには制約がたくさんあり、
一方で「使う側にとっての使い勝手」も考えなければならず、
それに「明確な答え」なんてないわけで

こういう経験をすると、「デザイナーさんの苦労」も見えてくるわけです
「妥協点探し」は相当大変なんだろうな・・・と (´-ω-)

もちろん、「プロのプログラマ」もさまざまなリソースを加味して妥協しまくりです
でも、「満たすべき仕様」がある程度はっきりしているので、
少なくとも表面上そこだけはクリアする、という基準があるわけです
（でないとコードは書けない・・・ですよね？）

「目に見える部分」だからこその難しさは
実際にサイトを作らないとわからないと思いますし、
たまにはいろいろ試してみてはいかがでしょう(´･ω･)？

*1: 「検索エリアの要素をパーティーエリアにドラッグアンドドロップする」という都合上、ドラッグ距離は短い方がいいというか、長いと使えませんよね・・・

*2: ライブラリの実装方法を調べて原因はわかりましたが、簡単にどうにかできるものではありませんでした(´･ω･`)

天才火消しエンジニア霧島さんのトラップに引っかかった件

Ruby POH

今回はいろいろ油断があったわけですが・・・

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite

・・・って、よく見たら霧島さん＝挑戦者＝私でしたかΣ(ﾟДﾟ)ｶﾞｰﾝ
それだと美しくないなので、霧島さん（26歳女性）の依頼で問題を解いたという体にしてですね・・・

とにかく今回は油断があったわけです

  • タイトルに「Lite」と入っていた
    • たぶん簡単なんだろうと誤解した
  • 問題が前回に比べて簡単に見えた
    • 前回はまず仕様をどうコードに落とすかが壁で、今回は書くだけなら簡単
  • 前回うかつにもSSSを取ってしまった
  • 最初に書いたコードでCase5を通過してしまった
    • しかも0.02sというかなりのタイムで

特に最後のが致命傷で、「あ、もうちょっとやん」と思ってしまったんですよね・・・
そこからが面倒だったのに(´-ω-)

とはいえ、前回に比べれば比較的シンプルで、
アルゴリズム勝負になっていたのは間違いありません

問題をどう捉えるか？

最初は1回目*1のような簡単な問題だと思ったのですが、
あれは「ペア」という縛りがあったのに対し、
今回は「任意のn個」（n <= 会社数）の組み合わせが存在します

nが小さいうちは総当たり・・・つまり、
全ての組み合わせについてコストを計算したあと、
条件を満たすデータを探す、という手も使えます

result = []
(1..(companys.size)).each do |n|
  # n個の組み合わせを全て抜き出す
  companys.combination(n) do |list|
    # 人数が足りないなら無視
    next if list.map(&:member).inject(:+) < need_member
    # コストを計算
    result << list.map(&:cost).inject(:+) 
  end
end
# 最小が答え
puts result.min

擬似的なコードですっごく雑に書くとこういうことですが、
nがちょっと大きくなるだけでも、
あっという間に組み合わせが発散してしまいます(lllﾟДﾟ) *2

一方で、ある程度総当たりしないと、
「どれが最小か？」はわからないのも事実です

1回目の時は目標金額が設定されていたため、
ある程度答えが見えたら切り捨てることも可能でしたが、
今回その手は使えません

結果的に、見た目は簡単そうでも、
実際には「高速なアルゴリズムを使う」か、
「適切な足切りを探す」か、その両方かが必要だったのです(´-ω-)

いきなりCase5を突破

以上をふまえてコードを書き始めたわけですが、
前回さんざん苦労させられた結果、
処理速度を上げるポイントはだいたいこんなところだろうと

  • データを「リスト」として処理する
    • 前回は盤面をbit化し、数値の配列として処理した
  • （Rubyの）eachで回すより、indexでアクセスした方が早い
    • RubyのEnumeratorは高性能だが、オブジェクトアクセスなので遅い
    • とはいえ、Arrayもオブジェクトなので、Cの実装レベルで最適化されている可能性
  • 無駄なデータを早めに刈り取る
    • 明らかに要件を満たせないデータはそもそも処理しない
  • うかつなソートは遅くなる

リストを探索するルートは以下のようになるはずです

1つ目を起点にする
  2つ目を足してみる
    3つ目を足してみる
      4つ目を足してみる
    4つ目を足してみる
  3つ目を足してみる
    4つめを足してみる
  4つ目を足してみる
2つ目を起点にする
...

1
1-2
1-2-3
1-2-3-4
1-2-4
1-3
1-3-4
1-4
2
...

つまり、ツリー構造の探査になります
で、各探査のタイミングで、条件に見合わないと確定したら切ってしまうわけです
ある時点でわかっているコストより、そこで計算したコストが大きければ無駄です

これを再帰的に処理するように書いたのが最初のコードです(´･ω･)っ

この時点でいろいろ考慮されていたのもあり、
最初からCase5で0.02sを叩きだしたわけですが、
ここからが問題でした(´-ω-)

メンバー数で足切りする

計算量を減らすには、「ここより先は無駄である」ということが、
「明確に言い切れる」条件を探す必要があります
今回の場合、この「明確に言い切れる」の部分が難しいのです

まず思いついたのが、「メンバー数」です
あるノードを見ている時に、あと20人必要だとしても、
その先の全ノードを足しても20人に満たないならそこで切り上げることができます

しかし、「この時点では」無駄でした(´･ω･`)

深さで足切りする

先ほどのcombinationを使った擬似コードにおいて、
例えばn=3の時点で答えの候補が見えているのであれば、
n=4でそれより小さい値が見つかるとは思えません

そこで、「深さ」の概念を追加してみたわけですが、
元々ツリーの途中で適切な足切りが実装されており、
あまり効果がないどころか、むしろループを増やすだけでした(´-ω-)

そもそも、nが大きい場合に、
n=2とか3で組み合わせ数が爆発する問題は解決しないわけで・・・

試行錯誤

この辺から完全に行き詰まったのですが、
やはり複雑なデータ構造を作るほど遅くなるため、
どうにもうまくいきません

問題が良くできているので、「一か八か、データ依存」的な条件を追加しても、
今度はCase5すら通らなくなるのです

コスト効率を考える

ここでいったんしばらく時間をおきまして、
一度頭をリセットしてやり直しました

冷静に考えると、足切りするには何らかのソートが必要です
でも、今回はデータのベクトルが「メンバー数」「コスト」の2次元なので、
どちらかの概念でソートしても、足切りがうまくいかないのです

ならば1次元化、つまり「コスト/メンバー数＝コスト効率」でソートすればと、
一度は考えていろいろ試したのですが、決定打がありませんでした

しかし、冷静に考えれば、「コスト効率×メンバー数＝コスト」です

もしコスト効率でソートされている場合、
ある時点での「コスト効率×残りメンバー数＋現時点でのコスト」が、
最小値を超えてしまうのであれば、それ以降の計算は無駄です

例えば、あるノードの時点で
「わかっている最小コスト100、コスト効率1.2、残り20人、現時点でのコストの和が80」
だとします

すると、「次のノードのコスト効率」は1.2以上であることが保証されており、
コストが「80+1.2*20」以上になることが確実です
なので、ここで切り上げてしまっても問題ないことになります

これを追加したところ、Case6を突破しました(`･ω･´)

もう一度メンバー数で足切り

先ほど一度は棄却した「これ以降はメンバー数を満たせない」という足切りですが、
今度は一次元の概念でソートされており、
うまく寄与するのではと予測しました

ついでに、コスト効率に関してももうちょっと見直しまして・・・

・・・Case7を突破し、S評価を獲得ですヽ(`･ω･´)ノ

まとめ

実は、前回の2回目で行き詰まった際、
「次元を落とす」というのを試していました

前回はうまく当てはめることができなかったのですが、
今回の場合はまさにぴったりだったようです(`･ω･´)

逆に、このような1次元化を導入したので、
探査ロジックを見直すことで、
まだまだ数秒縮められる気がします

「起点」という考え方を捨てて、
全体を一つのツリーとして見なせば、
ループを削れるのはわかっているのですが・・・

（まさにこれを書きながら気づきました
　前回もそうだったのですが、「行き詰まったらBlogに書いて整理」というのも、
　一つの手法かもしれません）

・・・暑いし、やることが他にある*3し、あとはお任せしますΣ(・ω・ノ)ノ


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

*1: https://paiza.jp/poh/ec-campaign 私のコードはこちら(´･ω･)っ https://gist.github.com/parrot-studio/7763295

*2: ちょっぴりグレーな方法・・・適当なところで例外を上げるようにしただけ・・・で確認したところ、Case5まででだいたいn=10、Case6でn=30程度でした　おそらくCase7は最大のn=50でしょう

*3: 「チェンクロパーティーシミュレーター」を開発中です(´･ω･)っ http://parrot.hatenadiary.jp/entry/2014/07/15/142913

「チェンクロパーティーシミュレーター」を公開しました

サービス Ruby Rails jQuery MySQL ccpts

昨年からだいぶはまっていた「チェインクロニクル」ですが、
そのパーティー構成を編集して共有するサイト、
「チェンクロパーティーシミュレーター」を公開しました


Get our light! - チェンクロパーティーシミュレーター
（現時点ではまだβ版としています）

経緯

セガさんが「サポーターサイト」というのを募集し始めまして、
素材利用申請をしようとしたところ、
まずサイトを登録する必要があることが判明しましてΣ(ﾟДﾟ)ｶﾞｰﾝ

セガR&D1サポーターズサイト

そこでBlogでも書き始めようかと思ったのですが、
あまりしっくりこなかった*1ので、
いろいろ考えた結果、こういうサイトになったという・・・

元々、私はROを長いことやっていて、
こういった便利ツールにはさんざんお世話になったのもあり、
チェンクロでも何か作れないかな・・・と

アーキテクチャ

今回のサイトはできるだけブラウザ上で完結させることを目指しましたが、
それ以上に「タブレット*2での動作」を意識しました

ずっと「PC向けだけど、たまたまタブレットでも動く」ってサイトばかりだったので、
「タブレットで "快適に" 動く」というのはやったことがなかったのです

時代的にPCよりタブレットやスマフォデバイスがメインになってますし、
そもそもチェンクロ自体、タブレットでプレイしているわけで、
タブレットで動くのは必須だろうと

タブレット向けに調整するまでのメモ

サーバ側のAPIは（得意分野なので）あっという間にできたものの、
そこからView側を調整するのにひたすら時間がかかりました(´-ω-)

せっかくなので、引っかかったポイントを覚えている範囲でメモしておきます

1. clickイベントの動作

ボタンでもリンクでも、たいていのものは「クリック」できるわけで、
clickイベントは相当使いまくります

$("#search").on 'click', (e) ->
  searchTargets()
  e.preventDefault()

例えば「検索ボタン」のコードがこれですが、
PCだけ考えればこれで十分すぎます

でも、このままタブレットで動かすと、
タップしてからの反応が恐ろしいほど遅いです
「あれ？　動かない？」と思う程度のラグがあります(´･ω･`)

原因はモバイルブラウザにおけるイベント処理にあるわけですが、
モバイルブラウザで「click」イベントを処理する前に、
大量のイベント判定をしているようなのです

http://patrickhlauke.github.io/touch/tests/results/

そこでいろいろ調べてみたのですが、
touchstart/touchend等できっちり書くやり方は面倒すぎるので、
もっと楽な方法はないかな・・・と

そこで見つけたのがこれです(´･ω･)っ

http://hammerjs.github.io/

これを読み込ませて、先ほどのコードをこう直します

$("#search").hammer().on 'tap', (e) ->
  searchTargets()
  e.preventDefault()

すると、PCではclick、タブレットでは「それっぽいタップ動作」になり、
非常に簡単ですヽ(`･ω･´)ノ

Railsに組み込むためのgemもあります

https://github.com/vincent-pochet/hammerjs-rails


2. ドラッグアンドドロップの実装

いつもの私ならこの辺でリリースレベルなので、
データの入力とかちまちま進めていたのですが、
試しに会社の人*3に軽くいじってもらったところ・・・

「ドラッグアンドドロップができないのが違和感」

・・・と言われましたΣ(ﾟДﾟ)ｶﾞｰﾝ

元々、「候補をクリック -> PT欄をクリック」という操作だったのですが、
このデザインだと「（アルカナ自体を）動かしたくなる」、と

最初に設計していた時点で、「ドラッグアンドドロップ」は考えていたものの、
とりあえずプロトタイプを・・・ということでスルーしてしまったのですが、
やはり対応しないとダメでした(´･ω･`)

これもやり方はいろいろあるものの、
面倒なのでjQueryUIを使うことにしました

ただ、さっきのclickイベントより深刻で、
PCで動くように実装しても、タブレットでは全く動きませんΣ(・ω・ノ)ノ

そこでまた調べたところ、「jquery.ui.touch-punch.js」というのを発見

http://touchpunch.furf.com/

こちらは読み込ませるだけでタブレット対応できてしまうので、
hammer.js以上に簡単です(｀･ω･´) ｂ

ただ、hammer.jsと同時に使う場合、
裏で使っているイベントが競合する場合がある*4ようで、
イベント登録する要素を工夫するとか、気をつけないといけません

3. デザイン周り

プロトタイプからたぶん3周くらい回って今のUIにしてますが、
それでもまだ微妙な感じがします(´-ω-)

チェンクロは「横画面のUI」で、アルカナは「縦表示」なので、
そこをデザインの基本にしました

ぶっちゃけ、アルカナを横長にして縦に積み重ねた方が、
デザインを考えやすかったのですが、
やはりゲームにあわせたかったので・・・

一方で、Twitter経由でサイトを見た際に、
Twitterはどうしても縦画面で見るのもあって、
やはり違和感がある、という意見もいただきました

せっかくBootstrapを使っているわけで、
画面の幅に合わせてデザインを変えられるのがベターですが、
まずは基本的な部分だけリリース、ということで、一つ(´･ω･`)

"全部"対応してから・・・とかやっていると、
いつになってもリリースできませんからね・・・

一方で、「どこを最小限とするか？」は、
「これは何をするためのサイトなのか？」が定義されていないとわからないので、
やっぱりコンセプト設計は大事です*5



追記

そもそもPC/タブレットを想定していたとはいえ、
それ以外のデバイスで画面がめちゃくちゃってのも気分が悪いので、
閲覧機能だけ暫定対応しました

「タッチで操作する」という前提なので、
スマフォの縦長画面だと操作しづらいのは見えているのですが、
どうしたものですかね・・・(´-ω-)

それにしても、classを指定するだけで、
ここまでさくっと表示/非表示やデザインを変更できるあたり、
やはりBootstrapはすばらしい・・・

追記2

どうでもいい話ですが、開発中はハッシュタグを「#ccpt」で考えていたところ、
Twitter検索してみたら海外で何かに使われていたので、「#ccpts」に変更しました

こういう名前空間の調査を適当にやっちゃうと、
いろいろあとで面倒ですからね・・・(´-ω-)

*1: というより、すでに2本書いていて、一方が滞っているのに、さらに増やしても・・・という(´-ω-)

*2: 個人的に想定しているのはiPad mini

*3: うちのチームは全員チェンクロをやっていて、専用のメーリングリストまであったりΣ(・ω・ノ)ノ

*4: おそらくどちらもtouchstart/touchendで何かするという処理のはず・・・ちゃんと見てませんが

*5: アジャイルサムライの「インセプションデッキ」がわかりやすいと思います

「女子大生とペアプロ問題」の言語別通過率を分析してみる

Ruby はてブ POH

先日私も参加した「女子大生とペアプロするだけのの簡単なお仕事」ですが、
最終的な結果がBlogで公開されました

【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選 - paiza開発日誌

これの言語別通過率が興味深かったので、
もうちょっと突っ込んだ分析がしてみたくて、
通過率をグラフ化してみました(´･ω･)っ



ここからいろいろなことがわかると思いますが、
まずはTwitter上でいくつか挙げてみたのをメモっておきます


大前提として、「最速」はある一人のエンジニアにより達成されるものですが、
「通過率」は統計的な値であり、言語に関わるエンジニアの傾向を、
ある程度表していると推測されます

もちろん大前提として、以下の要因を満たす人の範囲で、ですが

  • 「エンジニア」である
    • プロかアマかは無関係ですが、おそらくはプロが多かったのではと
  • この手のチャレンジ的なものに興味がある
  • あの仕様を理解し、何らかのコードに落とし込めるスキルがある
    • 理解できないのであれば、コードが書けない or 通らないはず

それをふまえた上で、私が仕事で使ったことがある言語の範囲で
いろいろ推測してみますと・・・

Javaは言うまでもなく、業務系のシステムでよく使われる言語です
言い換えれば、フレームワークに乗せて終わり、といった
単純な開発は少ないと思われます

一方、Rubyを含めたWeb系言語は、
比較的フレームワーク上で完結してしまうケースが多く、
特にRubyはRailsの出来が良すぎる*1ため、そこに特化している人が少なくないのではと

今回の問題は、純粋にアルゴリズムとチューニングを要求される問題であり、
「独自の仕組み」を自分で考えないといけません

また、Web系システムにおけるチューニングがフロントエンド主眼だとすると、
業務系システムのチューニングは大規模データに対するものが多いでしょう

それこそ、TwitterはフロントエンドこそRubyですが、
バックエンドはScalaで書かれている*2わけですし、
言語にはやはり得意分野があります

あくまでこのキャンペーンに挑戦した人達の範囲で考えたとしても、
RubyのエンジニアよりもJavaエンジニアの方が、
大規模データに対する問題解決とチューニングに慣れている、ということかもしれません

ただし、今回の問題でJavaはC等と同じコンパイル系言語として扱われていますし、
スクリプト言語であるRuby等に比べると、
チューニングのやりやすさで優位、という側面もあるかとは思います

実際の開発においても、Ruby等で無理矢理チューニングするよりも、
バックエンドはJavaという事例が多くなり、
Rubyにおけるチューニングノウハウが浅い、という可能性はあるかもしれません

あと、個人的に気になるのはPHPです

どうもPHPが揶揄される傾向にありますが、
「エンジニアではない人をエンジニア視点で評価している」だけな気がしていて、
「PHPエンジニア」のレベルはある意味「他と変わらない分布」*3なのではと思っています

実際、今回の結果を見る限り、RubyよりもPHPの方がむしろ好成績なわけで、
PHPがWebフロントエンドだけでなく、バックエンドでも使われており、
バックエンドのエンジニアのレベル分布は他の言語とそう変わらない、ということかと*4

なお、今回一番勉強になったのは、
この手の問題を解くためのアルゴリズムが存在していたことですΣ(・ω・ノ)ノ

いもす法 - いもす研 (imos laboratory)

最速のコードはこれをふまえてチューニングされていたわけですが、
これを知らないまま独自にCase7を突破できたことは、
それなりに価値があったと信じたい・・・・・・(´･ω･`)

*1: しかも、追加で何か要求があったとしても、gemを追加すれば解決してしまうという、優秀なエコシステムもありますね

*2: 以前はそうだったはずですが、今はどうなんですかね・・・(´-ω-)

*3: スーパーエンジニアもいれば、普通の人もたくさんいるという、当たり前の構図

*4: 実際、私がPHPで仕事をしていた時は、バックエンドもPHPでしたし、一方でJavaを使ったりもしていました

「女子大生とペアプロするだけの簡単なお仕事」で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のような）「コード管理」についても、「履歴」という「思考の過程」を残せることが、重要なメリットだと思っています