天才クールスレンダー美少女になりたい

チラシの表(なぜなら私はチラシの表にも印刷の上からメモを書くため)

TSG LIVE! 6 Day1 ライブコードゴルフ大会 writeup + 参加記

TL;DR

コードゴルフ陣取り合戦に出場し3-8で勝ちました。

youtu.be

この動画の3:39:40頃から。たぶんそのうちコードゴルフ部分だけ切り出した動画が上がるはず。



writeup + 想定解勝手に解説

問題

入力: 0以上4以下の数字を4つ並べた文字列が32個、改行区切りで与えられる。入力の最後には改行が付与される。
出力: 各行について0123, 1230, 2301, 3012のいずれかであれば1、3210, 0321, 1032, 2103のいずれかであれば0を出力せよ。出力された文字列に含まれる空白文字(改行含む)は無視される。

全体方針

まず、私はesolangが全く書けない。本当に書けない。
というわけで、とりあえず普通の言語を集中的に狙う。

アルゴリズムいろいろ

sを文字列/数字の列とする。

  • (s[0]-s[1])&2/2を出力
  • sを2回繰り返して、その中に"01"が入っているかどうか
  • sに01または12が入っているかどうか

……いろいろって言ったけど3種類しかないな。しかも最後の3つ目は思い付いたのがギリギリだった上に、これを適用して短縮できる言語の存在に気付けなかった。かなりアレ。

数値として読み込んで計算する方法も考えたけど、うまいこと0123, 1230, 2301, 3012と3210, 0321, 1032, 2103を振り分けられるような条件式を思い付かなかったし、そういう条件を探索するコードを書く余裕もなかったので……(先に用意しておけという話だが……)


これは想定解に使われているアルゴリズム

  • x%217%2
  • (x+1)%8/4

確かにこれでいけるな……天才か???????

各言語について

Ruby 3.0

29バイト。改行を落として2回繰り返して"01"が含まれているかチェックする。

$<.map{p _1.chop*2=~/01/?1:0}

冷静に考えると"01"か"12"をチェックする方が改行を削除する必要がない分短い。

# 後で思い付いた短縮コード 25バイト
$<.map{p _1=~/01|12/?1:0}

ちなみに↓が想定解らしい。23バイト。アルゴリズム(x+1)%8/4

$<.map{p -~_1.to_i%8/4}

そっか〜〜〜単項マイナスとビット反転の優先度が剰余演算子より高いのを利用してるんですね〜〜〜〜
-~の存在は知ってたけど(逆の~-も)そうやって使うんか〜〜〜

Node.js
(""+require('fs').readFileSync(0)).split`
`.map(a=>a>"!"&&console.log(+/01/.test(a+a)))

01|12方針でやった場合、""+の部分を5+などに変えられる。これをすると1行目の1文字目に"5"が挿入されるが、行を繰り返さないので問題ない。ただし後の部分が1文字増えるので結局変わらない。

(5+require('fs').readFileSync(0)).split`
`.map(a=>a>"!"&&console.log(+/01|12/.test(a)))

想定解は以下らしい。73バイト。

(0+require("fs").readFileSync(0)).replace(/\d+/g,v=>console.log(v%217%2))

なるほど、改行でsplitするのではなく、数字の列をゲットしてきてそれぞれに関数を実行させるのをreplaceの第二引数でやってるのか……そしてvは文字列だがv%217の時点で勝手に数値に変換される、と……

確かに、文字列から勝手に数値に変換される上に最後の改行(split後は空文字列)の扱いが面倒なJavaScriptにぴったりな方法や……これなら初めから空文字列なんて気にする必要ないんやもん……



ちぃ、覚えた。次は負けへん。1つ1つの敗北を噛み締めてコードゴルファーは成長していくんや。

