ツイキャスエンジニアインターンシップ2018応募前チャレンジでランキング1位を取った

はじめに

モイ！ツイキャスエンジニアインターンシップ2018 - TwitCasting の応募前チャレンジというおもちゃがあったので遊んでみました.

Hit&Blowというゲームで点数を競えるチャレンジです. これは,'0123456789'のように10桁の重複しないランダムな数字が与えられ,それを予想するゲームです.

例えば'0123456789' が正解だったとして 「答えは'1023456789' ですか？」とリクエストを投げるとツイキャスサーバーから 「8箇所あたっています(hit=8)」などと返ってきますのでそれを元にして正解を探索することができます.

見事「答えは'0123456789' ですか？」と正答できれば,ツイキャスサーバーから「正解です！インターン応募フォームはこちら！」と返ってきます.

募集要項のどこにも「これを解くプログラムを公開してはいけない」とは書いていなかったので,募集期間(7/11:23:59:59)を越えたので公開します.

解法

途中過程で n4ru5e氏と1位を争ってなかなかそれはそれで楽しかったので,途中の過程も書きたいのですが,めんどうなので最終解法だけ記述します.

このチャレンジでは並列にリクエストを送ることが可能です. そしてこのチャレンジの点数は正解までに掛かったラウンド数(試行回数)ではなく,単純にチャレンジ開始から掛かった時間のみで点数が決まります.

以上の前提と,ネックはCPU的な計算時間よりもネットワーク方面に落ち着くことから,なるべく並列にリクエストを送れるような戦略を取るのがよいことがわかります. また,問題の難易度を3~10で選べるのですが,10以外は点数が出ないので10にします.

戦略としてはこうです.

1. ゲーム開始のフラグを送る.
2. 並列にn個のリクエストを送信する.
3. 返ってきたn個のhit数の列のパターンからあり得る答えリストを作成する.
4. その答えリストを送信する.

こうして, 1. 2. 4. の三回の通信と,3.の答えリスト作成を如何にして最小にするかという問題になります.

並列に送信するn個のリクエストについて

正解としてありえるのは 0123456789 の順列なので 約360万通りしかありません. ですので,ランダムに作成したn個のリクエスト ([0123456789,6574839201,...,7564312098] など) に対して返ってくる Hit数の列([0,0,5,...,0,1]など)を予めメモして置くことが可能です.これなら先に計算しておくことでチャレンジ中でも一瞬で答えリストが求まりますね.

nの値は小さすぎるとパターンが少なく答えリストが大きくなってしまい本末転倒となります. 逆にnが大きすぎると答えはほぼ1択にできますがそれを求めるまでに通信する量が多くなり時間がかかってしまいます. 試行の結果 n=10 くらいがちょうどよかったので n=10にしました.

ランダムに10個のリクエストを作成すると約360万通りの正解候補に対してhit数の列は 70万程度のパターンになります. ただ,毎回ランダムな10個のリクエストを作成するのもアレなので,もうちょっとよいリクエスト(hit数の列の取りうるパターン数が多いもの)を考えたいものです.

そこでNimで遺伝的アルゴリズムを使ってよいリクエストを探索するプログラムを書いて一時間くらい回してみました.

{.emit: """#pragma GCC target ("sse4")""".}
proc popcount(n:int64):int{.importC: "__builtin_popcountll", noDecl, .}
proc memset(m:ptr ,ch:int,n:int):void{.importc:"memset",header:"string.h",noDecl.}
import sequtils,strutils,strscans,algorithm,math,future,macros
import sets,tables,random,intsets,strformat

const shift = 4
const n = 10

proc getAscending(n:int):seq[int] =
  result = @[]
  for i in 0..<n:result &= i
proc getRandom(n:int): seq[int]=
  result = getAscending(n)
  result.shuffle()

proc toHash(query:seq[int]): int =
  result = 0
  var s = 0
  for q in query:
    result += q shl s
    s += shift

proc fromHash(hash:int): seq[int] =
  result = @[]
  var h = hash
  for i in 0..<n:
    result &= h and 0xf
    h = h shr shift

proc getPermutations(n:int): seq[int] =
  result = @[]
  var permutation = getAscending(n)
  result &= permutation.toHash()
  while permutation.nextPermutation():
    result &= permutation.toHash()

var maxValue = 0
let permutations = getPermutations(n)
const bits = [1,7,49,343,2401,16807,117649,823543,5764801,40353607]
proc getHitPattern(permutation:int,queries:seq[int]) : int =
  result = 0
  for i,query in queries:
    let h = query xor permutation
    let hit = 10 - popcount(
      ((h and 0x11111111_11111111) shr 0) or
      ((h and 0x22222222_22222222) shr 1) or
      ((h and 0x44444444_44444444) shr 2) or
      ((h and 0x88888888_88888888) shr 3))
    if hit >= 7 : return 0 # hit=8,10の探索は誤差なので速度のために諦める
    result += hit * bits[i]

