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

皆さんこんにちは、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とか使ってるようですが、ゆるふわ勢なのでスクリプト言語でやっていきます。

RubyHTTPSリクエストを投げる方法

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)

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

RubyHTTPSリクエストで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()

もし太陽のコアがIntelCoreだったら

春合宿でやったLTスライドの内容についてじっくり語ります。

まず以下がスライドです。

 
この内容に思い至ったきっかけとしてまずWikipediaの太陽核に関する記述があります。

太陽核 - Wikipedia

核での単位時間あたりのエネルギー生産量は、中心からの距離によって変わる。太陽の中心では、核融合の効率はモデルからの推定で、約276.5ワット/m3と見積もられる[3]。太陽の内部における体積あたりの熱生産量の最大値は、コンポストの山の熱生産量密度と比較される程度である。太陽から放出される莫大な熱量は、体積当たりの熱生産量ではなく、太陽全体の大きさに起因する。

このように太陽の体積あたりの熱密度は中心部であってもコンポスト、つまり生ごみの発酵と比較できる程度のものであるそうです。

またハードウェア系の研究室に所属していることもあって現在の半導体の熱密度の大きさは授業でも何回も取り上げられます。半導体は小型化しているので面積あたりの消費電力は大きく増加し続けて冷却方法などの問題を抱えつつあります。

この2つの事柄を合わせて、もし太陽の熱密度が半導体並であればどうなるのかという疑問がわきました。

 

まず太陽のコアの平均熱密度を求めましょう。

Wikipediaによると太陽の放出エネルギーは3.846×10^26Wでその殆どが中心核で発生しています。また核は半径10万kmだそうです。純粋に割ってやると91w/m^3となります。明るめの電球くらいですね。

次に最新のCPUであるIntel Core i7 8700Kの熱密度を求めます。IntelのデータシートによるとTDPは95Wです。またIntel Core i7-8700K delidded | VideoCardz.comによるとダイ面積は150mm^2だそうです。厚さを1mmと仮定すると体積は150mm^3となり、熱密度は6.3×10^8W/m^3となります。太陽のコアの平均熱密度のおよそ700万倍です。

 

以上のことから太陽のコアがIntel Core と同等の熱密度なった場合、発生エネルギーは700万倍となります。

輻射するエネルギーも700万倍となると仮定すると逆二乗より2600倍の距離にいれば単位面積当たりの受けるエネルギー量は現在と同量になります。

そして2600倍の距離つまり2600天文単位を公転する場合、公転周期は2600^(3/2)の132574倍、つまりおよそ13万年となります。

 

次に太陽が700万倍のエネルギー(2.6×10^33W)を生産していた場合の表面温度を雑に計算してみましょう。

まず、太陽は変形せず黒体輻射でのみエネルギーを放出すると仮定して生産エネルギーと放出エネルギーの釣り合う表面温度となるとします。シュテファン=ボルツマンの法則より温度Tの黒体が輻射する1m^2あたりのエネルギーは5.67×10^-8×T^4です。これと太陽の表面積6.08×10^12km^2から表面温度Tの場合太陽が放出するエネルギーが求まります。これと生産エネルギーとの比較により表面温度は290000Kであると求まります。もっと何億Kとか行って欲しかったんですけどエネルギーの1/4乗でしか温度が増えなかったので残念ですね。

 

最後に290000Kの輝きがどんな感じか推定してみましょう。

プランク分布によりある温度Tでの輻射される各波長の光の強さが求まります。以下のグラフに290000Kの分布を青、実際の太陽の表面温度である5770Kを橙色で示します。

f:id:kazakami_9:20180328013315p:plain

 差があまりにも大きかったので片対数グラフで表示しています。見ての通り5770Kでは可視光領域でほぼ平坦なのに対し、290000Kでは波長の短いあたりに鋭いピークがあります。ヴィーンの変位則に基づいて計算するとピークは10nmとなり、これはX線と紫外線の境界上となります。

さてこの290000Kの光を浴びるとどうなるのでしょうか。先ほど2600天文単位まで離れれば単位面積当たりの受けるエネルギー量は現在の地球と同様になると話しましたが、このグラフを見るとエネルギーの大半を紫外線として放出しているので目で見るとかなり暗いでしょう。またオゾンが吸収する紫外線は200nmから300nmまであたりっぽいので290000Kの光に多く含まれる波長の短い紫外線は地表にほぼそのまま降り注ぐでしょう。死んでしまいますね。

この有害な紫外線をあまり受けなくて済むような距離まで離れると、今度は受けるエネルギー総量が少なくなり過ぎそうですし、290000Kの太陽にはハビタブルゾーンなさそうですね。

 

まとめ

  • 太陽は熱密度は大したことないが体積が膨大なので総エネルギー量が大きい。
  • CPUの熱密度はかなり大変な領域にまでなっている
  • 290000Kは最早輝きの向こう側

 

 

MinecraftでFPGA

この記事は KMC Advent Calendar 2017 - Adventar の17日目の記事です。

昨日の記事はCHY72さんの競プロに疲れた人のNim言語 - (/^^)/⌒●~*$ a(){ a|a& };a です。Nimいいですね、いいです、すごくいいです。

はじめに

今日の記事を担当します📛(KMC_id:kazakami)です。1回生です。(学部1回とは言ってない)

