mayoko’s diary

プロコンとかいろいろ。

ISUCON 8 予選に参加しました

ISUCON8 の予選に参加しました。

詳しい記事は我らがリーダー(?)が書いています
brookbach.com

とりあえず僕も書くかっていうだけ書いておきます。
今回は"前半戦は"座るだけではなかったので良かった(多分一番おいしいところを持っていった)

本番の流れ

僕はサーバーの設定ファイルとかよくわからない(えぇ…)のでそこらへんは任せて最初からアプリの実装を見たりデータベースの仕様を確認したりしていました。
で, get_event 関数がクソ遅そうだったのでそれの報告と改善方法を言ったら「やって~」と言われたので実装

実装内容

  • 各 sheet 毎に SQL を呼び出しているのが遅そうなので一回のクエリですべての情報を引き出すように変更
    • 具体的には SELECT * FROM reservations WHERE event_id = ${id} みたいな感じのクエリを呼び出せば, イベントごとの sheet 情報が引き出せる
  • sheet 情報は固定なので "ベタ書き"(???)

okeigo 君が開発用サーバーも用意してくれてたのでそっちでテストしてましたが, 7, 8 回書き直したので自分の実装力の NASA を感じる
でも 14:00 くらいに実装出来たのでベンチ通したらスコアが 600 点 -> 3000 ~ 5000 点くらいになってテンションが上がった

get_event 周りの所感

  • twitter 見ると「get_event 改善で 15000 点は行く」と言ってる人がいるんですがそうなんですかね…
    • 前提として 3 台構成にしてるとかサーバーのパラメータをいい感じに調整してるとかがあるからなのか
    • python が遅いからなのか

~競技終了まで

これ終わった後は特に改善できそうなところがよくわからなかったので終わり

  • 他の 2 人が改善していたっぽい
  • データベースの reservations に event_id, user_id, sheet_id の外部キー登録すると改善するのかなーと思ったけどパッとうまくいかなかったし, データベース変更しちゃったらどうしようという不安に襲われたのでやめた

最終的には 8000 点くらいだったっぽく, 予選落ち

  • 残念

まとめ

UNDERTALE はいいぞ!
undertale.jp
(PVだけ見るとオススメしづらそうなのやめろ)

TypeScript を使ってオセロを実装してみた(2)

やったこと

前の続きです。
mayokoex.hatenablog.com

今回は通信対戦できるようにしました。
また, せっかくなので, それを web 公開しました。こちらから遊べます。(出来がアですが)

オセロ

  • 「1」と書いてあるところで番号を選んで部屋を選択し, Name と書いてあるところに名前を入れると, 指定した番号の部屋に入れます。
  • 部屋に二人入ると対戦が始まります。

方針

今回は, nodejs と socket.io を使いました。
nodejs はサーバーを立てるときによく使うっぽくて, また, socket.io はチャットをするときとかによく使われるっぽいです。
(実際, socket.io でググるといろんな人がチャットツールを作っています)

で, 公開するために heroku というのを使いました。
jp.heroku.com

苦労したこと

実装はかなり簡単だったのですが(さすが socket.io), 環境構築系ですごく苦労しました。

npm

まず, javascript は外部ライブラリをインストールしないといけないです。
で, このインストールは gcc みたいに一回インストールしたらもうやらなくていいみたいなものではなく, 作りたいアプリごとにインストールするものです(node_modules というディレクトリに全部入ります)。
このインストールは, npm install [package 名] --save とやると出来ます。

また, node_modules に入るのは javascript のコードなので, typescript からすると型とかそもそもインストールしたのが何かわからない, という状況なので, 型情報を教える必要があります。
このインストールは npm install @types/[package名] --save とやると出来ます。

これらのことを, たたもさんに教えていただきました。ありがとうございました!

ここら辺のことを把握すると, このページで書かれていることのコマンドの意味が分かりやすいです。
ics.media

browserify

今回の構成では,

という流れで javascript コードが生成されますが, main.js の方は, コンパイルしたコードを動かそうとしても「require ってなんだよ」みたいなことを言われて実行することが出来ません(require が nodejs 専用の機能で普通に js を動かす分には利用できないとかなんとか)。

今回は socketio を使う際に require がコンパイル後に使われていて, そこでエラーになりました。

この問題は, browserify というのを使うと解決しました。
ただこれをやると行数が 500 行くらいから 8000 行くらいになるのでこれで正しいのかと若干心配になります…

heroku でちゃんと表示されるようにする

わけもわからずコードをランダムウォークさせてたらいつの間にか表示されるようになりました。

重要な変更点としては,

