サイコロの旅のすすめ

TL;DR

18きっぷが余っていたのでサイコロを振って出た目が示す所を目的地とするのを繰り返すサイコロの旅をしました。

サイコロの旅

どこに行くのか決まっている旅もいいですけど、たまにはどこに行くのか分からない旅もいいと思いませんか？ このサイコロの旅ではどこに行くのかはダイスを振って決めます。 予定が直前まで分からないので管理された旅が苦手な方におすすめです。

京都発

本家水曜どうでしょうに合わせて近く4駅,遠い2駅から目的地は万遍なく選びました。 柘植とかが出るとこのあとの発展性があるんですが、今回は関西空港になりました。

関西空港

次の目的地は和歌山になりました。

f:id:CHY72:20190914123010p:plain

関西空港に来ましたが、18きっぷを使うのが目的なので海外には行きませんし、当日飛行機は高価なので飛行機を使うわけでもありません。 その日はイベントもありません。 完全に「大阪から和歌山行きに乗ったが間違えて先頭車両に乗ってしまい関西空港に着いた人」です*1。

周りが飛行機で旅たとうとしているなか、我々は改札で出した18きっぷで再度Uターンします。 まあこういう完全な無駄行動もサイコロの旅の醍醐味ですね。

ちなみにサイコロの出目によっては,関西空港から神戸港のフェリーに乗ったり、すきっぷ2000というお得きっぷを使うレアな機会があったのですが、これらの目は出ませんでした、悲しい〜

和歌山

f:id:CHY72:20190914123544p:plain

徳島が出ました！フェリーか〜〜〜〜〜〜〜〜！

和歌山城・和歌山ラーメンを観光。

知っている人は知っている、和歌山の地酒高垣を売っている酒店です。

www.sankei.com

デレの不思議な縁でできた観光地になっており、前に来たときよりも随分とグッズが増えていました。 こういうところはいいですね。

フェリーに乗るとやたらとこのアニメがプッシュされていました。 「おへんろ。」という四国ローカルアニメらしいです。

どパスコが可愛かったのでツボに入りました。

徳島

f:id:CHY72:20190914123827p:plain

というわけで最終目的地は小歩危(大歩危)になりました。 歩くのが危険と書いていますが、それは昔の話で今は道も整備され電灯もあり、歩くのは容易いです。

2日目

2日目もサイコロを振ると帰れなくなるので普通に大歩危を観光して帰ります。

さいごに

サイコロを振って結果が出るまでどうなるか全然わからないのはかなり楽しいので、旅にちょっとしたスパイスをかけたいかたはぜひサイコロの旅をおすすめします。

おわり

*1:この列車は先頭4車両は関西空港に、残りは和歌山に行くことが多い

nim-lang/Nim に issue を建ててちょっと恥ずかしい思いをした話

TL;DR

  • Nim で C++ の std::set のラッパーを書いた
  • 奇妙なコンパイラのバグを踏んだのでNimにissueを建てた
  • 4年前に建てられていたissue と同様のものだったために close された、恥ずかし〜

はじめに

私は Nim が好きでNimをよく書いています。 最近AtCoderでstd::setを使う問題がよく出題されており、 Nimでも C++ の std::set を使えるようにラッパーを作っていました。

github.com

ところが、これを使用した方からコンパイルエラーが出るという報告をいただきました。

コンパイルエラー

type CSet {.importcpp: "std::set", header: "<set>".} [T] = object
proc cInitSet(T: typedesc): CSet[T] {.importcpp: "std::set<'*1>()", nodecl.}
proc insert[T](self: var CSet[T],x:T) {.importcpp: "#.insert(@)", nodecl.}
proc `==`[T](x,y:CSet[T]):bool{.importcpp: "#==#", nodecl.}
var (S1,S2) = (cInitSet(int),cInitSet(int))
S1.insert 1
if S1 == S2: echo "wrong"
else: echo "correct"

このコードをコンパイルすると、以下のエラーがでて、NimからC++に変換した後のC++のコンパイルに失敗します。

Error: execution of an external compiler program 'clang++ -c  -w  -~/.choosenim/toolchains/nim-0.20.0/lib -I~/codes/nim/ -o ~/.cache/nim/t_d/t.nim.cpp.o ~/.cache/nim/t_d/t.nim.cpp' failed with exit code: 1

~/.cache/nim/t_d/t.nim.cpp:153:7: error: invalid argument type 'TY_89ajMAHL4D29bP2aGRstu1mQ' (aka 'set<long long>') to unary expression
                if (!S1_X5vbOHyI0SI13LVkxEIzEQ==S2_q2YrwwKwgOf4xdemDnRTYA) goto LA4_;
                    ^~~~~~~~~~~~~~~~~~~~~~~~~~