const seven10 = 282475259+10
var table : array[seven10,bool]
proc check(queries:seq[int]) :int{.discardable.}=
  stdout.write queries.join("")[0]
  stdout.flushFile
  if queries.len() != queries.sorted(cmp).deduplicate().len() : return 0
  memset(addr table,0,seven10)
  var size = 0
  for permutation in permutations:
    let hitPattern = permutation.getHitPattern(queries)
    if table[hitPattern] : continue
    table[hitPattern] = true
    size += 1
  if size <= maxValue: return size
  maxValue = size
  let answers = queries.map(fromHash)
  echo(($answers).replace("], ","],\n "))
  echo size," patterns"
  echo size.float / permutations.len().float," mean"
  return size

# GA
const gaNum = 16
const queryNum = n
var queries = newSeqWith(gaNum,newSeqWith(queryNum,getRandom(n))).mapIt((v:0,q:it))
while true:
  let preQueries = queries
  var nowQueries = newSeq[tuple[v:int,q:seq[seq[int]]]]()
  var th = 0.5 * (maxValue / 70_0000) * (maxValue / 70_0000)
  for i in 0..gaNum:
    for j in (i+1)..<gaNum:
      var p = preQueries[i].q
      var q = preQueries[j].q
      if rand(1.0) < th / 5: q = newSeqWith(n+1,getRandom(n))
      var r = newSeq[seq[int]]()
      for k in 0..<queryNum:
        if rand(1.0) > 0.5: r &= p[k]
        else: r &= q[k]
      for k in 0..<queryNum:
        while true:
          if rand(1.0) < th / 2:
            swap(r[k][rand(n-1)],r[k][rand(n-1)])
          else: break
      nowQueries &= (r.map(toHash).check(),r)
  let nexts = (nowQueries & preQueries).sorted((x,y)=> y.v - x.v)[0..gaNum]
  queries = nexts.sorted((x,y)=> y.v - x.v)
  echo queries.mapIt(it.v)

結果,

