(/^^)/⌒●~*$ a(){ a|a& };a

きょうと…のだいがく？にかよってるんですけど！

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

はじめに

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

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

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

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

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

解法

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

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

戦略としてはこうです.

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

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

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

正解としてありえるのは 0123456789 の順列なので 約360万通りしかありません. ですので,ランダムに作成したn個のリクエスト ([0123456789,6574839201,...,7564312098] など) に対して返ってくる Hit数の列([0,0,5,...,0,1]など)を予めメモして置くことが可能です. n個のリクエストからHit数の列が得られるので,これなら一瞬で答えリストが求まりますね. 試行の結果 n=10 くらいがちょうどよかったので n=10にしました.

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

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

import sequtils,strutils,strscans,algorithm,math,future,macros
import sets,tables,random

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)
proc check(queries:seq[int]) :int{.discardable.}=
  stdout.write queries.join("")[0]
  stdout.flushFile
  if queries.len() != queries.sorted(cmp).deduplicate().len() : return
  var table = initSet[int]()
  var sum = 0
  for permutation in permutations: 
    var key = 0
    var bit = 1
    for query in queries:
      var h = query xor permutation
      let hit =
            ((h and 0x00000_0000f) == 0).int8 +
            ((h and 0x00000_000f0) == 0).int8 +
            ((h and 0x00000_00f00) == 0).int8 +
            ((h and 0x00000_0f000) == 0).int8 +
            ((h and 0x00000_f0000) == 0).int8 +
            ((h and 0x0000f_00000) == 0).int8 +
            ((h and 0x000f0_00000) == 0).int8 +
            ((h and 0x00f00_00000) == 0).int8 +
            ((h and 0x0f000_00000) == 0).int8 +
            ((h and 0xf0000_00000) == 0).int8
      key += hit * bit
      bit *= n
    sum += 1
    table.incl(key)
  let size = table.len()
  if size <= maxValue: return size
  maxValue = size
  let answers = queries.map(fromHash)
  echo(($answers).replace("], ","],\n "))
  echo size," patterns"
  return size


const gaNum = 10
var queries = newSeqWith(gaNum,newSeqWith(n+1,getRandom(n)))
while true:
  let preQueries = queries
  var nowQueries = newSeq[tuple[v:int,q:seq[seq[int]]]]()
  for i in 0..<gaNum:
    for j in (i+1)..<gaNum:
      var p = preQueries[i]
      var q = preQueries[j]
      if rand(1.0) < 0.1: q = newSeqWith(n+1,getRandom(n))
      var r = newSeq[seq[int]]()
      for k in 0..<(n+1):
        if rand(1.0) > 0.5: r &= p[k]
        else: r &= q[k]
      for k in 0..<(n+1):
        if rand(3) == 1:
          swap(r[k][rand(n-1)],r[k][rand(n-1)])
      nowQueries &= (r.map(toHash).check(),r)
  nowQueries.sort((x,y)=> y.v - x.v)
  let nexts = nowQueries[0..(gaNum-2)]
  queries = nexts.mapIt(it.q) & preQueries[0]
  echo nexts.mapIt(it.v)

結果,

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

が得られました.

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

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

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

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

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

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

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

CipherSuitesを変える

このままでは 1179kを超えることができません. 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 を用いてオーバーヘッド無しに回答を送信します.

TLSのコネクション先に貼るのはHTTPあんまり自分で喋ったことなかったのでちょっと挑戦して辛くてやめてましたが,1位奪還したかったので気合で実装しました.

これで1179.5k が出て,1位になることができました.やったぜ.

回答コード

package main

import (
    "encoding/json"
    "fmt"
    "strconv"
    "time"
    "runtime"
    "crypto/tls"
    "net"
)
const allow2ndNum = 5
const sleepSecond = 10
func initEnv(){
    cpus := runtime.NumCPU()
    runtime.GOMAXPROCS(cpus)
}

type Timer struct { pre time.Time }
func newTimer() *Timer { return &Timer{ pre:time.Now() } }
func (timer *Timer) check() time.Duration {
    now := time.Now()
    result := now.Sub(timer.pre)
    timer.pre = now
    return result
}

func getConns(n int) []net.Conn {
    config := &tls.Config{
        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 "" }
    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)
        fmt.Println("round",answerJson.Round)
        fmt.Println(answerJson.Message)
        ch <- 10
    } else {
    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 toint64(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 fromint64(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{
        {2, 6, 4, 3, 0, 9, 7, 1, 5, 8},
        {8, 7, 6, 9, 0, 5, 3, 2, 1, 4},
        {4, 7, 2, 3, 9, 1, 5, 0, 8, 6},
        {0, 9, 1, 5, 2, 6, 3, 4, 8, 7},
        {2, 1, 7, 5, 9, 3, 6, 8, 0, 4},
        {0, 3, 8, 7, 6, 9, 5, 4, 1, 2},
        {6, 0, 9, 1, 4, 5, 7, 8, 2, 3},
        {5, 8, 6, 1, 3, 9, 4, 2, 0, 7},
        {7, 0, 5, 9, 3, 4, 6, 1, 8, 2},
        {5, 4, 8, 9, 2, 3, 7, 0, 6, 1},
    }
}
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 := toint64(hits)
        val := toint64(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()
    sleepSec := 0 * time.Second
    table,queries := getGameMemo()
    for {
        time.Sleep(sleepSec)
        sleepSec = sleepSecond * time.Second
        timer := newTimer()
        conns := getConns(1+len(queries) + allow2ndNum)
        fmt.Println("after table:",timer.check())
        id := getId(conns[0])
        if id == "" {
            for _,conn := range conns { conn.Close() }
            continue
        }
        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[toint64(hits)]
        hitCans = make([] chan int,len(answers))
        if len(answers) > allow2ndNum {
            fmt.Println("too many answers :",len(answers), " :: try ",allow2ndNum," answers")
        }
        for i, answer := range answers {
            if i >= allow2ndNum { break }
            hitCans[i] = make(chan int)
            go postAnswer(id,toString(fromint64(answer,10)),hitCans[i],conns[i+1+len(queries)])
        }
        for i, hitcan := range hitCans {
            if i >= allow2ndNum { break }
            <-hitcan
        }
        fmt.Println("final      :",timer.check())
        for _,conn := range conns { conn.Close() }
    }
}

さいごに

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

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

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