モイ！ツイキャスのインターン応募前プレテストに参加してみた

皆さんこんにちは、Kazakami_9です。

ツイキャスとか言うのを運営しているモイ！とかいう会社がインターン応募のテストを行っていて、おもちゃとしてよいとのことなので参加してみました。今回はシュッとかいてサッと得点を取ることをメインとしてやっていきます。この記事ではその際に書いたコードについて語ります。
chy72.hatenablog.comのようなガチなものではないのでご注意ください。

テスト問題

よくあるHit&Blowです。手元で生成した文字列をサーバに送って、HitとBlowの数が返ってきます。しかしユーザ側でLevelを3から10の間で設定できます。このレベルは答えの文字数であり、10であれば0~9まですべての文字を1回づつ含んだ10文字の文字列が答えとなります。つまりLevel=10とすると適切な文字列を投げればHitの数+Blowの数は必ず10となり、Blowを無視することができます。Hit&Blowというゲームがお題のはずが、実は"Hit"というゲームをプレイすればいいのです。また成績もLevelが高い方が高くなるため、Level=10以外を選ぶ理由がありません。多分制作側の意図でしょう。知らんけど。

使用する言語

シュッと書きたいという事、HTTPSリクエストを行う必要がある事、JSONを扱う必要がある事、これらの理由から使用する言語としてRubyを選びました。ガチ勢はGoとか使ってるようですが、ゆるふわ勢なのでスクリプト言語でやっていきます。

RubyでHTTPSリクエストを投げる方法

HTTPリクエストは良く投げるのですがHTTPSはやったことがなかったので備忘録的に書きます。

uri = URI.parse(url)
https = Net::HTTP.new(uri.host, uri.port)
https.use_ssl = true
payload = {
  "answer" => num
}.to_json
req.body = payload
res = https.request(req)

これでJSONをHTTPSで送ってresに返答が入ります。

RubyのHTTPSリクエストでHTTPヘッダを追加する方法

これも初めてで知らなかったので備忘録
上記のコードでリクエストを送る前に

req["Headerrr"] = "hogeeee"

とすることで

Headerrr: hogeeee

がHTTPヘッダに追加されます。

"Hit"のアルゴリズム

"Hit"を解くためのアルゴリズムですが、シュッと解きたかったのでできるだけ実装の軽そうなものを考えました。ガチ勢は並列化したり、確率を考えて色々やったりしてるようですが、私は面倒なのでしません。

  1. まず"0123456789"という文字列を作ります
  2. boolの10要素の配列ok[]を用意してfalseに初期化します
  3. i=1, j=2をセットします
  4. ok[i]とok[j]の双方がfalseなら文字列のi文字目とj文字目をswapしてHitの数の変化を見ます
  5. Hitの値が10なら終了
  6. Hitの値が2増えたならok[i]とok[j]をtrueにセットします
  7. Hitの値が2減ったならok[i]とok[j]をtrueにセットしてswapをなかったことにします
  8. iとjをいい感じに変化させて4に戻る

こんな感じで文字列をスワップさせながらHitの値が2変化すればその2つは正しかったのだろうと推測してスワップ対象から外してループするという感じです。2重ループと配列と文字列のスワップができればいいのでプロコンの第一問程度のアルゴリズムですね。Hitの値が1だけ変化した場合も何とかしてやるべきなんでしょうが面倒なのでしません。

高速化のための工夫

これもまたガチ勢はTLSの暗号化強度を弱くしたり、TCPコネクションを予め沢山張っておいたりなどいろいろやってるようですが、やはり面倒なのでしません。単純ながら効果のある方法としてサーバまでの遅延の少ない東京のVPS上で動かすという事をやりました。結構効果あります。
後はレイテンシが少ない時間帯を狙うくらいです。ping打って1ms台ならよし、2ms超えてれば再走しましょう。

まとめ

完走した感想ですが、こんな け゛ーむに まし゛に なっちゃって と゛うするの(負け惜しみ)。結構楽しいおもちゃでしたが、ガチ勢に勝てなかったのが悔しいです。インターンテストの期間終了して最終的な順位は8位でした。
https://i.gyazo.com/7d9f89e291b66f3c8bd19181fc756814.png
開示タイムとしてソースコードを乗せておきます。

# coding: utf-8
require 'uri'
require 'net/http'
require 'json'
require 'parallel'

$token = "Your Token"

def get_id()
  url = "https://apiv2.twitcasting.tv/internships/2018/games?level=10"
  uri = URI.parse(URI.encode(url))
  https = Net::HTTP.new(uri.host, uri.port)
  https.use_ssl = true

  req = Net::HTTP::Get.new(uri.request_uri)
  req["Authorization"] = "Bearer " + $token

  res = https.request(req)

  #puts res.body

  id = JSON.load(res.body)["id"]
  #puts id
  return id
end

def get_post_req(id)
  url = "https://apiv2.twitcasting.tv/internships/2018/games/" + id
  uri = URI.parse(url)
  https = Net::HTTP.new(uri.host, uri.port)
  https.use_ssl = true

  req = Net::HTTP::Post.new(uri.request_uri)
  req["Authorization"] = "Bearer " + $token
  return req, https
end

def attempt(num, req, https)
  payload = {
    "answer" => num
  }.to_json
  req.body = payload
  res = https.request(req)
  return JSON.load(res.body)
end

#i文字目とj文字目を入れ替えた文字列を返す(i < j)
def str_swap(str, i, j)
  #return str[0, i] + str[j] + str[i+1, j - i] + str[i] + str
[j + 1, str.length]
  new_str = str.dup
  new_str[j] = str[i]
  new_str[i] = str[j]
  return new_str
end

def main()
  id = get_id()
  req, https = get_post_req(id)
  str = "0123456789"
  high_hit = attempt(str, req, https)["hit"]
  puts high_hit
  ok = []
  for i in 0..9 do
    ok[i] = false
  end
  while true
    for i in 0..8 do
      do_break = false
      if ok[i] then
        next
      end
      for j in i+1..9 do
        if ok[i] || ok [j] then
          next
        end
        new_str = str_swap(str, i, j)
        a = attempt(new_str, req, https)
        hit = a["hit"]
        #puts hit.to_s + ": " + new_str
        if hit == 10 then
          puts a
          exit
        end
        if hit == high_hit + 2 then
          ok[i] = true
          ok[j] = true
        end
        if hit > high_hit then
          high_hit = hit
          str = new_str
          #puts "change!"
          do_break = true
          #break
        end
        if hit + 2 == high_hit then
          ok[i] = true
          ok[j] = true
          #break
        end
      end
      if do_break then
        do_break = false
        break
      end
    end
  end
end

main()