express パッケージの追加
  • 結局オセロプレイ画面になる index.html を開いてほしかったのですが, それをやるときに app.js 内で
const app = express();
const server = http.createServer(app);
app.use(express.static(__dirname + '/public'));
app.get('/', (request, response) => {
    response.sendFile(__dirname + '/index.html');
});

とやると出来ました。
ただし, フォルダ構成として, /public/ に index.html, style.css, main.js が置いてあります。
app.use で「public にあるファイル使うぜー」って言って, app.get で, 「アクセスされたら index.html 開くぜー」と言っていそう。

ポート番号

上のコードのあとに,

server.listen(process.env.PORT || 8000);

をやるとアクセスしたときにちゃんとページを開いてくれます。
process.env.PORT ってお前どっから出てきたんだ。
ローカルで実験するときは localhost:8000 とかでやってたので出来てるんですが, heroku でやるときはポート番号が違うっぽいです(どこで決めてるのかは知らないですが)。

node_modules は git の管理下に置かない

node_modules を git の管理下に置いておくと, push したときに reject されます。
.gitignore で node_modules を消しておく必要があります。

まとめ

web 難しい…

ホモグラフィ変換

はじめに

OpenCV でホモグラフィ変換すると遅いので OpenGL でホモグラフィ変換する, というのはよくある流れだと思うのですが, 最初に OpenCV でホモグラフィ変換用の行列 H を求めていると, OpenGL 用の座標系 { \displaystyle
(-1, 1) \times (-1, 1)
}に変換するのがめんどくさいです。

(ちなみに, OpenCV でホモグラフィ変換する場合には, warpPerspective 関数を使います)

ここで, H はなんかの座標系から画像座標系へのホモグラフィ変換行列だとします。この画像座標系の画像の高さを h, 横の長さを w とします。

すると,

  • (0, 0) から (-1, -1)
  • (0, h) から (-1, 1)
  • (w, h) から (1, 1)
  • (w, 0) から (1, -1)

のホモグラフィ変換行列 H' がわかれば, なんかの座標系から OpenGL へのホモグラフィ変換行列は, H' * H として記述できます。

4 点と 4 点の間を結ぶ平面間の変換はホモグラフィ変換でできるのですが, 直感的に思いつく変換だとうまくいかなかったので, 少し真面目に計算して H' がどうなるのかを調べたというのがこの記事です。

結果

{ \displaystyle
H' = \begin{pmatrix} 2/w & 0 & -1 \\ 0 & 2/h & -1\\ 0 & 0 & 1 \end{pmatrix}
}

まとめ

OpenGL はもうちょっと気軽に使えるようにして。

TypeScript を使ってオセロを実装してみた

オセロです。
index.html, style.css, main.ts を同じフォルダに入れ, main.ts をコンパイルして main.js を作って, index.html をブラウザで開くと一人二役のオセロで遊ぶことが出来ます。
github.com

追記:こちらから遊べます
オセロ

通信対戦までやりたいので, まだ途中ですがある程度まとまったのでとりあえず公開です。
通信対戦は typing war みたいなのかっこいいので真似出来ればしたいです。
Typing War | traP

微妙にオブジェクト指向を意識しました。
クラス間の関係みたいのをメモした図はこちらです(オブジェクト指向の考えかたわからん)。
f:id:mayokoex:20180617100712j:plain

途中でめんどくさくなって if (this.board.state.board[i][j].get() === Cell.white) とか書いてあるのは御愛嬌です。
本当は Board クラスに get(i, j) っていうのを入れておいたほうが良さそうです。

今一番気になってるのは, createElement の型をどう書くのってところです(無理なのかな?)。
this.elem = createElement("div");
とか書くのですが, クラスのメンバとして elem を入れてないとダメなのでその時に elem: type みたいな感じで書かないとダメですが, type が分からないので人生終了です。

一時変数だったら const elem = createElement("div") とか書けば賢い visual studio code 君がインテリセンスを発動してくれるのですが, クラスのメンバだとダメです。

追記:しょラーさんに教えていただきました。ありがとうございます!

AGC016 B: Colorful Hats

面白かったので考察をメモしておこうかなと思いました。
B - Colorful Hats

考察

こういう問題は必要十分条件を考えるのが定石だろうと思います。
とりあえず考察として, 「数字は x か x+1 に絞られる」というのはちょっと考えてわかりましたが, それ以外は特に検討がつかないのでとりあえず実験してみます。

N <= 5 程度で可能なリスト, 不可能なリストを適当にピックアップしました。
実験してる間に気づいた一般的なことは, 「長さ N に対して, 全員が x 種類と主張する場合には, x <= N/2 または x = N-1 の時は必ず OK」だけでした。