1 error generated.

ほう、という感じですね、

このC++コードの全文は以下です。

N_LIB_PRIVATE N_NIMCALL(void, NimMainModule)(void) {
{
    tyTuple_WVskh7WUQHL0ugdByxngAw T1_;
    nimfr_("t", "/path/to/t.nim");
    nimln_(8, "/path/to/t.nim"); 
    T1_.Field0 = std::set<NI>();
    T1_.Field1 = std::set<NI>();
    S1_X5vbOHyI0SI13LVkxEIzEQ = T1_.Field0;
    S2_q2YrwwKwgOf4xdemDnRTYA = T1_.Field1;
    nimln_(9, "/path/to/t.nim"); 
    S1_X5vbOHyI0SI13LVkxEIzEQ.insert(((NI) 1));
    nimln_(10, "/path/to/t.nim"); 
    {
        if (!S1_X5vbOHyI0SI13LVkxEIzEQ==S2_q2YrwwKwgOf4xdemDnRTYA) goto LA4_;
{       echoBinSafe(TM_earX20ePV9cxitomwdUMS7g_2, 1);
}   }
    goto LA2_;
    LA4_: ;
    {
        nimln_(11, "/path/to/t.nim"); 
        echoBinSafe(TM_earX20ePV9cxitomwdUMS7g_4, 1);
    }
    LA2_: ;
    popFrame();
}
}

このエラーを見ると分かるように、要は if S1 == S2: ... の条件分岐を C++ に翻訳した時に、 if (!S1 == S2 ) goto LA4_; になってしまっているようです。 条件分岐をミスっている様子で、これは正解は if (!(S1 == S2 )) goto LA4_; となるべきですね。

つまり、if A == B: X else: Y をC++に翻訳する際に、 if (!(A == B))Y; else X; となるべきところを、 if (!A == B)Y; else X; としてしまっているわけです。どうして否定が入っているのかはわかりませんが、条件分岐のときにだけコンパイルが失敗するので、最適化か何かの都合で混入したバグなのでしょう。

nim-lang/Nim に issue を建てる

このバグは最新のNim0.20 でも発生します。流石にこれを放っておくわけにもいかないので issue を建ててみます。 勿論、(これはOSSを使うときには今までもよくあることなのですが) すでに issue で議論されていないか確認すべきです。 今回のissueに関連するワード equal function if override の単語で検索し、既に議論されていないか確認します。 無さそうだったので、早速 issue を建てます。

f:id:CHY72:20190913191300p:plain

こんな感じで、Bug Report のissueを建てようとすると、指針としてテンプレートが既に書かれています。便利ですね。 これに従って書いていけばよさそうです。

Think about the title, twice

と初めに書いてあります。タイトルは大事ですからね。 普段技術文書を英語で読むことはよくあるのですが、それに対して英語を書くのはとても苦手なので最低限文法が間違っていないかをgrammarly でチェックします。

そしてこれは戒めなのですが、最低限文法が通っているにしても意味が最低限間違っていないかをチェックするために Google 翻訳に2回かけるやつもやっておくべきでした...(英語→日本語→英語 or 日本語→英語→日本語 をして意味が崩れないかチェックするやつ)

例えば 建てた issue の冒頭、

Overriding equal function causes incorrect behaviour. Nim compiler translates !(a == b) into !a == b and fails to compile.

と拙い英語で書いていたのも、

Overriding an equal function will cause incorrect behavior. Nim compiler converts !(a == b)! to a == b and fails to compile.

になって、なんとなくこっちのほうがいい感じな気がします(非ネイティブ並の感想...)*1。

なんやかんやあって issue を建てました。 github.com

回答が来る

f:id:CHY72:20190913192953p:plain

要は # == # (#は出てきた順にその番目の引数を表す) ではなくて、 (# == #) と定義してくれとのこと。なるほど *2。 Low Priority のタグが付きます。

実は duplicate issue だった

f:id:CHY72:20190913193456p:plain

その後、これは duplicate issue だよ、と指摘されます。あちゃ〜やっちまった〜〜。 そういうわけで4年前に建てられたissueと同一の内容であったので close されました。 Low Priority なので 4年間放置されていたバグであっても仕方がないですね。

恥ずかし〜〜〜〜〜〜〜〜〜〜

