こんにちは、@kazこと成瀬順です。
#ツイキャスインターンチャレンジ のお話をします。

ツイキャスインターンチャレンジ

このたびツイキャスを運営するモイ株式会社では、エンジニアを志す学生の方を対象としたサマーインターンシップを実施いたします。
今回、ちょっとした「応募前チャレンジ」を用意させていただきました。

らしいですよ。よくあるコードテストみたいなもんですね。
「労働は雑魚」なのでインターンに行く気は無いんですが、とーふとふに教えてもらって面白そうな問題だと思ったので取り組んでみました。

問題

よくあるHit&Blowです。
問題レベルが３から１０まで存在して、レベル$n$では0〜9の数字のうちから$n$種類が選ばれて並んでいるので、ヒントを元に当ててくださいね、というやつ。
レベルが高い方が高得点がもらえます。

考える

問題レベルについて

レベル10のときだけHit数とBlow数の和が必ず10になるという性質があります。
つまり、レベル10のみシンプルなアルゴリズムで解くことが可能で「むしろ一番簡単じゃないか？？？」説がボクの中で有力でした。

少なくともレベル9よりは明らかに簡単です。
だってレベル10であり得る解の数$10!$に対して、レベル9であり得る解の数が${}_{10}{C}_9\times 9!=10!$で同じですからね。

ということでレベル10のみ解く前提で考えます。

数字の入れ替え

すべての数字は1回しか出現しないので、レベル10では全ての操作はいくつかの数字を入れ替えたと考えることができます。
特に2箇所のみを入れ替えたとき、その結果（Hit数の増減）によって得られる情報がシンプルに整理できます。

まず、入れ替え前の2箇所についてどちらも正しい数字であった、どちらか一方のみ正しい数字であった、どちらも正しい数字ではなかったの3通りの状況が考えられます。

どちらも正しい数字であった場合

入れ替え後は必ずどちらも正しい数字ではなくなるはずです。
1つの数字に対して、正しい位置は必ず1箇所しか存在しないので、当たり前ですね。

つまり、このとき入れ替え後にヒット数は-2となるはずですね。

どちらか一方のみ正しい数字であった場合

入れ替え後は必ずどちらも正しい数字ではなくなるはずです。
1つの数字に対して、正しい位置は必ず1箇所しか存在しないので、もともと正しい数字が入っていた場所には違う数字が入るし、もともと正しい場所にあった数字は別の場所にいれると必ず間違いになりますね。

したがって、このとき入れ替え後にヒット数は-1となるはずです。

どちらも正しい数字ではなかった場合

入れ替え後の状況として、どちらも正しい数字になる、どちらか一方のみ正しい数字になる、どちらも正しい数字でないままの3通りが考えられますね。
ということは、このとき入れ替え後のヒット数はそれぞれ+2、+1、±0となる事がわかります。

Hit数の増減が意味すること

2箇所のみを入れ替えたとき、そのHit数の増減に対して、考えうる状況はただ1通りであることに気が付きましたか？
これは非常に好ましい性質で、Hit数の増減から解の満たすべき性質を非常に簡潔に記述することができます。

式にする

プログラムに落とし込むにあたって、上記の解が満たすべき性質を式っぽく書いてみます。

まず簡単化のために、入れ替え前のパターンは必ず0123456789である、ということにしましょう。
すると、位置$(i,j)$を入れ替えたとすると位置$i$の入れ替え前の数字は$i$で入れ替え後の数字は$j$であり、逆に位置$j$の入れ替え前の数字は$j$で入れ替え後の数字は$i$となります。

解が$a_i(n\in [0,9])$であるとしたとき、

解いてみる

そのまま実装

パターン0123456789と、このうち2箇所を入れ替えて得られるパターン(${}_{10}{C}_2=45$通り)の全てを投げて、その結果から解が満たすべき条件式を作り、
解としてあり得る$10!$通りのパターンのうち条件式を満たさないもの除外していけば、解候補が求まりそうです。

これだけの情報で解を現実的な個数に絞り込めるかまでは考察していませんが、とりあえずNodeJSで適当に書いてみました。

https://github.com/kaz/TwitcastingInternshipChallenge2018Summer/blob/master/v1/v1.js

一つ一つの条件式を関数として作っておいて、全部の式を満たすものを全て解として投げています。
$10!$通りのパターンを作るのは予めやっておきます。そうじゃないと遅すぎる。

見切り発車で実装しましたが、大体2個から4個まで解を絞り込めていて、イイカンジでした。
ゲーム開始からおよそ300msくらいで正答を投げることができて、大体1175k点くらいもらえました。

SMTソルバに頼る

最後の解の絞り込みがクソ遅いです。当たり前ですが。

ん？条件式を満たす解を探す……？
おい！ それってYo！ Satisfiability modulo theories じゃんか！ アッアッアッｗｗｗｗ

餅は餅屋ですね。SMTソルバに任せるとしましょう。
とりあえず、有名どころのZ3の使ってみます。

https://github.com/kaz/TwitcastingInternshipChallenge2018Summer/blob/master/v3/v3.js

これでかなり早くなりました。
ゲーム開始からおよそ90msくらいで正答を投げることができて、大体1177k点くらいもらえました。

それと、小手先ではありますが、TLSは鍵交換やらなんやらで接続が始まってから実際にデータをやり取りするまでが重いので、
はじめにいくつかのセッションを確立しておいて、必要になったら実際のデータを送る、という改善も入れています。

いろいろ詰める

ココからは地味な改善を積み重ねる作業になりました……

• SMTソルバをyicesに変更
  • Z3で30msかかっていた解の探索が1msくらいになった
• 投げるパターン数を16種類くらいにした
  • 運が良ければコレくらいの条件でも解を十分に絞り込めるようだったので
• NodeJSからGolangに変更
  • メモリアロケーションを減らすとか
  • 弱い暗号スイート(TLS_RSA_WITH_RC4_128_SHA)を使うとか
  • 他にもいろいろ細かい変更を入れた
    • pprofを使うとどこで時間を食っているかがわかるので便利です
    • 最終的には通信以外の処理でオーバーヘッドがほぼなくなった
• 物理的に近そうな場所から解を投げる
  • 詳細は後述……

https://github.com/kaz/TwitcastingInternshipChallenge2018Summer/blob/master/v6/v6.go

yicesへの変更が効いて、結構早くなりました。
ここまでやってゲーム開始からおよそ50msくらいで正答を投げることができて、大体1179k点くらいもらえました。

失敗

物理的に近そうな場所から解を投げてたつもりだったんですが、ココで盛大にミスってました。
mtr -zしたらAS4694(Yahoo! Japan Corp.)だったのでIDCFクラウドか？と早合点してココから投げてたんですが……(ping 5msくらい)

株式会社モイが使ってるのはIDCFのデータセンターの方だったんですね。ソース
IDCFクラウドの東日本リージョンは白河データセンター（福島県）、IDCFのデータセンターは未公表だがおそらく東京近郊でしょう。

普通に大学のネットワークから投げたほうが圧倒的に早くて(ping 2ms)大草原でした。
終わったあとに気がつきましたが、わざわざ遠いところから解を投げてました。クソアホですね。

大学ネットから投げてたらもう少しスコアを伸ばせたかな〜と思います。

おしまい

たのしかったです。おわり。