第7の恋愛SLG（「プログラミングで彼女をつくる」を解いた件）
ふと、セブンスドラゴン3が終盤で止まっているな・・・と思い出しましたが、
とにかく今回の「POH7」は恋愛SLG仕立てだそうでΣ(・ω・ノ)ノ
まあ、要するに問題を解くとアイテムがGETできて、着せ替えも可能ってだけなのですが、
やっぱり見せ方は大事ですからね・・・(´-ω-)
そんなわけで、今回は問題が多そうだったので、
計画的にクリアしようと初日からざっと問題を確認したところ・・・
・・・1日で終わりましたΣ(ﾟДﾟ)ｶﾞｰﾝ
（上の画像には追加問題2問を含む）
最下段の3問が高難易度で、後は（プロのプログラマなら）即座に書き下せる難易度ですので、
その3問の話だけ考えたことを書いていきます
一応、全てのコードはこちらに(´･ω･)っ
https://gist.github.com/parrot-studio/96c758f393806a7df6ac
ついでに、過去の問題を解いた記事はこちら
メガネ
すぐに問題は理解できると思います
ただ、どう「効率よく計算するか？」が難しいのです(´-ω-)
単純に考えると、それぞれの盤面を配列（できれば1次元の）に保持し、
座標を動かしながら、値が一致するかを「各座標で」「順番に」比較していけばいいのですが、
これだと比較にO(m^2)かかるので、おそらく時間切れでpassできませんΣ(ﾟДﾟ)ｶﾞｰﾝ
これと類似の「2次元の盤面をparseする問題」がPOH2で出ており、
これを解くのに1週間以上かかったわけですが・・・
・・・もちろん、今回の問題もこれの応用でいけます
盤面の一行を「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
基本はただかけ算をしていくだけですが、
「適当な桁数」で数値を補正しています
- 数値を文字列にして桁ごとに分割
- ひっくり返して頭から0を取り除く
- 「適当な桁数」の数字文字列を取り出す
- 再びひっくり返し、結合してから数値化
どうせ最後に下の桁の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〜数行で書ける問題ばかりですので、いろいろ試してみてはどうでしょう
FRP(Functional Reactive Programming)を試した話＋JS周りのあれこれ
ここのところ、久々に技術調査をがっつりしており、
そのあたりをメモするのがメインの記事になりますので、
いつも以上にまとまりがないと思います(´-ω-)
私はサーバサイドのエンジニアで、Rubyを主に扱っており、
仕事でもほぼRailsを書いていたのですが、
ちょっとした事情によりNode.jsも書くことになりまして*1
今までJavaScriptを主体にしたコードを書いたことがなく、
プロトタイプ*2をいじくり回しているのですが、
やはり「本物」っぽいコードを書いた方がいろいろつかめるわけです
ということで、手持ちの「チェンクロパーティーシミュレーター」（以下ccpts）で、
いろいろ試しております...φ(･ω･｀)
ということで、以下考えた思考過程のメモなどを
FRP(Functional Reactive Programming)
Node.js・・・というかJavaScriptを本格的に書きはじめて、
最初に引っかかったのはやはりcallbackの多さです
あらゆる処理を非同期で処理するのが前提ですからね(´-ω-) *3
もちろん、有名どころではPromise*4を使うのが定番で、
最初はそれで書いていたのですが、「もっといい手」があるのでは・・・と気になりまして
そんな時、ちょうど流れてきたのが「Rx」の話でございます*5
Rx自体は別にJavaScriptに限った話ではなく、不完全ながらRubyにもあるわけですが、
フロントエンドで使われることが多いので、本家のC#とJavaScriptがやはり目立ちます
でまあ、先ほどの記事を読むとなんとなくわかる・・・というか、
わかった気になると思いますが、要するにRxのようなFRPとは・・・
「非同期処理と同期処理を一つのストリームで扱えるもの」
・・・であり、Rubyの文脈で雑に書くならば・・・
「イベントも扱えるようになったEnumerator」
・・・と考えればだいたいあってます
そもそも、プログラムを書く側からすると、非同期処理だろうと同期処理だろうと、
「渡した値に対応する値が返ってくること」にしか「興味がない」わけです
（まさに「関数」です）
理想的には・・・
「イベントが発生」->「必要な値に生成」->「APIに投げる（非同期）」
->「結果を得る」->「画面を描く」
・・・という流れができればいいわけです(`･ω･´)
とはいえ、わかった気になっても、実際に書こうとすると、
正直全く書けませんで・・・
そこで、まずは「callback」と「Promise」を排除することを目的に、
ccptsを書き直し始めました
当初、RxJSで書いてみたのですが、リリースしようとしたところで、
妙に動作が遅くなる問題が発生し、JavaScriptに特化した「Bacon.js」に切り替えました
Rx(JS)の方が「本質的」ですが、Bacon.jsの方が「実用的」なので、
比較的楽に書けました
例えばこんな感じで(´･ω･)っ
# Searcher @search: (params, url) -> params ?= {} params.ver = ver result = Bacon.fromPromise($.getJSON(url, params)) # AjaxのPromiseをStreamに変換 result.onError (err) -> $("#error-area").show() result @searchArcanas: (query) -> if cached # キャッシュがあったら as = ... # キャッシュから読み込む処理 return Bacon.once(as) # 値を直に返す result = @search(query.params(), searchUrl) result.flatMap (data) -> as = ... # APIから取得して返す Bacon.once(as) # Viewer Searcher.searchArcanas(query) .onValue (as) -> pager = createPager(as) replaceTargetArea() # 結果のrender処理
https://github.com/parrot-studio/cc-pt-viewer/commit/28793357cac2f08396240fb2104fa2dac615fc45
キャッシュを返す時は同期的な処理ですが、
APIを経由する時は非同期処理です
それを一つのオブジェクトで包んで返すことで、
受け取る先ではどのような経緯でデータがやってきたのか、
意識しなくても書けるわけです(`･ω･´)
これでだいぶ慣れてきたので、イベントからrenderまでを本格的にStreamでつないでみることに
# 検索ボタンを押したとき、queryを構築するStream queryFromSearch = $(".search") .asEventStream('click') .doAction('.preventDefault') .doAction -> $("#search-modal").modal('hide') .map -> Query.build() # 各queryのStreamを合流させる queryStream = queryFromSearch # 検索ボタンQuery .merge queryfromQueryLog # 検索ログからきたQuery .merge queryFromInit # 初期状態 # queryでAPIを叩いて結果を得る querySearchStream = queryStream .map (q) -> (if q.isEmpty() then recentQuery else q) .flatMap (query) -> searchTargets(query) # 他の方法で得たリストのStreamを合流 searchStream = querySearchStream .merge favSearchStream .merge arcanaNameSearchStream # 検索結果からページ送りオブジェクト生成 searchResult = searchStream .flatMap (as) -> createPager(as, pagerSize) # このプロパティを各Viewでsubscribeして描画 @targetArcanas = searchResult # 検索結果 .merge prevPageStream # 前のページをクリック .merge nextPageStream # 次のページをクリック .merge jumpPageStream # ページ番号をクリック .map -> pager.get() # pagerから描画する部分だけ渡す
まあ具体的なコードは正直分からなくてOKなのですが、
重要なのは「Streamの切り貼りだけで処理が書ける」というところです
ところどころ非同期処理があったとしても、
全て「値を渡して値を得る」という形をしていることが大事なのです(`･ω･´)
これを構築したおかげで、インクリメンタルサーチも簡単に追加できました
arcanaNameStream = $arcanaName # 名前入力フォーム .asEventStream('keyup change') # イベント .delay(500) # モバイルで日本語変換する場合に対応するため、微妙に読み込みを遅らせる .map -> $arcanaName.val() # フォームの値を取得 .debounce(300) # 0.3s置きにに値を監視 .skipDuplicates() # 「前と同じ値」ならイベントを却下する nameSearchStream = arcanaNameStream .filter (name) -> name.length > 1 # 2文字以上入力してなければ却下 .flatMap (name) -> searchName(name) # 検索APIを叩く
https://github.com/parrot-studio/cc-pt-viewer/commit/3be1bbf0aaa78fb9072ae1934bbe66f5a4628f64
普通に考えるとそれぞれとても面倒なはずですが、
このような関数の切り貼りであっさり実装できます∠( ﾟдﾟ)／
しかしこのFRP、実際の業務に持ち込めるかというと、
正直微妙なんですよね・・・
今は検証レベルで私が好き勝手やっているので自由に書けますが、
他の人がこのコードをいじることになったら、果たしていじれるのかと
もちろん、FRPの概念が一般化すれば可能です
しかし、RubyのEnumeratorも必ずしも浸透してない状況*6で、
FRPへのジャンプはあまりにも大きすぎるのではないかと(´-ω-)
回転の早いJavaScript界隈ではありますが、
FRPそのものは「設計思想」であり「概念」なので、
そこは安心なのですが・・・
ES6かCoffeeScriptか、それが問題だ
さて、このようにFRPで記述するにあたり、
CoffeeScriptの書きやすさが非常に際立っております
むしろ、CoffeeScriptでなければテンションが上がらないというか（ ﾟдﾟ）o彡ﾟ
しかし、いろいろ調べてみると、CoffeeScriptよりもES6に流れが移りつつあります
現時点でES6がまともに動くブラウザはありませんが、
Babelのような「ES6のコードをES5に変換する仕組み」も整備され、
さらにサーバサイドで考えればブラウザの状況は完全に無視できます
もちろん、CoffeeScriptには多数の利点があり、
「後置ifが書ける」とか「括弧がいらないのでシンプル」とかありますが、
一方でES6は「純正のJSである」という利点があります
さすがにccptsをES6に書き換えるのは手間がかかるなんてものではないので、
仕事で書いたプロトタイプを一部ES6に書き換えたりしていますが、
やっぱりCoffeeScriptに慣れているとしっくりこないんですよね(´-ω-)
でも、CoffeeScriptも知らない人にとってみれば、
ES6もCoffeeScriptも習得コストに大差はなく、
むしろ純正のJSを覚えた方がいろいろ便利なのではないかと・・・
ということで悩んでいたのですが、
とりあえず「関数型っぽいコードが書ければ緩和できるのでは？」と、
こちらのライブラリを試してみることに
こちらはあくまでライブラリであり、
ES6だろうとCoffeeScriptだろうと使えますし、
「やりたいこと」が詰まっていてとても便利です(｀･ω･´) b
ccptsでもできるだけlodashを使うようにして、
いざES6に書き換えるとしても、コストを下げられるようにしました
実際に書き換える場合はこちらなどを参考に
Moving to ES6 from CoffeeScript · GitHub
ここからどっちに進むか？
あくまで当初の目的は「サーバサイドJSに関する採用アーキテクチャの検討」であって、
View側のJSは目的ではないので、ここから先は私自身の興味になりますが・・・
ここまでViewのコードを書き換えれば、やっぱり次に気になるのは話題のreactですよね
ただ、reactを適用しようとすると、Viewをほぼ一から書き直すはめになり、
過去2回ほど挑戦しようとしたものの、途中で挫折しています(´-ω-)
https://gist.github.com/parrot-studio/b937179bff3d61f69df5
ただ、reactとセットで出てきたfluxの概念*7については、
reactと無関係に適用できる・・・らしいです
せっかくStreamで構造を整理し直したので、そこにfluxの概念を投入しておけば、
残りのreact化もスムーズに進むのではないかと(`･ω･´)
そこで、話題になっているらしい、こちらを適用しようと考えました
react自体は「データが更新されたらviewを自動で書き変える仕組み」なのですが、
実際に書いてみるとデータ（state）の管理が面倒でして・・・
その点、reduxは「データを一箇所で管理する」という仕組みになってまして、
これなら後々react化もたやすいのではと考えたのです(`･ω･´)
しかし、ここで問題が
ライブラリ管理で使っているのはbower（実際はbower-rails）という仕組みなのですが、
reduxはbowerに対応していませんΣ(ﾟДﾟ)ｶﾞｰﾝ
Node.js界隈ではnpmでライブラリをインストールするのが一般化しており、
フロントエンド側もその仕組みに移行しつつあるのです
私がbowerで管理し始めたのが今年の頭なので、
まだ1年経たないうちに再検討させられるあたりが、
JS界隈の回転の速さを感じる部分なのですが、それは置いておいて・・・
Railsと新しい仕組みがまだ試行錯誤段階で、
Railsのsprocketsがよくできすぎているために、
皆が暗黙的に使いすぎていて、移行が文字通り「面倒」なのが問題です(´-ω-)
私もこのあたりは調べ始めたばかりで、有効な回答を持ってないのですが、
そもそもjQuery周りのライブラリは逆にbowerにしかなかったりして、
検討を始めるといろいろ難しいです
（DOMレベルでのjQueryは排除できても、ccptsは「jQuery UI」にがっつり依存しており、
その代替になる仕組みがreactにはまだなく、
そもそもreactのライブラリはモバイルに問題があるケースが多いという・・・）
react-railsの仕組みを使ってreactの初期状態をサーバサイドでレンダリングする*8とか、
やりたいことはあるのですが、どうにも私の知識やノウハウが追いつきません(´･ω･`)
とりあえず、仕事で「納得できるJSのコード」を追求しつつ、
見つけた概念をccptsで試す・・・というやり方が続きそうです
・・・以上、完全に私自身のメモ書きでしたΣ(・ω・ノ)ノ
*1: 最初からNode.jsを選んだわけではなく、その選択自体もだいぶ手間取ったのですが、それはまた機会があれば・・・
*2: 最小限の要件を満たしつつ、運用とかもふまえた一式
*3: わずかでもブロックする処理を入れてしまう時点で、Node.jsを使う意味がなくなります(´･ω･`)
*4: jQueryのAjax処理も今はPromiseを返しますね
*5: Rxが出始めた初期の頃にいろいろ見た記憶がかすかにあるのですが、当時は「何に使うのか？」がいまいちわからず(´-ω-)
*6: 書けないって人はだいぶ減っていると思いますが、「関数型的なデータの流れで捉える」というのはもう一つ上の概念です
*7: https://github.com/facebook/flux/tree/master/examples/flux-todomvc/
その文明はわりと現役です（「女子高生プログラマーの大バトル！〜コボール文明の逆襲〜」を解いた件）
いやまあ、別にこのBlogはPOHの結果を貼るためのものではなく、
前回から今回までの間にLTをやったりはしていたのですが、
仕事がなかなか忙しくてですね・・・(´-ω-)
さすがに新しい仕事に移って半年だと、
Blogで書けるような新しいネタも少なくて・・・
まあ、LTのネタを書き忘れていたのは単なる怠慢ですが
それはさておき、6回目です
前回が4月なので、約半年ぶり・・・って、そんなに経ってましたか(lllﾟДﾟ)
4回目くらいで難易度が下がりはじめ、
5回目でパフォーマンスを気にしなくてもいいレベルまで下がってましたが、
今回はさらに下がっていた気がしますΣ(ﾟДﾟ)ｶﾞｰﾝ
（仕事が忙しくて）着手がだいぶ遅くなり、
今ならもう皆さん解いているはずなので、
今回は答えを本文に書いてしまいます...φ(･ω･｀)
緑川つばめの問題
https://paiza.jp/poh/joshibato/tsubame
難易度の表示とか何もなく、実際は「霧島->緑川->六村」の順で解いたのですが、
Blogでは簡単な順に書きます
・・・とはいえ、この1問目はあまりに簡単すぎますΣ(・ω・ノ)ノ
「プロのプログラマ」がこの問題を一瞬で解けない場合、
「貴様、普段全くコードを書いてないどころか、まともに書いたことないな？щ(ﾟДﾟщ)」
と疑われるレベルでしょう
（逆に、あまりに単純すぎて、何か罠があるのでは・・・と疑ったくらいで）
ただですね・・・「転職支援サイト」で、
このレベルの問題を「最低ライン」として提示しているということ自体、
「プログラムを書けない人」の転職が増えているのかな・・・とも思います(´-ω-)
正直、残すほどのコードではないですが、一応こんな感じで
https://gist.github.com/parrot-studio/8fae30021b17177d4ba4#file-tsubame-rb
六村リオの問題
https://paiza.jp/poh/joshibato/rio
さすがに多少難易度が上がりましたが、ご丁寧にも詳細な計算式が提示されているため、
ただその仕様を実装するだけのお仕事です(´･ω･`)
ただ、「小数」を扱う関係上、数値の取り扱いを間違えると誤差が出ます
私も手抜きしたら通りませんでしたし
https://gist.github.com/parrot-studio/8fae30021b17177d4ba4#file-rio-rb
厳密にいえば、きちっと精度を確認し、
BigDecimalやRationalを検討すべきなのかもしれませんが、
今回はFloatで問題なかったのでこれで
さすがにFloatの方が速いですしね・・・ *1
ただ、誤差で思いもよらぬバグを生み出すこともありますが(´-ω-) *2
霧島京子の問題
https://paiza.jp/poh/joshibato/kirishima
今回のメイン・・・ですが、これも前回よりは簡単な気がします
わりと力技で通ってしまい、アルゴリズム的な小技が不要なので
この問題はとにかく「問題を理解すること」が重要で、
その上で「文章をコードに落とし込めるか？」がポイントであり、
あとはせいぜい効率化を考えるくらいでしょう
ルールに従い、順番に盤面をparseしていって、
ゴールにたどり着けば「Yes」、止まるか外に出たら「No」、
ここまではすぐ思いつくレベルです（効率はともかくとして）
問題は「循環して止まらない場合」です
これを排除できないと、単にparseしていくだけでは終わらなくなります(lllﾟДﾟ)
要は、「一度通ったところを再度踏むと循環する」ということなので、
通った場所を記憶しておいて、また踏んだら「No」と考えればOKかと
そして効率化ですが、当初は盤面をあらかじめ逆にparseしておき、
「数値が来た時点でO(1)の計算量」的なものを目論んでおりました
ただ、実際は盤面のサイズが大きくなるほど、
無駄な計算が多くなる可能性が高く、コードも複雑化しそうだったので、
単純に「一度計算した結果を覚えておく」程度にしました(´-ω-)
https://gist.github.com/parrot-studio/8fae30021b17177d4ba4#file-kirishima-rb
たぶん、名前のついたもっとうまいアルゴリズムとかあるのだと思いますが、
今回はこれでも0.1秒を切ってますし、気にしない方向で( ﾟДﾟ)y─~~
まとめ
ということでざっと見てきましたが、
2〜3回目くらいの「TestCase5が通らないのぉぉぉぉっ！(つД｀)・ﾟ・。」
みたいな難易度からはすっかり遠ざかった印象です
前回のおまけ問題がそれに近いのかもしれませんが、
あれはあれでガチすぎて手を出す前にあきらめる問題だったので、
「なんとなく手を出したら深淵が待っていた」くらいのが個人的な好みです
まあ、そういう問題を出されると、
一週間くらいはその問題のことで頭がいっぱいになるので、
仕事が進まなくなるのですが・・・Σ(・ω・ノ)ノ
*2: つい先日、Floatの誤差でバグが出まして、原因がわからずに数時間つぶれたこともΣ(ﾟДﾟ)ｶﾞｰﾝ ロジカルなレベルでは間違いがなく、特定の値が来るとおかしくなるってのは、実にデバッグが難しく・・・
幼なじみと許嫁が修羅場らしいが、それなら両方手に入れればいいじゃない
ということで、5回目です(`･ω･´)
いつもだと・・・
問題を読む -> 仕様通りに書く -> サンプル通りの出力になるか確認する ->
いったんサイトで実行してみる -> 途中で落ちる -> リファクタリングしてみる ->
小手先の修正では通らない -> 奇抜な方法を試す -> サンプルの出力すら出なくなる ->
煮詰まって悩む -> いったん寝る -> ヒントになりそうなアルゴリズムを探す ->
いまいちいいのがない -> でも調べるうちになんとなく見える ->
書き直してみる -> あれ、もうちょっとで通るやん？ -> 直す -> ∠( ﾟдﾟ)／
・・・というプロセスを経由してクリアしております(´･ω･`)
なので、過去の記事においては、
「どう試行錯誤したか？」をまとめているわけです
しかし、今回はですね・・・
問題を読む -> 仕様通りに書く-> 先回りして罠を回避する ->
サンプル通りの出力になるか確認する -> いったんサイトで実行してみる -> 通ったΣ(ﾟДﾟ)ｶﾞｰﾝ
・・・ということで、一発で通ってしまいまして(； д ) ﾟ ﾟ
なので、そもそも今回の問題が（いつもに比べて）簡単という可能性もあります
実際、もっと高難易度な問題は別に用意されてますし
とはいえ、過去の問題の傾向から、
ここを押さえればいけるというポイントがわかっていたのも事実で、
今回は「何を考えたか？」を中心にいろいろ書いてみます...φ(･ω･｀)
なお、私の回答は「おまけ」にて
1問目
見た瞬間解けないと・・・とまでは言いませんが、最近のWeb企業を受ける場合、
このような問題を面接で出される可能性はある*1ため、
できれば5分、最低でも15分くらいで解き方を思いつかないと(ﾟдﾟ)ﾏｽﾞｰです
なお、問題文では「ODD」といってますが、
たいていの言語において、配列は0-originなので、
実際のコードでは「EVEN」というのが罠と言えば罠でしょうか
2問目
「周期性のあるものは割った余りを見ろ」ってミルカさん*2が言ってたΣ(・ω・ノ)ノ
この問題は実際の業務でもありそうな話であり、
効率の良いコードとまではいかなくても、全く書けないというのは問題です
3問目：レナルート
先に解いたのはアイドルの許嫁でしたが、
ぶっちゃけ話をきちっと読んでなかったので、
先に目に入った方を解いたという・・・Σ(ﾟДﾟ)ｶﾞｰﾝ
Excelのような表にあらかじめ値が入っており、
あとから複数指定される領域を結合した領域に含まれる値の合計、
といった問題でございます
ポイントはもちろん「領域には重複があること」であり、
素直に解くならば、まず「領域がどんな形になるか？」を組み立て、
元の表をparseして領域に含まれるかを判定して足す・・・という感じでしょうか
でも、これだと「領域を組み立てる」ので一度parseし、
「合計を算出する」段階でもう一度parseするわけで、
過去の問題だとこのやり方で100点は無理です(´･ω･`)
「読み込み（gets）しながら問題を解く」というのが理想であり、
「最初の表を読み込む」のは仕方ないにしても、
「領域の読み込みと計算」は同時に進めたいところです
要は、「再度読み込まれても値が加算されない」なら良いわけで、
しかも求められているのは「合計」だけです
なので、「一度読んだ領域を0で上書き」すれば、何度読んでもOKです(`･ω･´)
ついでに、素直にデータ構造を組むとHashとか使いたくなりますが、
これも過去の経験から「Arrayのindexアクセスが速い」とわかっていたので、
データをただの配列で保持し、x/y座標からindexを算出する方法を取っています
あと、きっちり問題を読むと、
表領域に対し指定領域のindexが異様に大きいような気がしたので、
一応足切りを入れていますが、どの程度効果があったかは不明です(´-ω-)
＜結果＞
3問目：ミナミルート
レナルートは業務寄りの問題なので、実行効率はともかく、
全く書けないってことはないと思うのですが、
ミナミルートは「まんま書く」をやろうとして詰む可能性はあります(lllﾟДﾟ)
いわゆる「落ちものパズル」の話で、
火のついた爆弾が消えると、上にあった爆弾が「落下する」という条件で、
最終的にどんな盤面になるかを出力せよ、という問題です
状態が「空＝0」「普通の爆弾＝1」「火のついた爆弾＝2」と3つあり、
しかも「落下する」ということは「下に何があるか？」を考えなければならず、
普通に解こうとすると結構悩ましい問題です(´-ω-)
しかし、冷静に「出力結果」を見ていただきたいのです
出力するのは「0か1」であり、「火のついた爆弾＝2」はどうせ消えるので、
考えなくていいわけです
しかも、「落下する」と考えるから混乱するわけで、
「落下したあとどうなっているか？」を考えると、
「各列ごとに爆弾がいくつ残るか？」がわかればいいわけです(`･ω･´)
つまり、最初の盤面をparseしながら、「各列ごとに1の数をカウント」し、
出力する時にその値に応じた行を出力していけばいいわけです
結果的に、ミナミルートの方が圧倒的に簡単なコードになります
強いていえば、出力時は「盤面の上から」であり、
「下から積み上げ」ではないので、1か0かの判定が多少混乱しますが、
サンプル出力になるように適当にいじればどうにか・・・Σ(・ω・ノ)ノ
（なお、この問題ではカウンターにHashを使っていて、
「そこはArrayじゃないのか？щ(ﾟДﾟщ)」と突っ込みを受けそうですが、
ええやん、それでも100点だし、直すのめんどいし
そもそも、普段の業務なら迷わずHash.new(0)にしているのもあって・・・）
＜結果＞
まとめ
過去の問題で学んだチューニングポイントがこちら(´･ω･)っ
- parseやループ回数をとにかく減らす
- 細かなチューニングよりも圧倒的に重要
- 盤面を保持するデータ構造はできるだけ簡潔に
- 複雑な構造を使おうとしている時点で、解き方がおかしいと考える
- 簡単に足切りできそうなら切る
- 結果さえあっていればいいので、過程はどうでもいい
- 結果から逆算して、求められている計算手法を予測する
この辺がわかっていたので、今回は一発でしたが、
やはり本命はSP問題の方でしょう
・・・時間がないのでやりませんがΣ(・ω・ノ)ノ
とあるプログラマの転職記録
別なBlogでそれっぽいことを書きまくっているので今さらですが、
3月から新しい会社で仕事をしております(`･ω･´)
ギリギリまで引き継ぎをしていたため、相当に有休が余りまくりでしたが、
技術者は私一人でしたので、「あとはよろしく」ってわけにも・・・
（在籍中の後半は別なグループ会社の仕事を主にしてました）
で、この手の記事にありがちな「前の会社の実績」とか、
「新しい会社でやること」とか、
私のような無名の技術者の場合はどうでもいいですよね？
むしろ、「私が（読者ならば）知りたいこと」は、
具体的な転職の経緯とかノウハウだと思うので、
その辺をメモしておこうかと...φ(･ω･｀)
転職のきっかけ
今までの転職はほぼ仕事への不満100％でしたが、
以前の職場は楽で給料も良かったので、
その意味での不満はありませんでした
ただ、「世間一般の会社」がやっていることに対し、
どんどん遅れていっていることが不安になりまして(´-ω-)
それでも十分な利益が上がっているので、
会社としては問題ないのかもしれませんが、
私個人のレベルではちょっとな・・・と
他に稼げる手段もないので、エンジニアとして一生食っていくという覚悟でやってますが、
基本的な部分でめんどくさがりなので、
過剰なコストを払って「一流」*1になる気はありませんc(・ω・`c )っ *2
ただ、「いざ仕事を探す時に、選択肢がない状況」にはしたくないので、
そのギリギリのラインは維持できるようにと考えていて、
そろそろそれを下回るな・・・というあせりがあったのです
いくらプライベートでいろいろ作っていたとしても、
やはり実務実績がないと説得力に欠けるわけで、
「今の世間一般的な経験」を積む必要があるだろうと
まあ、それでも元の会社が楽なのは事実で、
年齢で面接に通らない可能性も十分にあったので、
元の会社に残る選択肢を残しつつの転職活動でした
ただし、この「技術者としての理由」は半分で、
「プライベートな理由」もかなり大きいのですが、
それはきっかけになった本だけ紹介するに留めます(´･ω･)っ
- 作者: ロースおじさん
- 出版社/メーカー: 一迅社
- 発売日: 2014/08/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (1件) を見る
- 作者: 二村ヒトシ,青木光恵
- 出版社/メーカー: イースト・プレス
- 発売日: 2012/12/02
- メディア: 文庫
- 購入: 7人 クリック: 125回
- この商品を含むブログ (31件) を見る
エージェントの紹介と書類選考
転職を決める1年前、最近の流れを見るため、
転職エージェントに会って情報を流してもらっていたのですが、
本気で転職すると伝えて仕切り直したのが10月末です
過去の転職でも、特に理由がない限りは転職エージェントを利用しています
企業のHPで募集をしてないって場合でも、
エージェント経由だときっちり募集していたりしますし、
なにより各種調整を代行してくれるってのがとても楽です
書類の提出から面接日程の調整はもちろん、
入社前の条件調整とか、お断りの連絡とか、全部代行してくれます
業務と並行で転職活動をするならとても便利だと思います(｀･ω･´) b
もちろん、入りたい会社が最初から決まっているとか、
誰かに誘われたから転職するって場合は不要です
あくまで「漠然とどこかに行きたい」という場合に利用するものです*3
で、早速まとまった数の企業を紹介してもらいまして、
各企業について個人的にじっくり調べまくり、
書類を出し始めたのが11月の頭でした
紹介されたのは流行のゲーム系と普通の業務系で半々くらいで、
この時点ではどちらとも決めていなかったので、
単純に企業情報を調べて「良さそうなところ」に出してみました*4
あと、ずっと前から目をつけていた会社の求人も、
エージェント会社のDBにあったので、
こちらも個人的な興味で出してみました
まあ、最終的に入ったのがそこなのですが・・・Σ(・ω・ノ)ノ
面接のもろもろ
書類を出した時点では、「そこそこの数通るやろ」と油断していたのですが、
予想以上の数蹴られまくったので、相当にあせりましたΣ(ﾟДﾟ；≡；ﾟдﾟ)
スキル的には十分だとしても、年齢や希望年収*5で折り合わないケースが思ったより多く、
逆に面接にこぎ着けたのは「年齢よりもスキル重視」の会社だと思ってます
実際、どの面接でも私のBlogやGitHubのリポジトリを「その場で」チェックしてました
「普段Rubyを書いているようですが、C#は触ったことありますか？」という質問に、
「書いたことがあります」と答えるのと、
「書いたことがあり、GitHubにコードがあります」では、全く印象が違いますからね
もちろん、どんな雑なものでもUPしておけばいいってものではありませんが、
普段からいろいろ書いておくのは有利に働くはずです(`･ω･´)
それに、最近の会社でgitを使わないってことはほぼないはずで、
GitHubにコードがあるということは、
最低限の使い方を知っているという証明にもなります
あとはやはり、過去にやったLTの資料とかも役に立ちました*6
あれの話をしつつ、ほとんど雑談のように面接が進んだ会社もあります
一方で、最初に面接を受けた会社は、私自身の心構えも十分でなく、
聞かれて当然の質問にあせって真っ白になるという事態に陥りまして(lllﾟДﾟ)
他にも鋭い質問が飛びまくり、これはやばいと思ったものの、
後半うまく取り戻したおかげで、その面接は突破したのですが・・・
面接が終わった後、今の人が「社長」だと教えられましたΣ(ﾟДﾟ)ｶﾞｰﾝ
他の面接に比べると、これが最初にして最大の難関でしたが、
この会社は先ほども書いた「前から興味のあった会社」であり、
面接の翌日には内定をいただき、結果的にその会社に入っております
選考プロセスの違いについて
会社によって選考プロセスが違うため、
先ほどのように1回の面接で内定が出る会社もあれば、
Webテスト等々を経由してやっと面接、という会社も少なくありません
規模の大きい会社ほどプロセスが長いため、
結果的にある会社の一次面接が、
最初に内定が出た会社の回答期限前日って状況だったりもΣ(ﾟДﾟ)ｶﾞｰﾝ
書類を出す順番を考えるべきだった気がしますが、
かといって出すのが遅れて募集が終わってしまってもあれですし、
こればっかりは巡り合わせとしか・・・
規模の違う会社を同時に志望する場合、
書類を出す順番をある程度調整した方がいいかもしれません
会社を決めた基準
最初に面接を受けた会社から内定が出て、
その回答期限が11月末だったのですが、その段階で私はこのような状況でした
- 内定：2社
- 1次面接突破：2社
- 1次面接待ち：1社
このうち、4社がゲーム関連で、1社がWebサービスの会社です
他にもWebサービスの会社はいろいろ出したのですが、
ここ以外は全部書類で蹴られましたΣ(ﾟДﾟ)ｶﾞｰﾝ
で、個人的に悩んでいたのが、内定を取った2社（A/B社）と、
まだ面接が先の1社（以下C社）の3社でした
C社のゲームはめちゃくちゃはまっていたのもあり、
入れるなら本気で入りたいと思ってはいたものの、
実際にどのような業務でスキルを生かせるのかが不明確でした
一方、A社は「ゲームプログラマ」としての採用であり、
B社は技術面で有名で、やはりゲームのプロジェクトで採用の予定でした
しかも、どちらの会社もメインの言語がRubyでした
相当に悩んだ結果、A社とB社については、
ゲームの内容で決めることにしまして、実際にプレイしてみた結果、
私好みのゲームを作っていたA社を選択しました
仕事とプライベートは切り離していますが、
どうせ作るなら自分でもやりたいと思うゲームがいいですからね
B社ゲームはどちらかというと「普通の人向け」だったので
問題はまだ面接してないC社ですが、
面接前に「ゲームプログラマの採用か否か？」という基準を決めました
C社の面接ではゲームへの愛を相当に語りまくりまして、
またそういう人が好きな会社であることもわかっていたわけですが、
だからこそ、ゲームそのものの要求技術レベルが高いのもまた事実です
面接の中で「採用するとしたらどのようなポジションか？」と聞いたところ、
やはりバックエンド周りとのことで、仕方なく今回はあきらめました(´･ω･`)
もし、A社の回答期限までにC社の内定が出ていれば、
相当に悩んだと思うし、C社を選んだ可能性も十分にあったのですが、
こればっかりはタイミングですかね・・・
実際に入社してみて
ということで、12月頭には入社が決まっていたのですが、
元の会社の引き継ぎに時間がかかることがわかっていたため、
2月いっぱいまで待ってもらいまして、3月から入社しております(`･ω･´)
1週間過ごしてみての感想は、良くも悪くも「想定した通り」であり、
やはり事前に細かく調べておいたのは正解だったな・・・と
その他、もっと細かいもろもろは、
今月末開催の「NetGamers.dev.talk」あたりで聞いてください(´･ω･)っ
*1: GoogleとかAmazonとか、外資系に入れちゃうレベルの実力
*2: 別に「有名な会社」に入れば幸せとは思ってないので・・・
*3: 余談ですが、一応知りあい経由で打診されたことはあるのですが、一度目は全く転職を考えておらず、二度目は新しい会社の入社直前でしたΣ(・ω・ノ)ノ これもまたタイミングですかね・・・
*4: あとは、スキルセットが合わないのを承知で、「普段お世話になっている会社」にも出しましたが、予想通り書類で蹴られました(´･ω･`)
*5: といっても、前の会社の1割以上減で提示したのですが、それだけ前の会社がゆるいってことかもしれません
*6: やはり関数型のあれは評価されました http://www.slideshare.net/parrotstudio/gunmaweb-5-20110514