どうすれば duplicate issue を回避できたか、 equal function if override で検索したのに加えて C++ compile error でも検索する、もしくは Label:C++ codegen を探しておく、が正解だったっぽいですね。

う〜 。

未来永劫 duplicate issue を建てた者としてnim-lang/Nimに記録が残るのはちょっと悲しいですね〜〜〜。

総計 12028 件の Nimのissueのうち duplicate を含む issue は たった 502 件 しかなくてそのうちの一つになっちゃったな〜〜〜〜。

うひ〜〜〜。

あ〜〜〜〜〜〜〜〜。

おわり。

*1:というか function って可算名詞ですね。

*2: ちなみに、Nimの流儀として全ての二項演算をこのように (#+# ではなく (#+#) と書く) 定義するといった指針はありませんのでこれは特殊な書き方と言えます。

パスワード を 平文 で保存していませんか？？？パスワードの最強の保存方法「Piet埋め込み」について調べてみました！

こんにちはwwwwww！！！！

暑い日が続きますねwwwwwww！

突然ですが、あなたはパスワードをどうやって保存していますか？？？

平文のままテキストファイルに保存していますか？

それとも適当なハッシュ関数でハッシュ化してそのハッシュをテキストファイルに保存したりしていませんか？？？

実はそれ、 とっても危険な保存方法 なんです！！！！！！！！

テキストファイルに怪しい文字が書いてあった場合、どんなに強いハッシュ関数でも賢い人達が衝突させてしまう可能性があります！！！！！！！！

大変ですよね！！！

一体どうすればいいんでしょう？？？？？？？？？

Piet

テキストファイルに怪しい文字を保存するのは危険 ですよね！！！！

なので、実はパスワードは画像に埋め込むべきなんです！！！！！！！！！！！

ここではオススメの埋め込み方法として、Piet にパスワードを埋め込む方法 を解説します！！！！！！！

f:id:CHY72:20190911175649p:plain

(元画像は 東方32×32打ち直しシリーズまとめ！ - えるるのだいあり ～Season2～ よりお借りしています！！！ )

この画像は何の変哲もない32x32のフランちゃんのドット絵ですよね！！！！！！！！！

でも、この画像はなんとPiet として実行できる んです！！！！！！！！！！

実際にこの画像を(npietなどで)実行すると 「PietPiet」と表示されるんです！！！！！！！！！！

この「Piet埋め込み」 の方法を使えば安全にパスワードを保存できますね！！！！！！！

さらにさらに、僕は頑張ったので 好きな文字を好きなドット絵に、なるべく原型を保ったまま最良優先探索をしてPietとして埋め込むプログラムが既に存在してるんです！！！！！！！

f:id:CHY72:20190911180316p:plain

すぐに使える実装コードはこちら！

github.com

この「Piet埋め込み」 の方法を使えば安全にパスワードを保存できますね！！！！！！！

さいごに

いかがでしたか？？

もしパスワードを平文やテキストのまま保存していた場合はこの記事のようにパスワードをPiet化して保存したほうがいいかもしれませんね！

この記事が役に立ったら欲しい物リストのものを買って下さい！

https://amzn.asia/4n4xnzC

ISUCON9で予選通過したのでbcryptについて書く

はじめに

ISUCON9の本戦出場が決まりました. 今年から学生枠が無くなったためかなり厳しい状況になるな〜と思っていましたが、チームメンバーのおかげで通過できました.

リポジトリはこちら

私のチーム(百万円ドブリン)の状況は@nakario のブログ に詳しく書いてあるのでそちらをご参照ください. 私がしたことはbcryptをいじっていただけだったのでチームメンバーの力が如何に素晴らしいかがわかります。

bcrypt 改善について

実は去年の本戦でもbcryptが出題されていました。 GoアプリのCPUフレームグラフを見るとbcryptの処理が支配的になるのですが、 その時はGoアプリのCPUはネックになっていないため、そこをどんなに改善してもスコアが上がらない、という構成でした。 昨年はここを改善しようとして沼にハマって大敗しました。 詳しくは isucon8本戦は低レイヤーがネックにならない良問だった - (/^^)/⌒●~*$ a(){ a|a& };a を読んでいただければ。

うって変わって今年の bcrypt はかなり強めの主張をしてきました。 アプリをチューニングしていくと頻繁に login 処理が入るようになり、bcryptの処理が支配的かつCPUを大量に消費するようになります。

f:id:CHY72:20190911145737p:plain

これの直し方は以下の2つがあります。

  1. こちらが持っているハッシュ化済みのパスワードからもとのパスワードは推測できないので、ベンチマーカーからのログインを盗聴してハッシュアルゴリズムを変更し、徐々にコスト10のbcryptを取り除いていく。
  2. 本質的に改善不可能な処理なので、ログイン専用サーバーを構築し、処理を分散させる。

私は最初は1の方法を取ったのですが、実はログインはそんなに成功しないことが分かりました。 そのため試算の結果では数十回ベンチを回す必要がありそうでした*1。 加えてこの盗聴作業は楽しくなかったため、我々のチームはログイン専用サーバーを構築することにしました。 Nginxでどうやるんだったけ...とぼーっとしていたら aokabi がシュッと実装してくれました。

f:id:CHY72:20190911151158p:plain

17時前、複数台にした途端点数が跳ね上がりました。やったぜ。aokabi最高！ 勝利！ もちろんbcryptが支配的になるまでチューニングしてくれたnakarioも最高！ 優勝！

Go の bcrypt は遅い？

本戦終了後、twitterを見ていると 「Goのbcryptは遅い」という主張がたまに目につくようになります。 これは例えばPythonのbcryptは(Pythonそのままでbcryptすると遅すぎるので)内部的にC言語で書かれており、 そのためGoのbcryptとくらべて速いのでは、という主張です。 一理あったのでGo/Python/Rubyの3バージョンで雑に計測してみます*2。

コードはこちら

結果、Go実装は15秒,Python実装は14秒,Ruby実装は13秒でした。Go実装はちょっとだけ遅いものの、そこまで差は無いように見えます*3*4。 どの言語を選んでもbcryptと向き合う必要がありそうです。

最後に

感想戦をする時に盗聴をしなくてもbcryptを完全に排除できるように、 全ユーザーの生パスワードを抽出したjsonファイルを作りました！お使い下さい！

今回こそは１００万円を取るぞ！

*1:bcryptをほぼ完全に取り除く場合,実際はもっと少なくても効果はでうる

*2:@手元のMac(core i5 / RAM8GB)でgo 1.11.5 / python3.7.4 / ruby 2.3.7

*3:PythonについてはCの最適化がなされていない可能性を考慮し、手動でCソースをO2/O3をつけてビルドしたPython非経由の実装も試してみましたが結果は同じでした

*4:もちろん、環境によっては特別な最適化がなされて速度が変わる可能性はあります

AtCoderで青になるまでにやったこと

チームで制作しているゲームのミーティング(だいたい土曜日九時から)をサボってAtCoderに出るという行為を毎週続けていた結果、無事青になれました！

ごめんね！もう満足したから！

NimでAtCoder Beginners Selectionを解いてみた！

はじめに

昔にNimの競プロ記事を書いていたのですが、今改めてNimで競プロを始めるならやっぱりAtCoder Beginners Selectionの解説があった方が便利だよなーと思ったので 、マイナー言語Nimを普及させるために解いた記事を書いておきます。 Nimをご存じない方は、この記事を読んで、書きやすそうだなと思ってもらえれば幸いです。

僕のNimの競プロライブラリはこちらにあります。

古いAtCoder用Nim0.13.0のドキュメントやビルド情報はこちらにまとめてあります。

最新のNimの場合は こういう感じで コードの内部実装が手軽に読めるという特徴があります。

また、訳あって入力のとり方はやや非自明な取り方をしていますが、これは自分に合うものを使用してください。

入力のとり方について補足

入力が

n
A1 A2 A3 ... An
B1
B2
...
Bn

とあった時に通常は以下のように書くことが多いです。

let n = stdin.readLine.parseInt()
let A = stdin.readline().split().map(parseInt) # 一行の中で空白で分割して取る
let B = newSeqWith(n,stdin.readLine().parseInt()) # 行ごとに取る

この書き方では、場合に応じて２つの書き方を使い分けないといけない欠点があります。 長いしややこしいですよね。

なので最近ではC言語のscanfを使ってこう書いています。

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan())
let B = newSeqWith(n,scan())