最近後輩がサーバ管理の練習のためにマイクラサーバ建てたりしたこともあってマイクラ熱が再び湧いてきてます。マインクラフトではいろいろな人が色々なものを作っていますが、「minecraft FPGA」でググってもそれらしきものが出てこなかったので新規性チャンスと思いやってみました。

 

FPGA

FPGA(field-programmable gate array)とは動的に回路の構成を変更可能な回路の一種です。典型的なFPGAは再設定可能な論理セルと再設定可能な配線セルから構成されています。詳しくはググってください。

 

Minecraft

知っている人が多いと思いますが、Minecraftとはブロックを設置・撤去して地形破壊したり建物立てたりできるゲームです。このMinecraftには”レッドストーン”という要素があります。レッドストーンを並べて作った配線はスイッチやボタン等で活性化することができ、これによって扉の開閉を行ったりピストンを動かしたりできるようになってます。レッドストーンはいい感じに組み合わせることでNOT回路やOR回路を作ることができます。つまりチューリング完全です。

 

レッドストーン回路

レッドストーンの配線はスイッチによって活性化されます。

f:id:hiroshi-matsuoka-2125:20171216193025p:plain

ただしこれは距離の制限があり15ブロックまで活性化しません。

f:id:hiroshi-matsuoka-2125:20171216193745p:plain

この画像を見ると上の方では赤く光っていません

 

f:id:hiroshi-matsuoka-2125:20171216194041p:plain

そこで15ブロックより遠くまで信号を伝達するためにリピータと呼ばれるブロックを挟むことになります。実はこれがかなり厄介で、信号の伝達遅延はかなり大きくなり、また信号を片方向にしか伝達できなくなります。

 

取敢えず作ってみる

小さな構成で作ってみます。

f:id:hiroshi-matsuoka-2125:20171216220756p:plain

 ■が論理セル・〇が配線セルで、このように論理セル4個とその周りを囲む21個の配線セルからなる設計とします。この規模だとかなり小さな回路しか構成できませんが、まぁ動けばいいんです。

論理セル

 

f:id:hiroshi-matsuoka-2125:20171216220808p:plain

論理セルはこのように3-bit LUTを1つだけ含むような構成とします。

f:id:hiroshi-matsuoka-2125:20171216224311p:plain

マイクラで実装するとこのようになります。白羊毛部分がデコーダで黒羊毛部分がメモリとなっています。黒羊毛上のスイッチで0と1を指定します。

配線セル

f:id:hiroshi-matsuoka-2125:20171216220759p:plain

配線セルはこのような構成となります。先述の通りレッドストーンの配線は片方向にしか信号を伝達できないので入力同士・出力同士をつなぐスイッチがありません。

f:id:hiroshi-matsuoka-2125:20171216225436p:plain

シアンの羊毛上にスイッチが置かれています。

 

全体の実装と動作テスト

実装した論理セル配線セルをシュッとコピーして並べて完成です。

f:id:hiroshi-matsuoka-2125:20171216230419p:plain

並べるとかなり論理回路っぽく見えますね。

折角作ったのでこのFPGA上に回路を構成しましょう。今回は試しにSRラッチ回路を構成します。LUTを1個使いNORを表現するので、LUTを2個も使った贅沢なラッチ回路になります。

 

 

f:id:kazakami_9:20171216234640p:plain

 右側のスイッチがSet入力、左側のスイッチがReset入力、真ん中が出力となっています。

f:id:kazakami_9:20171216234815p:plain

Set信号を入力をオンにすると出力もオンになります。

f:id:kazakami_9:20171216235112p:plain

 Set信号をオフにしても出力はオンで維持されます。

f:id:kazakami_9:20171216235150p:plain

Reset信号をオンにすると出力はオフになります。

ラッチ回路が構成できました!!!

改善案

今回作った回路は5×5の25個のセルを並べておきながら論理セルが4個しかないため大した回路が作れませんでした。配線セルの信号伝達遅延もかなり大きいことから、ただ信号を伝達するだけでなく演算しながら伝達した方が無駄も少なくなるのではと考えられます。そこで論理セルと配線セルの区別をなくし単一の汎用セルを並べることで同じ回路面積でもより多くの種類の回路を構成可能にしようと考えました。

f:id:kazakami_9:20171217000843p:plain

f:id:kazakami_9:20171217000533p:plain

この汎用セルは4-bitのLUTを1つ含みます。このセルは上で示した論理セル・配線セルのどちらの機能の実現できます。これによって同じ5×5の回路面積でもより大規模な回路を構成可能になるはずです。

 しかしこの設計の汎用セルでは依然としてラッチやフリップフロップを構成するのに複数のLUTを消費して実現しないといけません。別途DFF等をセルに組み込めば解決するかもしれませんが、レッドストーンの配線が高遅延であるためマイクラにおいては全てのセルに同時にクロック信号を入力するのが難しいのです。これの解決はskewed clockを使ったりすればいいのかもしれませんが今後の課題とします。

 

最後に

 FPGAのプロやマイクラの強い人から見ると突っ込みどころ満載かもしれないので、「この分野には詳しくないのですが~」みたいな質問が来ないか戦々恐々としてます。とはいえ、マイクラでFPGAという分野に関しては多分他に誰もやっていない以上私が第一人者です。皆さんも誰もやっていないような組み合わせを見つけて雑に新規性していきましょう。

 明日の KMC Advent Calendar 2017 - Adventar はwalkureさんで「まぁいけるやろ。」です。いけるいける。大丈夫大丈夫。知らんけど。