2018年7月13日 | ブログ記事

2018年の夏は #ツイキャスインターンチャレンジ

kaz

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

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

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

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

問題

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

考える

問題レベルについて

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

少なくともレベル9よりは明らかに簡単です。
だってレベル10であり得る解の数10!10!に対して、レベル9であり得る解の数が10C9×9!=10!{}_{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数の増減から解の満たすべき性質を非常に簡潔に記述することができます。

ヒット数の増減 入れ替え前の状況 入れ替え後の状況 解が満たすべき性質
+2 どちらも正しい数字ではない どちらも正しい数字 入れ替えた2箇所の数字が入れ替え後に一致する
+1 どちらも正しい数字ではない どちらか一方のみ正しい数字 入れ替えた2箇所の数字がそれぞれ入れ替え前に一致せず、かつ入れ替え後のどちらか一方のみに一致する
±0 どちらも正しい数字ではない どちらも正しい数字ではない 入れ替えた2箇所の数字がそれぞれ入れ替え前後のどちらにも一致しない
-1 どちらか一方のみ正しい数字 どちらも正しい数字ではない 入れ替えた2箇所の数字がそれぞれ入れ替え後に一致せず、かつ入れ替え前のどちらか一方のみに一致する
-2 どちらも正しい数字 どちらも正しい数字ではない 入れ替えた2箇所の数字が入れ替え前に一致する

式にする

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

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

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

ヒット数の増減 解が満たすべき条件式
+2 ai=j  and  aj=ia_i = j \mathrm{\;and\;} a_j = i
+1 ai̸=i  and  aj̸=j  and  (ai=j  xor  aj=i)a_i \neq i \mathrm{\;and\;} a_j \neq j \mathrm{\;and\;} (a_i = j \mathrm{\;xor\;} a_j = i)
±0 ai̸=i  and  aj̸=j  and  ai̸=j  and  aj̸=ia_i \neq i \mathrm{\;and\;} a_j \neq j \mathrm{\;and\;} a_i \neq j \mathrm{\;and\;} a_j \neq i
-1 ai̸=j  and  aj̸=i  and  (ai=i  xor  aj=j)a_i \neq j \mathrm{\;and\;} a_j \neq i \mathrm{\;and\;} (a_i = i \mathrm{\;xor\;} a_j = j)
-2 ai=i  and  aj=ja_i = i \mathrm{\;and\;} a_j = j

解いてみる

そのまま実装

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

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

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

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

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

SMTソルバに頼る

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

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

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

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

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

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

いろいろ詰める

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

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)大草原でした。
終わったあとに気がつきましたが、わざわざ遠いところから解を投げてました。クソアホですね。

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

おしまい

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

この記事を書いた人
kaz

シスアド班の人です。サーバー/部内システム/インフラを管理しています。 好きな言語はPerl/JavaScript/Go、エディタはSublimeText3です。

この記事をシェア

このエントリーをはてなブックマークに追加

活動の紹介

カテゴリ

タグ