「単純な例から初めて決まった動きをさせると解が構成できる」みたいな方法もできるかなと思いました。
今回の場合は, それぞれの人の帽子の色を始めに固定しておいて, そこから一人ずつ帽子の色を変えていく, みたいな方針です。
一番基本的な形とその時に感じた, 「それぞれの人の帽子がバラバラ」というのから初めて色を変えていきます。
以下は左が帽子の色で, 右がその時のそれぞれの人々の主張です。

  • ABCDE: 44444
  • BCDAA: 33344
  • BCAAA: 22333
  • BAAAA: 12222
  • BCBAA: 32333
  • ...

この実験をやって突然「帽子がユニークな人は x と主張してユニークでない人は x+1 と主張する」ことに気づきました。
全体で x 種類の帽子があり, かつ帽子がユニークな人が y 種類いる場合, (y <= x)

  • (1, 2, 3, ..., y), (y+1, y+2, ..., x), (y+1, y+2, ..., x), (...)

というように帽子がかぶられればよく, このような解が生成できる必要十分条件は, y + (x-y) * 2 <= N です。

とりあえずこれで実装して実は全てが x の場合でもうまくいかないかなーと思いましたが, そううまくは行かなかったので, 場合分けしてホイっと解きました。

感想

考察書いてみれば思考過程振り返れるかなーと思ったけど結局一番大事な考察に突然気づいてやがるのでなんかなぁ。
「どうやって思いつくか」が大事だと思うけど実験してたら突然思いついた感がある

javascript で 2048 を実装してみた

何をやったのか

javascript 初心者が javascript で 2048 を実装した話です。

javascript で初めてアプリっぽいものを作ったのでやったことを残しておこうかなーと思って書いています。
作ったものはこちらです。
github.com

  • index.html, main.js, style.css を同じフォルダに置いて index.html をブラウザで開くと遊べます。
  • 「AUTO」を押すと AI が起動して勝手に動かしてくれます。「AUTO」を押すとボタンが「STOP」に変わりますが, それを押すと AI が止まります。

追記:遊べるようにしました
https://mayoko.github.io/myGame/
AI はなんとモンテカルロをやっているのでかなり重いです

クラス構成

javascript は private とかなくてガバガバですが 一応クラスがあります(altjs とか使うとそういうのもちゃんとするんですかね?)。
作法的に private method を作りたいときは 関数名の最初に "_" を付けるっぽいです。

で, クラス構成ですが, 以下のようになっています。

  • Game クラス
    • 以下で述べる State クラス, Animation クラスをまとめて動かします
  • State クラス
    • ゲームの論理部分を担当するクラスです(上に動かしたらセルがどう動くーとか)(セルというのは「2」とか「128」とか書いてある一マスのことです)
    • 本当は分けて書いた方が良いと思うのですが, 面倒なのでアニメーションに必要な情報もここで計算しています
  • Animation クラス
    • 下で述べる Cell クラスを用いて, セルが動くとかセルが表れるといった Animation を制御します
  • Cell クラス
    • セル単体のアニメーションをサポートするクラスです
  • GameAI クラス
  • State を受け取って, どういう風に動けば良さそうかを考えるクラスです

以下で各クラスの説明をしていきます

State クラス

主な役割は, 「上/右/下/左に動かしたときに, 各セルがどこに行くか」を計算することです。
これは calcNextState というメソッドて計算しているのですが, まぁこの記事を見ている人なら簡単に実装できると思います。
といいつつ定数倍遅くなりつつ楽に実装できる方針をとったのでちょっと説明します。

  • まず, 上に動かしたときにどういう風に動くかを計算できるようにしましょう。
    • これは, 上の行から順番に上に動かす, というような方針を取れば実装できます。
  • 上に動いた場合さえ計算できれば, 例えば右に動いた場合の計算は, 「board を 3 回時計回りする -> 上に動かす -> board を 1 回時計回りする」というように実装することによって, 上に動かすのを利用して実現することができます。

Animation クラス, Cell クラス

これが一番大変でした。
アニメーションは結局要するに,

  • アニメーション開始からどれくらい時間たったかを計算することによって, 進捗率を求める
  • 進捗率に応じて, 位置なり角度なりを制御する
  • 進捗率が 100% 出ないのであれば, setTimeout なり requestAnimationFrame なりを呼び出して続きをやらせる

ということをやればいいです。

コードにして書くと以下の通りです(適当に書いたので間違ってるかもしれません。また, const に値を入れていないので当然コピペしても動きません)。