意味が明確かつ簡略になって、かなり見やすくなりました！ 便利！

1 Product

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
if (scan() * scan()) mod 2 == 0 : echo "Even"
else:echo "Odd"

ちなみに scan() なしだと let tmp = stdin.readLine.split().map(parseInt);let a = tmp[0];let b = tmp[1] と書かないといけなくてつらいです。

2 Placing Marbles

import sequtils
echo stdin.readLine().filterIt(it=='1').len

配列の操作には なんとかit が便利です。 Nimは fun(a,b,c) を a.fun(b,c) と書ける(UFCS)のでメソッドチェイン的なことができて便利です。

あとは getchar を使う解法もあります。

proc getchar():char {. importc:"getchar",header: "<stdio.h>",discardable .}
echo newSeqWith(3,getchar()).filterIt(it=='1').len

3 Shift only

import sequtils
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var A = newSeqWith(n,scan())
var ans = 0
while A.allIt(it mod 2 == 0):
  A = A.mapIt(it div 2)
  ans += 1
echo ans

allIt などの便利な なんとかIt を使っていきましょう。 定数への代入は let 、変数への代入には var を使います。

while A.all(proc(x:int):bool = x mod 2 == 0):
  A = A.map(proc (x:int):int = x div 2)

のように関数を作成して書いてもOKです。

