第7の恋愛SLG（「プログラミングで彼女をつくる」を解いた件）

ふと、セブンスドラゴン3が終盤で止まっているな・・・と思い出しましたが、
とにかく今回の「POH7」は恋愛SLG仕立てだそうでΣ(・ω・ノ)ノ

paiza.jp

まあ、要するに問題を解くとアイテムがGETできて、着せ替えも可能ってだけなのですが、
やっぱり見せ方は大事ですからね・・・(´-ω-)

そんなわけで、今回は問題が多そうだったので、
計画的にクリアしようと初日からざっと問題を確認したところ・・・

・・・1日で終わりましたΣ(ﾟДﾟ)ｶﾞｰﾝ
（上の画像には追加問題2問を含む）

最下段の3問が高難易度で、後は（プロのプログラマなら）即座に書き下せる難易度ですので、
その3問の話だけ考えたことを書いていきます

一応、全てのコードはこちらに(´･ω･)っ

https://gist.github.com/parrot-studio/96c758f393806a7df6ac

ついでに、過去の問題を解いた記事はこちら

parrot.hatenadiary.jp

parrot.hatenadiary.jp

メガネ

すぐに問題は理解できると思います
ただ、どう「効率よく計算するか？」が難しいのです(´-ω-)

単純に考えると、それぞれの盤面を配列（できれば1次元の）に保持し、
座標を動かしながら、値が一致するかを「各座標で」「順番に」比較していけばいいのですが、
これだと比較にO(m^2)かかるので、おそらく時間切れでpassできませんΣ(ﾟДﾟ)ｶﾞｰﾝ

これと類似の「2次元の盤面をparseする問題」がPOH2で出ており、
これを解くのに1週間以上かかったわけですが・・・

parrot.hatenadiary.jp

・・・もちろん、今回の問題もこれの応用でいけます

盤面の一行を「0b0010=2」のように捉えれば、
盤面はそれぞれ「n個の数値の配列」と「m個の数値の配列」と考えられます

あとは、座標を動かして比較するのに必要なところを抜き出せばOKです

# 例として、「0 1 1 0」に「0 1 1」が含まれるかを調べる

# 3桁分のマスクを作る
mask = ('1'*m).to_i(2) # => 0b0111

# 目的の値とand演算する
t = 0b0110 & mask # => 0b0110

# 比較
t == 0b0011 # => false

# maskを一桁ずらす
mask = mask << 1 #=> 0b1110

# 目的の値とand演算する
t = 0b0110 & mask # => 0b0110

# ずらした桁を戻す
t = t << 1 # => 0b0011

# 比較
t == 0b0011 # => true

実際のコードは、これを座標をずらしながら、
複数行＝m個の数値の比較でやっているだけです

https://gist.github.com/parrot-studio/96c758f393806a7df6ac#file-ex1_glasses-rb

この方法だと「たかだかm個の数値同士の比較」に落とし込めるので、
だいぶ高速化できますヽ(`･ω･´)ノ

ただまあ、これは以前1週間以上悩んだからこその解法であり、
やはり積み重ねは大事ですね

サンタ服

3つの問題の中では最も簡単な問題です
文章を仕様に落とし込めれば楽勝かと(`･ω･´)

問題をよく読んでいくと、求めるのは「体積」なのですが、
「水平方向=z軸」には切りません
つまり、「最小の"面積"」を求めて、最後に高さをかければ十分です

ナイフは常に「並行」に入ります
なので、単純に「x軸とy軸それぞれで一番小さい幅」をかけたものが答えです

しかし、渡されるのは「位置」であって「幅」ではありません
しかも、渡される順番も適当です

そこで、いったんx軸とy軸ごとに配列に格納し、
ソートした後、隣同士の座標で幅を計算＝引き算して、
「一番小さな値」を取り出せばOKです

ここまで問題をかみ砕いてしまえば、書くのはとても簡単です(｀･ω･´) b

https://gist.github.com/parrot-studio/96c758f393806a7df6ac#file-ex2_santa-rb

ポイントは「端っこの値＝0とx（or y）」を配列に入れてしまうことです
そうすることで、特別なif文など不要になり、単純なリスト処理でけりがつきます

水着

一応ラスボスじゃないかとは思いますが・・・
これをクリアすると、海の背景も開放されますし

問題の意味はすぐに理解できますが、
ポイントは「莫大な計算量をどうするか？」です

仕様通りに計算すると、Rubyなら一応ベタに計算できますが、
言語によっては桁あふれになりますし、
Rubyだとしてもパフォーマンスが最悪です(´-ω-)

そこで、どう間引くかが問題になるのですが・・・
正直、自分の中でも確信は持てていません

それでも一応1秒程度で実行できたのがこちらです

https://gist.github.com/parrot-studio/96c758f393806a7df6ac#file-ex3_swimwear-rb

基本はただかけ算をしていくだけですが、
「適当な桁数」で数値を補正しています

1. 数値を文字列にして桁ごとに分割
2. ひっくり返して頭から0を取り除く
3. 「適当な桁数」の数字文字列を取り出す
4. 再びひっくり返し、結合してから数値化

どうせ最後に下の桁の0は全部取り除かれますし、
欲しいのはその上の9桁なので、途中でそれを計算してしまえば、
ある程度の桁数に抑えられるでしょう・・・と

とはいえ、途中の桁数でぴったり9桁にすると、
次の数値をかけた時に必要な桁のところに誤差が来てしまうので、
最初12で実行し、11->10と下げていって、10では止まったので11・・・という

ただ、いろいろ試行錯誤はしたのですが、どうしても1秒を切れません
おそらく「reduce」の処理をもっと最適化するか、
そもそもやり方を変えるか・・・(´-ω-)

最初は毎回間引いていたので、一定回数ごとに抑えたところ、
8秒だったのが1秒まで削れました
つまり、間引く処理が遅いことになります

でも、あまり間引く回数を減らすと、今度は桁が大きくなりすぎて計算が遅くなります
まあ、いろいろやっても1.11秒と1.13秒ばかりなので、
なんらかの限界の可能性はありますが・・・

Rubyに関していえば、今回の問題はおそらくBignumの範囲で計算されているので、
Fixnumの範囲で押さえられないか・・・とか、
そのあたりでしょうね(´･ω･`)

まとめ

ここ数回の難易度に比べると、元の難易度に近くなったかな・・・という気はします
サンタ服の問題はともかく、他2問はこの手の問題をやったことがないと難しいでしょう(´-ω-)

むしろ、このサイトのメインターゲットである、
「転職を考えているエンジニア」の観点だと、
この3問以外の、残りの問題があっさり解けるか・・・の方が大事です

それぞれベタな書き方は可能ですが、面接で効率の良いコードを書けると、
「お、この人はいいかも」と思わせることができます(`･ω･´)
（というか、面接官にその観点がない場合、その会社は怪しいかと・・・）

https://gist.github.com/parrot-studio/96c758f393806a7df6ac#file-others-rb

1〜数行で書ける問題ばかりですので、いろいろ試してみてはどうでしょう