// アニメーション開始時間
let start = null;
// アニメーションにかける時間[ms]
const time = 1000;
// 例えば fromX から toX に動かすアニメーションを作りたい
const fromX, toX;
// 動かす対象
const elem;

// アニメーション更新関数
const update = () => {
    if (!start) {
        start = new Date();
    }
    // 進捗率
    let progress = (new Date() - start) / time;
    progress = Math.min(1, progress);
    const x = fromX + (toX - fromX) * progress;
    // 位置指定
    elem.style.left = `${x}px`;
    // まだ進捗率 100% でないなら続き
    if (progress < 1) {
        requestAnimationFrame(update);
    }
};
// アニメーション開始
requestAnimationFrame(update);

これだけ聞くとかなり簡単に聞こえるのですが, 個人的にややこしかったのは, setTimeout なり requestAnimationFrame は, while 文みたいに「一回実行したらアニメーションが終わるまで続きを実行しないで待つ」みたいな関数ではないということです。

これのどこに注意が必要なのかというと, 例えば今回の場合, 4 と 4 が合体して 8 になる, というようなアニメーションをする場合,

  • 2 つの 4 が移動するアニメーションをやる
  • アニメーションが終わったのを確認してから合体して消える片方の 4 を消す
  • 4 を 8 に変化させるアニメーションを入れる

というようにアニメーションを進行させていきたいわけですが,

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 合体して消える要素は削除
removeChild(elem);

というように書いてしまうと, アニメーションをしている間に elem 要素が消えてしまうので, update 関数から「そんな要素ねぇぞオラァ」と怒られてしまいます。

また,

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 2 つ目のアニメーション更新関数定義
const update2 = () => {...};
// アニメーション2開始
requestAnimationFrame(update2);

という風に書いてしまうと, 1 つ目のアニメーションが終わる前に 2 つ目のアニメーションが始まるので「オイオイ待ってくれよ」ということになります。

ただ逆に, アニメーションを同時に動かしたいときは, for 文で requestAnimationFrame を発火させておくだけでいいので楽っちゃ楽かもしれないです。
2048 の場合, 複数セルを同時に動かさなければならないことが多々あるので, for 文 requestAnimationFrame 同時発火手法はイケそうな感じがしましたが, 今回はそのような実装方針にしていません(後で説明します)。

で, じゃあどうすれば良いかということなんですが, 主に 3 つ工夫(?) しました。

  • アニメーションされる要素を用いずに, どういうアニメーションがされるのかを前計算しておく
  • アニメーションを連続させるときは, 1 つ目のアニメーションが終了したタイミングで次のアニメーションが発火するように setTimeout でタイミングを測る(これもっとうまくできる方法あったら知りたいです。知っている方いたらお知らせください。)
  • 進捗ごとにどのように要素が動くのか定義する関数(progress を引数にとって要素を動かす関数) と アニメーション更新関数(update 関数) を分ける

それぞれについて説明していくのですが, その前に Animation クラス, Cell クラスがどのようなクラスなのかを説明しておきます。
2048 のアニメーションですが, 大きく分けると「移動」, 「出現」に分けられて, 「出現」はさらに 2 つに分けられます。

  • ランダムにセルが出現するときにあるような, 何もないところからだんだん膨らんで現れるやつ
  • 2 と 2 が合体して 4 が表れるときにあるような, セルが普段の高さ, 幅よりもちょっと膨らんでからもとに戻るやつ
  • Cell クラス
    • アニメーションの進捗率を受け取ると, 「移動」の場合は今セルがどこにいるべきか, 「出現」の場合は今セルがどれくらいの大きさか, を計算してくれる
  • Animation クラス
    • Cell クラスの集合を保持しておく
    • アニメーションするときには, 進捗率を管理しながら, 「移動」, 「出現」を各 Cell にやらせる
    • アニメーション更新関数(update) を呼び出すのはここであって Cell クラスの中でではない
前計算

これはまぁわかりやすいですね。
どういうアニメーションにするかあらかじめ計算しておくことによって, コードが読みやすくなります。
javascript はオブジェクトを参照で受け取るっぽいので, Cell のまま管理しようとすると想定外の Cell がいつの間にか消えていたりしてややこしいです。

発火タイミングを調整

1 個目のアニメーションに 100ms 使うとかわかっている場合には, 2 個目のアニメーションは 1 個目のアニメーションが発火した 110ms 後とかに発火すると良さげですね, というようなことです。setTimeout は呼び出す関数が次にいつ呼び出されるかを指定できるので, 最初の呼び出しだけ setTimout を使って後は requestAnimationFrame を使う, みたいなことをやりました。