(追記: 元の想定解は(""+だったんですが(0+の方が短いということに気付いてしまった。初めに0がついても数値に変換すると消えるため)

Bash(busybox)

35バイト。

awk '{print match($0 $0,/01/)?1:0}'

特にコメントすることはないです。

想定解は以下。18バイト。

awk '1,$0=$1$1~23'

$0=$1$1~23はわかる。$1を2回繰り返して23とマッチするか試し、その結果(1か0)を$0に代入する、と。ここで23じゃなくて01にすると1という意味になってヤバい。/01/ならともかく。
そういやawkって何もしなかったら$0を出力するんだったっけ?

なので、以下のコードがうまくいくのはわかる。match関数も~でいいし、なんならこいつが1と0返すから三項演算子もいらんかったってことか……

awk '{print $1$1~23}'

で、初めの1,がわからん……解説スライド曰く「$0の中身を必ず出力するのに必要な設定」らしいけど……

これはawk/sed完全理解目指さないとダメですね……sedもだけどawkもマジで騙し騙ししか書けん……

C(GCC)

76バイト。

main(i){for(;i++<33;){char s[5];scanf("%s",s);puts((s[1]-s[0])&2?"0":"1");}}

この方針で後で短縮したものがこれ。58バイト。たぶん動くはず。getsは最後改行の後に読むものがなくなるとヌルポ返すので。

char s[5];main(){for(;gets(s);)puts(s[1]-s[0]&2?"0":"1");}


想定解は以下。43バイト。

main(a){for(;gets(&a);)putchar(49-a%21/9);}

………………………は〜〜〜〜〜〜〜


文字列をリトルエンディアンのintとして無理に解釈させるやつ、実は私も1回コードゴルフ大会でWebAssembly手書きしたときやったことあるんですよね……そっかあ……

Python3

Pythonマジでわからん。Rubyの1/INF倍しかわからん。48バイト。

[print(+("01" in input()*2)) for i in range(32)]

冷静に考えると同じ方針でもさらに短縮できるな……
代入式最高! 一番好きなPython3の言語仕様です(コードゴルファー的に)

while s:=input():print(+("01" in s*2))

これで38バイト。


ちなみに想定解はこれ。33バイト。

while 1:print(int(input())%217%2)

調べてみた(というか実際に確認してみた)ところ、確かにinput()はEOFError吐いて落ちる。賢いなあ……
(追記: この記事を初めて書いたときは「最終的にinput()が空文字列返して、それをintに変換するとエラーで落ちる」と思っていましたが、違いました)

反省会総括

なんというか、とにかく集中しすぎてて、アルゴリズムを考えるところから細かい短縮をするとこまで全部自分でやってしまったせいでチーム戦というメリットをいまいち活用できなかった気がする……2日目はもっとコミュニケーションを取っていきたい……

あと、esolangに一切手をつけられなかったのはアレだったかな……とはいえ汎用5言語相手にするので精一杯だったから仕方ないといえば仕方ない気もするけど……
九マイルは遠すぎる。75分は短すぎる。

ライブ中の解自力解想定解
Ruby 3.0292523
Python3483833
Bash(busybox)353518
Node.js878773
C(GCC)765843

まあ、アレですね。今後も精進します……



涙の数だけ強くなれるよ アスファルトに咲く花のように


参加記(時系列)

ゴルファー的に有意義な情報は全部上に書いたので、こっからは私の思考を追体験したい人、あるいは臨場感が欲しい人だけ読めばいいと思う。

待機

ドキドキしながら待つ。余計なことが起こらないよう必要ないウィンドウは閉じ、メインディスプレイ(画面共有してる)は特に片付けておく。

ちなみに、デスクトップパソコンはWindowsだが、あまりにWindowsが苦手すぎて、困る……ウィンドウの切り替えも全然スムーズにできないし(たぶん私が悪い)、普段Macならちょちょいとターミナルに打ち込んでワンライナーで済ませるようなことも、Windowsだとまともにできない。仕方がないので手元のmacbook airで言語仕様検証を済ませ本格的なコーディングはコードテストでやることにした。明日までにWSL準備しとくか……?

競技開始、問題読解

13時33分、競技が始まったので問題を読む。

季節が巡る向きを判定せよ

問題文冒頭からめちゃくちゃエモワードだが、そんなことに気を取られている余裕がなく、というか冒頭のとこは問題の本質でないため読み飛ばしててエモに気付きようがなかった。

昆布くんの趣味は時間旅行ですが、気まぐれに旅をするので、いつも自分が未来へ進んでいるのか過去へ遡っているのか分からなくなってしまいます。 しかし、昆布くんはとても風流なので、四季の訪れを正確に感じとることができます。昆布くんは春が訪れたら0を、夏なら1を、秋なら2を、冬なら3をメモします。 4つの季節を体験した時点で、昆布くんはメモを見て自分が向かっている方向が未来なのか過去なのかを判断します。 例えば春、夏、秋、冬の順に体験した場合、メモには0123と書かれ、未来へ進んでいると判断できます。

昆布くんは32回旅行しました。それぞれのメモが与えられるので、昆布くんが未来に進んでいるときは1を、過去に遡っているときは0を出力してください。



入力: 0以上4以下の数字を4つ並べた文字列が32個、改行区切りで与えられる。入力の最後には改行が付与される。
出力: 各行について0123, 1230, 2301, 3012のいずれかであれば1、3210, 0321, 1032, 2103のいずれかであれば0を出力せよ。出力された文字列に含まれる空白文字(改行含む)は無視される。


焦りのせいか題意が掴めない。ヤバい。とりあえず落ち着いて何度か読む。ようやく出力セクションが本質であることがわかってきた。時間に追われる大会が苦手と申します……

[AC] 3分44秒 bash(busybox) 69バイト

とりあえず「0123, 1230, 2301, 3012なら1を、3210, 0321, 1032, 2103なら0を出力すればいい」ということが分かったので、脳死sedbash(busybox)を通す。

sed -e 's/0123\|1230\|2301\|3012/1/' -e 's/3210\|0321\|1032\|2103/0/'

[WA] 13分38秒 Node.js 83バイト

ちょっと考察する。

冷静に考えると、入力は4文字取らなくても初めの2文字だけで判別できる。そこで、1文字目-2文字目を考えてみる。これが-1か3であれば1を、1か-3だったら0を出力すればいい。

とりあえずNode.jsを攻めてみることにする。

JavaScriptって文字列を引き算したらどうなるっけ……と思い手元のmacで試してみると、"0"-"1"は-1になった。自動的に数値に変換されて計算されるらしい。これなら数値に変換する必要はない。

さらに、-1, 3, 1, -3をbitで表記してみると、順に111...111、000...011、000...001、111...101となる。-1と3は下から2桁目が1、1と-3は0になっている。つまり、&2をすることで前者を2、後者を0にすることができる。さらに2で割った値を出力すればいい。

(""+require('fs').readFileSync(0)).split`
`.map(a=>console.log(((a[0]-a[1])&2)>>1))

冷静に考えたら>>ではなく/を使えばいい。こいつ馬鹿か?


そしてこいつはWAした。

[AC] 16分39秒 Node.js 92バイト

……冷静に考えると、入力の最後には改行がある。そしてこいつのせいでsplitした配列の33番目には空文字列が入っていて、こいつが結果的に0を出力する。

普通の言語ならnilなりnullなりundefinedを引き算すれば、あるいはゼロ除算すればエラーになって落ちてくれるのに、こいつには浮動小数点しかないせいでNaNとかINFとかいうものが発生して処理が続行されてしまう。そして後で知ったのだが、NaN&2は0らしい。は?????


とりあえず、経験上「最後の改行でエラーを吐かせて処理系を落とす」という手はJavaScriptじゃまず使えない。どうにかして改行はスキップさせなければならない。
応急処置としてmapの第二引数のインデックスを使って33番目の処理をスキップさせる。

(""+require('fs').readFileSync(0)).split`
`.map((a,i)=>i<32&&console.log(((a[0]-a[1])&2)/2))

92バイト。長いけど、出さないよりはいい。ちなみに後で気付いたことだが、ビットANDより引き算の方が優先度高いので、(a[0]-a[1]&2)/2でいい。


次は……RubyistらしくRubyに手を出そうかなあ。

[AC] 27分46秒 Ruby3.0 57バイト

迷走しまくった。


Rubyは私の母語みたいなものだ。人生で2番目に触った言語であり(1番目はJavaScript)、間違いなく仕様を一番詳しく理解している言語でもある。言語の根本的なデザインをちゃんと理解しているから「え、この書き方できないの?」とかまごつくこともないし、標準ライブラリもけっこう把握している。言語自体もめちゃくちゃ自由度が高いし、私もそこそこ「流暢に」書ける。


それゆえに、こういう問題を普通に出されたら数分で書ける。
行ごとの文字列のまま扱う? バイトに変換する? 1文字ずつ読み込む? 数値に変換する?
どれでもいい。どの方針でもすぐ書ける。なんとでも書ける。


しかし、その自由度の高さが短期決戦のコードゴルフでは仇になる。どの方針で書けば短くなるだろう?
この問題自体のアルゴリズムだっていろいろ考えられる。どれを選ぶべきだろう?


少し悩んだ後、盤面を見た。661nos氏がC(GCC)を通していた。そのコードの方針はs[1]-s[0]==1||s[2]-s[1]==1。まあ確かにそれでも解けるな。

それを見た結果、脳死Rubyコードができた。57バイト。

$<.map(&:bytes).each{|a|p a[0]-a[1]==1||a[1]-a[2]==1?0:1}

かなり馬鹿コード。文字列同士の引き算ができないからバイト列に直したのだろうけど、それをやるならさっきの((a[0]-a[1])&2)/2をした方が短かった。しかもeachはmapにした方がいいし、というかmapしてmapするの文字数の無駄だからまとめた方がいいし、なんかマジで錯乱してたんだな、このときの私。

# 参考コード
# 36バイト
$<.map{a=_1.bytes;p (a[0]-a[1]&2)/2}

[WA] 31分43秒 Ruby3.0 24バイト

その後1分か2分くらい(ひょっとしたら数十秒かもしれない)考えて、ふと「1行を2回繰り返して"01"が出てくるかチェックすればよくね?」という天啓を得た。ささっとその方針で書く。前の提出の直後に別方針の超シンプルなやつ降ってきたの、アイデアの女神は気まぐれってことかなあ。

$<.map{p _1*2=~/01/?1:0}

WAした。

[AC] 32分48秒 Ruby3.0 29バイト

$<.map{p _1.chop*2=~/01/?1:0}

改行の存在忘れてた。String#chopで改行を落としてから2回繰り返し01が含まれるか調べる。


結果的にこれが今回のRubyの最短コードになったが、実際にはもうちょい短くなるよね……

[WA] 36分31秒 Node.js 80バイト

さっきの「2回繰り返して01が含まれるか調べる」方針。

(""+require('fs').readFileSync(0)).split`
`.map(a=>console.log(+/01/.test(a+a)))

無意識で単項+によるtrue/falseから1/0への変換を使ってた。使った記憶全然ないんだけど。集中しすぎてゾーン入ってたんか?

WAした。アーッ33番目の改行!

[AC] 45分16秒 Node.js 87バイト

(""+require('fs').readFileSync(0)).split`
`.map(a=>a>"!"&&console.log(+/01/.test(a+a)))

……なんでこれ提出するのに8分かかってるの?

JavaScriptの文字列比較は辞書順なので、0よりも順番が早い1文字と比較すれば空文字列<1文字<数値となる。ASCIIコードを見ると"!"が0より早かったので採用。

[AC] 49分52秒 C(GCC) 80バイト

そろそろCを短縮してみようと思い、661nos氏のCのコードを眺める。

// 元コード
i;int main(){for(;i++<32;){char s[5];scanf("%s",s);if(s[1]-s[0]==1||s[2]-s[1]==1)puts("1");else puts("0");}}

iを引数に移動、((a[0]-a[1])&2)/2メソッドを適用、三項演算子を適用。この環境だとiの初期値は1なので32を33にずらす。

int main(i){for(;i++<33;){char s[5];scanf("%s",s);puts((s[1]-s[0])&2?"0":"1");}}

[AC] 54分11秒 C(GCC) 76バイト

初めのint消すの忘れてた。

main(i){for(;i++<33;){char s[5];scanf("%s",s);puts((s[1]-s[0])&2?"0":"1");}}

まあ、実際はもっと縮むのだが、このときはそこまで頭回らなかった。

[AC] 64分20秒 Python3 48バイト

C言語のmainの第二引数(文字列か何かだったはず)をsにできないかしばらく考えたけど、C言語なんもわからなくてできなかった。ポインタってなんだっけ、配列ってなんだっけ、型が合わないんだけど……

気分転換にPython3をする。これも既に661nos氏のコードがあった。その中でfor i in range(32):とあったので、なんとなくそれを使うことにした。

[print(+("01" in input()*2)) for i in range(32)]

これも当然もっと縮む。

[AC] 70分8秒 Bash(busybox) 35バイト

awk '{print match($0 $0,/01/)?1:0}'

同じ方針でawkで書いた。後で「$0が01または12を含む」という方針も思い付いたが、文字数は同じだった。

awk '{print match($0,/01|12/)?1:0}'

タイムアップ

おしまい。なんか結果的にはめちゃくちゃ圧勝してしまった。学ぶべきところは学んで次につなげたい。
次というか、明日さっそくKMCの人とバトルするんだけど。