TL;DR
TSG LIVE! 6の2日目のコードゴルフ大会に出場しました。TSGとKMC(京大マイコンクラブ)で勝負し11-6で勝ちました。
TSG側のプレイヤーは私、しとお先生(https://twitter.com/sitositositoo)、昆布さん(https://twitter.com/u6606u5e03)。KMC側のプレイヤーはDNEKさん(https://twitter.com/dnek_)、aotsukiさん(https://twitter.com/RikuAotsuki)、ten986さん(https://twitter.com/ten986)。
しとお先生だけ「先生」呼びなのに他意はありません。マジでないよ。
コードゴルフはこれの2時間08分40秒頃から。
コードゴルフが本当に楽しすぎてコードゴルフジャンキーになりつつある今日この頃。次のゴルフ問題はまだですか?????????
AtCoderに問題が無数にある、それはそう。
この記事は分量がかなりヤバいので、目次をうまいこと活用して飛ばし読みするのが吉。
writeup + 各言語勝手に解説
ライブで使われた解説スライドはこちら。やっぱesolang面白いけどなんもわからんな……
せっかくなので、KMCとTSGの双方から提出された言語は全部載せて、解説できるところは解説してみた。
問題
- to と kyo をそれぞれ10個ずつランダムに並べた50文字の文字列が与えられる。入力の最後には改行が付与される。
- tokyoの数を数えてt/Tをその数だけ出力するか、kyotoの数を数えてk/Kをその数だけ出力する。大文字小文字は混ざっててもいい。
全体方針
とりあえず汎用言語を取る。esolangは後で考える。
たぶんチームメイトも同じ感じだったと思う。
アルゴリズム
- "tok"の数だけt/Tを出力("yot"の数だけk/Kを出力してもいい)
- "tok"をTに置換、さらにT以外を削除("yot"をKに置換、K以外を削除)
ありえる並べ方は"toto"と"kyokyo"と"tokyo"と"kyoto"の4種類で、tokを含むのはtokyoだけ、yotを含むのはkyotoだけ。
……私はマジでこれだけしかやってない。他のesolang書いてた人は別の方法もいろいろ考えてたのかもしれないけど……
各言語について
Ruby 3.0
書いたのは28バイト。
$><<?T*gets.scan("tok").size
想定解は24バイト。
puts gets.scan /t(?=ok)/ # 参考: kyoto 25バイト puts gets.scan /k(?=yot)/
ヴェアアアアアアアアアア
正規表現の先読み完全に忘れてた……そうか、tを自分で用意せず"tokyo"のtだけ抜き出す方が短いんだな……馬鹿……
(解説スライドのコードはscanの括弧が外れてなかったので1バイト長くなっています これを後から発見したのはwriterの人で私じゃないです)
Node.js
書いたのは69バイト。まあ大半は昆布さんが書いたんですが……
(0+require('fs').readFileSync(0)).replace(/tok/g,a=>console.log("T"))
想定解は67バイト。
console.log(...(0+require("fs").readFileSync(0)).match(/t(?=ok)/g)) // 参考: kyoto 68バイト console.log(...(0+require("fs").readFileSync(0)).match(/k(?=yot)/g))
ぐえ〜先読み〜〜(スライドでは初めが""になっていたが、ここを0に置き換えると1バイト縮む。0が文字列の先頭についても影響がない)
Bash(busybox)
書いたのはこれ。29バイト。
sed -e s/tok/T/g -e s/[^T]//g
想定解はこれ。25バイト。
# tokyo sed 's/tok/T/g;s/[^T]//g' # kyoto sed 's/yot/K/g;s/[^K]//g'
ぎゃー、sedって複数の条件をセミコロンで連結できたんだ……
ちなみに解説スライドのコード(元々想定されてた解法)では"^T"が"a-z"になってた。"^T"(T以外にマッチする文字を意味する)にすると1バイト縮む。
C(GCC)
書いたのはこれ。75バイト。
char* p;char s[55];main(){for(p=s,gets(s);p=strstr(p,"tok");p++)puts("T");}
strstr関数は「文字列1から文字列2を探しそのアドレスを返す。発見できなければNULLポインターを返す」というやつ。
forの初期化で文字列を読み、条件判定でstrstrの結果をpに代入し("tok"がもう存在しない場合ヌルポが返ってくるのでfalse扱いとなりループを抜けられる)、pが次の"tok"の開始位置を指しているので更新部分でポインタを1つ進めてやる。すると文字列pは"ok..."となるので次のループでその先の"tok"を探してくれる。
for文とC言語のポインタや文字列の仕様を余すところなく利用したコードなので「うまく書いたった」という満足感はけっこうある。ただ変数宣言で長くなってしまった。intなら型宣言いらないんだけどな……
後で冷静に考えたところ、pは宣言時に初期化できることに気付いた。アホか?
これで73バイト。
char s[55];char* p=s;main(){for(gets(s);p=strstr(p,"tok");p++)puts("T");}
解説スライドに載っていた想定解は以下。57バイト。
// tokyo a,b;main(c){for(;c=getchar()&5;a=b,b=c)a-c-3||puts("T");} // kyoto a,b;main(c){for(;c=getchar()&5;a=b,b=c)c-a-3||puts("K");}
こりゃえっらいテクニカルなコードやな……
aが読んだ文字の2文字前、bが1文字前、cが読んだ文字を保持している。最後のa=b,b=cで1文字進めることになる。
ただし、ただgetcharするのではなく、それを&5したものを保持している。以下の表の通り、改行を読み込むとこの部分が0になるためループを抜けられる。
| 文字 | ASCIIコード | ASCIIコード(2進法) | (ASCIIコード)&5 |
|---|---|---|---|
| t | 116 | 1110100 | 4 |
| o | 111 | 1101111 | 5 |
| k | 107 | 1101011 | 1 |
| y | 121 | 1111001 | 1 |
| 改行 | 10 | 0001010 | 0 |
a-c-3||puts("T")というのは要はa-cが3ならTを出力ということだ。上の表を参照すれば分かるが、a=4,c=1のときのみTが出力される、つまり直前に読んだ3文字が/t?k/または/t?y/のときTが出力されるということ。/t?k/という並びはto/kyoの列において"tok"しか存在しえないし、/t?y/という並びはそもそも存在しえない。つまり"tok"の個数だけTが出力されることになる。"tok"は"tokyo"の中にしか出現しないので、これでいい。
kyotoの方はc-a-3||puts("K")になっているが、これはa=1,c=4すなわち/k?t/か/y?t/のときKが出力されるという意味で、これは要は"yot"のことである。やってることは同じだね。
…………いや、理解はできるけどさ……できるけど、&5で1文字目と3文字目の差が3って、いったい何食べたら思い付くん? 天才?
ちなみに、getcharでEOFしたら定数のEOF(普通-1)が返ってくる。
……あれ、これ実はEOF利用したらもっと短くなったりしない?
// tokyo a,b;main(c){for(;c=~getchar();a=b,b=c)a-c+9||puts("T");} //kyoto a,b;main(c){for(;c=~getchar();a=b,b=c)a-c+5||puts("K");}
……なった。56バイト。
ビット反転でEOF(-1)を0にしてループから抜ける。そしてビット反転しても差は保持されるので、「差が5」("y*t")か「差が9」("t*k")のときa-c+9/a-c+5が0になり、ORでputsを実行する。
最後に"y*\n"か"t*\n"になることもあるが、これも\nが10で英数字からめちゃくちゃ離れてるので差が5や9になることはない。
| 文字 | ASCIIコード | ~(ASCIIコード) |
|---|---|---|
| t | 116 | -117 |
| o | 111 | -112 |
| k | 107 | -108 |
| y | 121 | -122 |
| 改行 | 10 | -11 |
| (EOF) | (-1) | 0 |
TeX
書こうとしたが、文字列処理は仕様とかexpandafterとか全然分からなくて厳しかった……
想定解は空白や改行を削除して160バイト。
\let\e=\expandafter \def\f#1#2#3#4-{ \edef\h{#1#3} \def\tk{tk} \ifx#3; \else \ifx\h\tk \immediate\write0{T} \fi \e\e\e\e\e\e\e\f\e\e\e#2\e#3#4- \fi } \read0to\s \e\f\s;- \end
……そう……
expandafter多すぎて動作解読できへんけど???????? どうなっとんねん、ほんま。
とりあえずここらへん読んだらわかるようになる……かもしれない。
これの類似問題にAtCoder Beginners Selectionにも含まれている白昼夢(Daydream)があって、これをTeXで解いた記事があるので、そっちも読むとよさそう。私は理解できてないです。というか本番中もこれ読んで「同じ方法でやればできるはず!」と頑張ったが普通に無理だった。
PHP
しとお先生が通したやつ。68バイト。
<?php $s=substr_count(readline(),"tok");for($i=0;$i<$s;$i++)echo"T";
想定解。58バイト。
<?php // tokyo for(;$c=fgetc(STDIN);$a=$b,$b=$c)echo$a.$c==tk?T:"";
<?php // kyoto for(;$c=fgetc(STDIN);$a=$b,$b=$c)echo$a.$c==yt?K:"";
さっきのC言語とほぼ同じ。直近3文字保存して1,3文字目がt,kならTを出力。あるいはy,tならKを出力。
PHPで裸の文字列を使うと勝手に文字列にしてくれるらしい。barewordとかいう名前の仕様。なんでこんな仕様があるのか全く分からないし、普通のプログラミングやる上ではカス仕様以外の何物でもないし、PHP8から廃止されるとかなんとか。
Python3
昆布さんの提出が想定解と完全に一致してた。31バイト。まあ、これはもうこれ以上短く書けないよね……
print("T"*input().count("tok"))
kyoto版は"T"を"K"に、"tok"を"yot"にするだけ。
プロデル
しとお先生が提出したやつ。Shift_JISで52バイト。
ｺﾝｿｰﾙから受け取から「tok」の個数回繰り返 「T」を出力
想定解。Shift_JISで49バイト。
こっちはtokyo版。
ｺﾝｿｰﾙから受け取から｢tok｣の個数回｢T｣を繰り返を報告
こっちはkyoto版。
ｺﾝｿｰﾙから受け取から｢yot｣の個数回｢K｣を繰り返を報告
なるほど、カタカナだけでなくカギカッコも半角があるんだなあ。知らなかった。
コンパイル時TypeScript
TypeScriptで型レベル計算? できらあ!
昆布さんが通したやつ。75バイト。
type R<S>=S extends`${infer _}tok${infer Z}`?`T${R<Z>}`:`` export default R
軽く解説。
inferというのは「○○にマッチするときの○○」に名前を付けて参照できるようにする記号。
// 上記サイトから引用 // 配列の中身の型を取り出す type ArrayOf<T> = T extends (infer U)[] ? U : any; const a:ArrayOf<string[]> = "hoge" // エラーにならない const b:ArrayOf<string[]> = 2 // 型エラー string[]の中身はstringのため、numberを代入することはできない
要は「Tの型がU[]として表せるときにUを取り出す」ということ。
ここまでくればさっきのも読める。
type R<S>=S extends`${infer _}tok${infer Z}`?`T${R<Z>}`:``
R<S>は、Sという文字列が`${_}tok${Z}`として表せるとき、`T`とR<Z>を連結した文字列を返す。要は再帰。
再帰というからには終了条件も必要だ。ここで、もしSという文字列が`${_}tok${Z}`として表せないときは空文字列が返ってくる。これが終了条件。
文字列リテラル型をinferとextendsで扱うのは、発想としては正規表現の(名前付き)キャプチャに似ている。
同じことをRubyで書いたのが以下のコード。
(TypeScriptの挙動と合わせるために、beforeのところでさりげなく最短マッチを使っている)
def solve(str) # 元のコードではbeforeが_でafterがZだった result = /(?<before>.+?)tok(?<after>.+)/.match(str) if result "T" + solve(result[:after]) else # マッチしなかった場合 "" end end # 出力： TTTT puts solve("kyototokyototokyokyototototokyokyokyokyokyototokyo")
↓こちらはスライドにあった想定解。空白抜きで110バイト。
type F<I> =I extends`tok${infer Z}` ?`T${F<`k${Z}`>}` :I extends`${infer _}o${infer Z}` ?F<Z> :`` export default F
さっきのよりちょっと複雑だけど、あれが読めるならこれも読めるはず。
- lが"tok"から始まったら"k"と「"tok"の後ろの文字列」を連結したものを再帰的に呼び出す
- そうでなければ次の"o"を探し、マッチしたら"o"の後ろの文字列を再帰的に呼び出す
- どっちもマッチしなかったら空文字列を返す
……昆布さんが本番で通した解法の方がシンプルで短いんだよな……
Perl
KMCのDNEKさんが通したコード。38バイト。
for(<>){s/kyoto/K/g;s/kyo|to//g;print}
kyotoをKに置換、さらにkyoかtoを空文字列に置換。
こっちは想定解。19バイト。
# tokyo print<>=~/t(?=ok)/g # 参考: kyoto 20バイト print<>=~/k(?=yot)/g
先読みやなあ。そしてPerlマジでなんもわからん。
jq
jqっていうのはJSONを扱える例のコマンドラインツールのこと。jqを知ってても普通「なるほど、あれでコード書くのか!」とはならないだろうけど、実はjqのクエリ言語はチューリング完全らしい。
その証拠に、jqによるbrainfuckインタプリタも存在する。
入力も出力もJSONではないので、ジャッジ側では-rRオプション(--raw-outputと--raw-input)をつけて実行される。
しとお先生が通したやつ。29バイト。
.|split("tok")|.[:-1]|.[]|"T"想定解。どっちも15バイト。
scan("tok")|"T"
scan("yot")|"K"
><> (fish)
KMCのtenさんが提出したコード。54バイト。読めへん。
i:f(?\:ab*(:?ii~?~ >$ ~0>~:@@:@%9=?\ \ o:/
想定解。93バイト。
iiv
>i:a=?;:{$-9=?\
7
c
*
o想定解より短いコード提出してて、こわいです
PPAP
KMCのDNEKさんが提出していたやつ。196バイト。
I have A I have B I have C I have S I have 334 X I have 116 T A Uh! Replace-A-B Uh! Replace-B-C Uh! Pick-C Uh! Replace-S-A Uh! Append-S-B Uh! Append-S-C Uh! Compare-S-X-B!? Uh! Put-T B Uh! Jump-A
要は「1文字ずつ読み、直前3文字を保持しておいて、ASCIIコードの合計が334ならTを出力しループ」ということ。合計が334というのは"tok"のこと。ASCIIコードが116, 111, 107なので。というかこの334は狙ってやったと本人が放送終了後の雑談で言ってた気がする。
想定解。tokyo版。183バイト。
I have A I have B I have C I have 116 T I have 107 K Uh! Pick-A Uh! Pick-B L Uh! Pick-C Uh! Compare-A-T-E!? Uh! Compare-C-K-E!? Uh! Put-T E Uh! Replace-A-B Uh! Replace-B-C Uh! Jump-L
インタプリタの都合上、最後の改行は必要。
こっちは1文字目がtで3文字目がkだったらT出力するやつ。もはやお馴染み。ここまで読んだ人がいれば、だけど……
MAO(マルコフアルゴリズム)
文字列を規則に従って置換していくやつ。なぜかニコニコ大百科がやたら詳しい。そしてチューリング完全らしい。そう……
Markov Algorithm Onlineというマルコフアルゴリズムで問題を解くサイトがあって、MAOというのはそれに由来する。
このサイトでは規則の数の少なさが本質的な評価基準で、規則が少なければどれだけ長くてもいいのだが、今回のコードゴルフでは規則全体の文字数が評価されるので、そういう意味では少し特殊。
今回使われたインタプリタはこれ。
KMCのDNEKさんの提出がこちら。14バイト。
kyoto:K kyo to
使ってたインタプリタでは空文字列で置換するときのコロンを省略しても問題なく動作するらしい。たとえばaを削除するa:をaと書ける。これを発見したDNEKさんにスタンディングオベーションするレベル。
想定解がこちら。13バイト。
tok:Tk to kyo
(スライドでは空文字列に置換するときのコロンを付けていたため15バイトだった)
これ考えたのは私じゃないけど、TSG側で作ってたMAO12バイトも供養しておく。コロンを付けると15バイトになるため提出できなかった。コロン消してもいいなんて知らなかったから……
o tky:T ky t
(追記)
TSGの強者が9バイトの書いてしまったので載せておく。
o yt ky t
た、確かにkyotoがkになってそれ以外削除されるな〜〜〜やべ〜〜〜
反省会総括
アルゴリズムが「"tok"の個数だけTを出力」一辺倒だったのはあまりよくなかった。
そもそもの方針はともかく、「同じ方針でもっと縮むのに……」というのは(1日目のコードゴルフ大会は多発してたのに比べると)少なかった。そこはまあプラス評価ポイントかなあ……Cの自明短縮ポイント逃したのは馬鹿。
チームでいい感じに手分けして書けたのはよかった。
参加記
もう重要なとこは全部書いたので、後は私の文章をもっと読みたいとか時系列順に大会を追体験したいとかそういう人だけ読めばいいと思う。そんな人がどれだけいるかはともかく……
競技開始、問題読解
12時半から放送が開始される。YouTubeにつながってる通話はマイクもミュートして音量も0なので(ブラウザのタブをミュートした)無音。
12時33分、競技開始。
東京か京都、好きな方を数えよ。
好きな方を数えていいらしいです。太っ腹ですね。
入力: to と kyo をそれぞれ10個ずつランダムに並べた50文字の文字列が与えられる。入力の最後には改行が付与される。
出力:
以下のどちらか一方を選んで、出力せよ。
与えられた入力全体の中に含まれる tokyo の数だけ T あるいは t を出力する。T と t が混在していても良い。
与えられた入力全体の中に含まれる kyoto の数だけ K あるいは k を出力する。K と k が混在していても良い。
出力中の空白文字は無視される。改行は空白文字に含まれる。
指定されたもの以外の文字を出力してはならない。
提出するプログラムは、入力されうるすべてのテストケースに正しく出力できるものでなければならない。つまり確率解を禁止する。
つまり、tokyoの数を数えてt/Tをその数だけ出力するか、kyotoの数を数えてk/Kをその数だけ出力するか、どっちかをやればいい。
[AC] 4分44秒 Ruby 30バイト
とりあえずRubyがすぐ書けそうだったので手をつける。
Rubyの文字列マッチをどうやるか調べたところString#scanがあるらしい。
$><<?T*gets.scan("tokyo").size
Tをtokyoの個数回連結して出力するだけ。
同じくらいの時間に昆布さんがNode.jsを70バイトで通してた。速い……
[AC] 7分50秒 Ruby 28バイト
次どうするか考えていたところ、開始7分ちょいで「tokyoを数えるならtokを数えればいい」という本質情報がチームメイトから寄せられる。
さっそくRubyを修正しAC。
$><<?T*gets.scan("tok").size
このあたりでしとお先生がPHPを70→68バイトで通してた。速くない????
これも"tok"の数だけtを出力する方針。
[AC] 12分45秒 Node.js 69バイト
「次どれやろうかな〜」といろいろ考える。具体的に言うと、Bashでどういう方針を取るのが正解か悩んでたし、TeXを取りに行きたいが文字列処理が無理すぎて泣いてた。
気分転換に、昆布さんが書いたNode.jsのコードをちらっと眺める。toStringかますための初めの""+を0+に置き換えて1バイト短縮できた。0を先頭に追加しても何の影響もないため。
(0+require('fs').readFileSync(0)).replace(/tok/g,a=>console.log("T"))
そして、しとお先生がプロデル通してた。
[AC] 16分2秒 Bash(busybox) 33バイト
bashの方針を思い付く。「tokをTに置換、その後T以外を消去」でええやろ。
sed -e 's/tok/T/g' -e 's/[^T]//g'
[AC] 22分48秒 Bash(busybox) 29バイト
Cの方針について考える。うーん、どうしよう……
そして冷静に考えるとBashのやつはシングルクオートいらんかった。気付いて修正しAC。
sed -e s/tok/T/g -e s/[^T]//g
しとお先生がjqを、昆布さんがCompile Time TypeScriptを通してた。はやい
[AC] 40分19秒 C(GCC) 75バイト
Bashを縮めた直後に昆布さんがPython3を通していた。
Cを書いてみた。この時点で"tok"を探す以外の方針を出せていないので、strstrを使う。
forの初期化で入力を受け取り、条件判定でstrstrの結果をpに代入し("tok"がもう存在しない場合ヌルポが返ってくるのでfalse扱いとなりループを抜けられる)、pが次の"tok"の開始位置を指しているので更新部分でポインタを1つ進めてやる。すると文字列pは"ok..."となるので次のループでその先の"tok"を探してくれる。
// セグフォる…… char* p;char s[55];main(){for(gets(s);p=strstr(p,"tok");p++)puts("T");}
セグフォった。なんでだろ〜〜って言ってたらpを初期化してなかった。馬鹿か?
char* p;char s[55];main(){for(p=s,gets(s);p=strstr(p,"tok");p++)puts("T");}
ACした。