{
  {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
  {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
  {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
  {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
  {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
  {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
  {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
  {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
  {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
  {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
}

が得られました.

821843通りのパターン数となって結構いい感じです. このリクエストだと答えリストを最大5個送信するとして3割くらいの確率で成功できます.

Go言語で並列に高速に通信する

アルゴリズムはほぼ最速なので,あとは通信部分です.

Nim -> Python -> NodeJs などと送信する言語を変えたりしましたが,結局はGoに落ち着きました. goroutine が強いのと通信に関する標準ライブラリが出揃っているのとコンパイルできるのが強いですねという感じです. 並列に送信するのは goroutineですぐにできますし,便利ですね.

実行するサーバーは39ff氏の前回のFizzbuzzの考察 (kblog: ツイキャス新卒採用2019で遊んだ) でも速いと書かれている通り,ConoHaでやるといい感じです. AWSとかIDCFクラウドとか東京の知人に託すとか色々しましたが,結局ConoHaが一番でした.

ここまでの戦略で,多分1177k後半くらいになると思います.

ゲーム開始から終了までに 70ms くらいかかる速度です.

HTTPSの高速化

このままの状態では 1179kを超えることができません. ここから先はHTTPS通信を高速化していきます. この問題ではKeep-Aliveは無効・HTTP2通信はできないなどの制約がありますがチューニングは可能です.

CipherSuitesを変える

HTTPSのCipherSuitesをクソ雑魚なものに変えて高速化します. Go言語だと tls.Config をいじることでそれが実現可能です.

config := &tls.Config{ 
  CipherSuites: []uint16 { tls.TLS_RSA_WITH_RC4_128_SHA, }, 
}

この手法はnonylene先生がふと言いだした手法で僕には思いつけなかったですね…

これで 1178k後半くらいになります.

ゲーム開始から終了までに 60ms くらいかかる速度です.

予めTLSのコネクションを16個貼る

最後のチューニングです.

Go言語の tls.Dial を使って通信を全て直書きします.

conn := tls.Dial("tcp", "apiv2.twitcasting.tv:443", config )

これを予め使用する16個分ゲームID取得に先駆けて取得しておき, 以降

data := `{"answer":"` + answer + `"}`
conn.Write([]byte(
    "POST /internships/2018/games/"+id+" HTTP/1.1\n" +
    "Host: apiv2.twitcasting.tv:443\n" +
    "Authorization: Bearer " + token + "\n"+
    "Content-Length: "+ strconv.Itoa(len(data))  +  "\n" +
    "\n" + data + "\n"))

のように予め取得した conn を用いて通信直書きでオーバーヘッド無しに回答を送信します.

これで1179.5k が出ます.ゲーム開始から終了まで40msくらいの速度です. 以上のチューニングによって 1位になることができました.やったぜ.

1位奪還！！ スコア 1,179,538 を獲得！現在 1 位です👏 https://t.co/48tZm6MCcb #ツイキャスインターンチャレンジ pic.twitter.com/eU8qEq9DGJ

— むらため (＞ ＜) (@new_paradigm_9) 2018年7月11日

回答コード

package main

import (
  "crypto/tls"
  "encoding/json"
  "net"
  "runtime"
  "strconv"
)

const allow2ndNum = 5
const sleepSecond = 10

func initEnv() {
  cpus := runtime.NumCPU()
  runtime.GOMAXPROCS(cpus)
}

func getConns(n int) []net.Conn {
  config := &tls.Config{
    InsecureSkipVerify: true,
    CipherSuites: []uint16{
      tls.TLS_RSA_WITH_RC4_128_SHA,
    },
  }
  results := make([]net.Conn, n)
  for i, _ := range results {
    results[i], _ = tls.Dial("tcp", "apiv2.twitcasting.tv:443", config)
  }
  return results
}

func getId(conn net.Conn) string {
  defer conn.Close()
  token := "??"
  conn.Write([]byte(
    "GET /internships/2018/games?level=10 HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if n == 0 || string(buf[2:4]) != "id" {
    return ""
  }
  // JSONをパースする時間も勿体無いので決め打ち
  id := string(buf[7 : n-2])
  return id
}

type AnswerJson struct {
  Hit     int    `json:"hit"`
  Message string `json:"message"`
  Round   int    `json:"round"`
}

func postAnswer(id, answer string, ch chan int, conn net.Conn) {
  defer conn.Close()
  token := "??"
  data := `{"answer":"` + answer + `"}`
  conn.Write([]byte(
    "POST /internships/2018/games/" + id + " HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n" +
      "Content-Length: " + strconv.Itoa(len(data)) + "\n" +
      "\n" +
      data + "\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if buf[7] == '1' && buf[8] == '0' {
    var answerJson AnswerJson
    json.Unmarshal(buf[:n], &answerJson)
    println(answerJson.Message)
    ch <- 10
  } else {
    // JSONをパースする時間も勿体無いので決め打ち
    ch <- int(buf[7] - '0')
  }
}

func reverse(a []int, startIndex int) {
  offset := len(a) - 1 + startIndex
  for i := startIndex; ; i++ {
    j := offset - i
    if i >= j {
      break
    }
    a[i], a[j] = a[j], a[i]
  }
}
func nextPermutation(a []int) bool {
  if len(a) < 2 {
    return false
  }
  i := len(a) - 1
  for i > 0 && a[i-1] >= a[i] {
    i--
  }
  if i == 0 {
    return false
  }
  j := len(a) - 1
  for j >= i && a[j] <= a[i-1] {
    j--
  }
  a[j], a[i-1] = a[i-1], a[j]
  reverse(a, i)
  return true
}
func encode(a []int) int64 {
  result := int64(0)
  k := 1
  for i := 0; i < len(a); i++ {
    result += int64(k * a[i])
    k *= 10
  }
  return result
}
func decode(a int64, n int) []int {
  result := make([]int, n)
  for i := 0; i < n; i++ {
    result[i] = int(a % 10)
    a /= 10
  }
  return result
}

func toString(q []int) string {
  result := ""
  for i := 0; i < len(q); i++ {
    result += strconv.Itoa(q[i])
  }
  return result
}
func getInitialQueries() [][]int {
  return [][]int{
    {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
    {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
    {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
    {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
    {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
    {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
    {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
    {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
    {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
    {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
  }
}
func getGameMemo() (map[int64][]int64, [][]int) {
  a := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  table := make(map[int64][]int64)
  queries := getInitialQueries()
  for {
    hits := make([]int, len(queries))
    for j, query := range queries {
      hit := 0
      for i := 0; i < 10; i++ {
        if query[i] == a[i] {
          hit++
        }
      }
      hits[j] = hit
    }
    key := encode(hits)
    val := encode(a)
    if _, exists := table[key]; exists {
      table[key] = append(table[key], val)
    } else {
      table[key] = []int64{val}
    }
    if !nextPermutation(a) {
      break
    }
  }
  return table, queries
}

func main() {
  initEnv()
  table, queries := getGameMemo()
  conns := getConns(1 + len(queries) + allow2ndNum)
  id := getId(conns[0])
  if id == "" {
    for _, conn := range conns {
      conn.Close()
    } 
  }
  hitCans := make([]chan int, len(queries))
  for i, query := range queries {
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(query), hitCans[i], conns[i+1])
  }
  hits := make([]int, len(queries))
  for i, hitcan := range hitCans {
    hits[i] = <-hitcan
  }
  answers := table[encode(hits)]
  hitCans = make([]chan int, len(answers))
  for i, answer := range answers {
    if i >= allow2ndNum {
      break
    }
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(decode(answer, 10)), hitCans[i], conns[i+1+len(queries)])
  }
  for i, hitcan := range hitCans {
    if i >= allow2ndNum {
      break
    }
    <-hitcan
  }
  for _, conn := range conns {
    conn.Close()
  }
}

さいごに

前回のFizzBuzzに比べてできることが多かったのでISUCONみたいな感じでなかなか楽しかったです.

特に,競い合える人がいたのが本当によくて,様々な知見が得られました…

前回のISUCONではお茶くみくらいしかできなかったので今回は僕もGoをチューニングして @nakario_jp を手伝えるようになりたい.

追記 (07/26)

ついでにそのままモイのインターン応募したけど落ちた笑