javascript のライブラリで anime.js というアニメーションをやってくれるすごいやつがいるっぽいです。
anime.js で連続したアニメーションをやりたい場合は, 1 個目が発火した後何秒後に次のアニメーションを発火させるか, みたいのを指定して連続アニメーションを実現しているようです。
今回のやり方も同じように発火させるタイミングを時間で指定しているので, 結局やったことは anime.js 手法を自分で書いた感じになったのでしょうか(詳しく知らないので想像でしかないですが)。

animejs.com

Animation クラスと Cell クラスで役割を分割

今回は, Cell クラスは「進捗率を受け取ると, それに合わせて二次元位置であったりセルの大きさを調整する」ということを行い, Animation 関数の中でアニメーション更新関数(update)を呼び出すようにしました。
こっちの実装方針の方が, アニメーションが終了したときの処理を柔軟に書きやすいという利点があるような気がします。

例えば, セルの「移動」, 「出現」のアニメーションが終わるまでは, 別の矢印キーが押されても反応しないようにするために, Animation クラスには finish という bool 値があるのですが, これは update 関数内の進捗率が 100% になったら finish を true にする, というような処理を行うことによって簡単にできます。
一方で, Cell の中で update 関数を書くような方式にした場合, 全ての Cell のアニメーションが終わってから finish を true にする, というような処理を書くのが面倒な気がします。
(一つの方法として, ある Cell にのみ finish を参照渡しして, その Cell のアニメーションが終わったら finish = true にする, という方法があると思いますが, あんまりきれいじゃない)

なんか冷静に考えると別にどっちでもいいような気がしてきました, はい。

ACM-ICPC 2017 アジア予選に参加しました

参加しました。しばらく競プロはお別れな気がする。

前日まで

前回のDCCCでなんか言っていたが特に達成していない(9/25 AC)

せっかくなので JAXA エクスカーションに行った


なんかあるのかと思ったけど普通の見学だったのでうん, まぁという感じ
せっかくなので風船飛行機を買った(324 円)
たまに飛行機を飛ばして害悪行為をしておりましたすみません

割とグダグダしながら会場入り

会場も割とグダグダだったけどホイホイしながら練習
まぁここらへんは逆に企業間イベントが頑張ってるんだよなぁとか思った
ddccとかこどふぇすとかのスタッフさんすごい

  • 英字キーボードヤバすぎて vim を使う気を起させなかった
  • gedit で行こうかなぁとか思ったけど最後何気なく使った eclipse が案外優秀だったので eclipse で行くことに

ごはんを目の前にひたすら待たされる作業
早く食べたかったよー

ホテル
OpenGL の勉強しようかと思ったけどそういえば環境は my PC にはなかったのでスプラをやる
丁度ガチアサリをやっていたのでやったけどなかなか難しいね


C帯で 29 キルするな

本番

8:00 頃に起床 AC
風船飛行機をしぼませるストローをなくして邪魔だったのでストローを買った

本番の動き
僕がログインしてる間にどりきゃすに A 問題, 住建に B 問題を読んでもらった
A は dp らしいので書き書き
B は全探索らしいので書き書き
C はどりきゃすが式を生成していたので書き書き
I は住建が解いてくれたので一部書き書き
G はなんか知らんけど解かれてた
ここまでで 2 時間半で, ここからの 2 時間半は,

  • 僕とどりきゃすが E 問題で適当な貪欲をして意味不明をする
  • 住建が F 問題を解こうとしてなんかダメ

で終了。コンテスト時間 3 時間で良かったよ

11 位でした。10 位からなんかいい感じだったので惜しい

解説
ただでさえわからない競プロ解説を英語でやるとどうなるか…

閉会式

一位114514知ってた
sigmaさんが負けたの辛いみたいなツイートしてたけどそれでも続けてるのすごいなぁとか思った

懇親会

思ったより就活イベントっぽかった
たまに就活イベントとか行ってるんですけど、そこであった人が割りといてビックリ
いい生活とレトリバから景品もらえたのでハッピー
バランスボールはとりあえず家に一週間くらいおいて使ってみたいです
あとは知り合いも新しい知り合いも含めて色んな人と話せたので良かったです

mayoko と競プロ お別れの時

実際のところ, 国内予選で終わりかなぁと思っていたんですが, なぜかアジア予選に通ってしまったのでここまで伸びてしまいました。
競プロは楽しいんですけど, 解けないと面白くないのでちゃんと練習したいんですが, 最近は別の娯楽(switch とかね)をやってるし研究室とか別のことが忙しいので, 全然解けなくて面白くないを錬成しているのでまた時間が取れたら戻ってきます。

戻って来れるのかは分かりませんが・・・・・・・・・・・

まとめ

SHIROBAKO はいいぞ