また、 import future (最新のNimでは import sugar) をすると

while A.all(x => x mod 2 == 0):
  A = A.map(x => x div 2)

みたいな感じにも書けます。 なんとか It は 言語機能にあるわけではなく、配列を操作するタイプで個別に実装しているだけなので、 こういうラムダ式形式の書き方も応用性は広く覚えておいて損はないです。

4 Coins

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let a = scan()
let b = scan()
let c = scan()
let x = scan()
var ans = 0
for ia in 0..a:
  for ib in 0..b:
    for ic in 0..c:
      if 500 * ia + 100 * ib + 50 * ic == x : ans += 1
echo ans

forループは for i in 0..n で n を含み、 for i in 0..<n で n を含まない意味でループを回せます。

5 Some Sums

import sequtils,math
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let a = scan()
let b = scan()
var ans = 0
for i in 1..n:
  let isum = ($i).mapIt(it.ord - '0'.ord).sum()
  if a <= isum and isum <= b: ans += i
echo ans

数字の文字列化は $ 演算子を使います。 文字コードの数値を取得するには ord を使います。

6 Card Game for Two

import sequtils,algorithm
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan()).sortedByIt(-it)
var alice = 0
var bob = 0
for i,a in A:
  if i mod 2 == 0 : alice += a
  else : bob += a
echo abs(alice - bob)

import algorithm の後、 破壊的にソートする場合は sort() が、新たに作成する場合は sorted が使えます。 今回の場合は、ソートのキーを指定する .sortedByIt(-it) の他に、通常のソート .sorted(cmp,Descending) と書くのもありです。 for a in A ではなく for i,a in A と書くことで、 i に配列のindex を取得することができ、便利なことが多いです。

7 Kagami Mochi

import sequtils,tables
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
echo newSeqWith(n,scan()).toCountTable().len

古いNim 0.13.0では deduplicate がO(N2) かかるので注意が必要です。 最新のではソート済み情報を渡せるので大丈夫ですが。

8 Otoshidama

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let y = scan()
for ia in 0..n:
  for ib in 0..(n-ia):
    let ic = n - ia - ib
    if ic >= 0 and ia * 10000 + ib * 5000 + ic * 1000 == y :
      echo ia," ",ib," ",ic
      quit 0
echo "-1 -1 -1"

proc 内ではないためreturn が書けないのですが、実は quit 0 でプログラムを終了できます。

9 Daydream

import strutils
var S = stdin.readLine()
proc check():bool =
  for word in ["dreamer","eraser","erase","dream"]:
    if S.endsWith(word):
      S = S[0..^(word.len+1)]
      return true
  return false
while S.len > 0:
  if not check(): quit "NO",0
echo "YES"

Nim は文字列操作も割と得意です。

10 Traveling

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var (ct,cx,cy) = (0,0,0)
for _ in 0..<n:
  let (t,x,y) = (scan(),scan(),scan())
  let (dt,dx,dy) = (t-ct,x-cx,y-cy)
  if dx.abs + dy.abs > dt or abs(dx + dy) mod 2 != dt mod 2: quit "No",0
  (ct,cx,cy) = (t,x,y)
echo "Yes"

Nimはタプルの分割代入が可能なため、必要に応じて使っていきましょう。

最後に

Nimはマイナー言語ですが、AtCoderでも毎回片手では数えられない程度の人数がNimで解いて提出しています！ 書きやすくて速い最高の言語であるNimの使用者が増えてくれるといいな〜〜〜

就活をしてしまっていました...

最初のころのぼく

就活を終えたぼく

いかがでしたか？

入る会社では多分飲酒コーディングはできないと思いますが、規定を読んだ限りでは業務中に飲酒をしてはいけないとは明文化されていなかったので可能性はあるかもしれませんね！

ちなみに僕はほろ酔いで真っ赤になります！！！！！！！！！！！！！！