TSG LIVE! 5 ライブコードゴルフ大会 参加記

こういう大会があることは結構昔から知っていて、五月祭に足を運んでは実況を見ていたのですが、今年はなんと外部プレイヤーとして参加するチャンスがあるとのこと！意気揚々と立候補して、無事外部チームの1人として参加できることになりました。

追記：外部チームとして一緒に参加したx20さんの参加記が公開されました！リンクはこちらです。

i-i.hatenablog.jp

また、対戦したTSGチームのうらさんの参加記も公開されました！リンクはこちらです。

n4o847.hatenablog.com

5月にもコードゴルフ大会があって、そちらは東大と京大が合同で開催した、かなり大きな大会でした。僕以外の外部の人も数名参加されていて、たとえばanarchy golfの管理人であるshinhさんもいらっしゃいました。この大会のWriteupはここです↓

第6回東大京大コードゴルフ大会 Writeup · hakatashi/esolang-battle Wiki · GitHub

今回は特にそういった場が設けられているわけではないので、自分が書いたコードについてこのブログ記事をWriteup代わりにします。

問題概要

それ以前のどの数値よりも真に小さいか判定せよ。

入力

2桁の数値が50個、改行区切りで与えられる。入力の末尾には改行が付与される。

出力

与えられた数値それぞれについて、それ以前に与えられた数値のいずれよりも真に小さいとき1、そうでないとき0を出力せよ。

※ちなみに、出力中の空白文字（\s）はすべて無視されます。

制約

  • 同じ数値は2度以上出現しない。
  • 入力の数値は10以上99以下である。
  • 初日については1を出力すること。

C言語（55B）

main(a,p){for(;~scanf("%d",&a);)puts(p>a?p=a,"1":"0");}

初めに手を付けた言語です。最初問題を読み間違えていて、大きいかどうか判定して2回WAを出してしまいました。修正してACし、さらに3度縮めたのが開始6分半のことで、そのあとは誰にも取られませんでした。かなりシンプルなのでこれ以上縮まないと思っています。

強いてテクニックを挙げるなら、pの初期値を設定する代わりに、main関数の第2引数が十分大きいのを期待していることでしょうか。あとは親の顔より見たコード、といった感じに手癖で書けました。

Go言語（87B）

package main
import."fmt"
func main(){p:=100;for{a:=0;Scan(&a);if p>a{p=a};Print(p/a)}}

上にリンクを貼った、以前の大会のWriteupを見て書きました。一応最初の提出から25B縮んでいます。まず出力するのにif文とPrintを2回書くのは明らかに長いので、そこを何とかします。p/aすれば1と0が得られるので、場合分けがなくなってよさそうです。書いてる最中はGo言語の割り算が整数に切り捨てるか知らなかったのでちょっとドキドキしました。

これは副次的な効果をもたらします。aの初期値として0を入れておけば、Scanに失敗したときにそのままa=0となってp/aがゼロ除算で落ちてくれます。こういう終わり方でもAC判定を得ることができるため、50回のループから無限ループに書き換えることができました。

周りにTSGチームの陣地がないので、一切脅かされませんでした。例えばp:=99にするだけでも（1/90の確率でWAするようになりますが）1B縮みます。Go言語はほとんど使用したことがないので、探せばまだ少し縮むと思います。

Python3（49B→47B）

x=':'
while t:=input():
 if u:=x>t:x=t
 print(+u)

これはTSGチームに縮められてしまいました。ループ内部をx=min(x,t);print(1-(x<t))とすると48Bのようです。ifのせいでインデントが入っているので縮む余地はありそうに見えていたのですが……。

配信アーカイブを見ていて気付きましたが、これで47Bになります。

x=[]
for t in open(0):x+=t,;print(+(min(x)==t))

while t:=input()がfor t in open(0)になっているのは、同じ長さ（！）なので更新点ではありません。Pythonには配列のminがあるので、以前の最短を特別に保持する必要がなかったようです。この発想は大会中、一切出てきませんでした。

追記

x,r=': '
while t:=input(r):
 if r:=+(x>t):x=t

しーあるさんの改善により、45Bになりました。

GolfScript（27B→16B）

~].99\{[\]$~;.}%\;]zip{~=}%

~]は入力全体を数値の配列にするイディオムです。まず入力が1つの文字列としてスタックに入っているので、~でevalして数値に分解し、]で配列にまとめます。[と対応していない]は、公式のドキュメントにも載っている由緒正しい使用方法です。

次に、その配列をdupして、cumminを計算します。苦労しました。mapで実装することにしたのですが、以前の最大値を変数に持つ必要があるように見えます。

mapの仕様がよくわからなかったので、インタプリタの実装を確認しました。スタックサイズを記録したあとに要素をpushしてブロックを実行し、増えた分だけ取り出して新しい配列にしているみたいです。つまり以前の最大値をスタックに残したままやりくりすることができるはずなのですが、なかなかうまくいかず苦労しました。しかしハマっていたのは別のところだったらしく、結局かなりシンプルなコードになりました。

{[\]$~;.}が実行するブロックです。先頭2要素を配列にまとめ、sortしてからdumpし、大きいほうの要素を削除して小さいほうの要素をdupします。このdupされた要素のうち、片方は新しい配列に入れられて、もう片方はスタックに取り残され、次のループに備えます。

cumminする前とした後の配列をzipしたあと、それぞれのペアについて値が等しいかどうかをスタックに積んでいきます。{~=}です。コードが終了するとスタックの中身がすべて出力されるので、明示的に出力を書く必要はないです。

さすがにこんなコードが短い訳がない。ということで書き直しました。16Bです。

~]1\{.[@]$~<\}*;

美しいですね。mapでもeachでもなくfoldを使っているのがポイントで、これで仮の最小値として99を置く必要がなくなりました。代わりに、最初の出力として1を用意しています。

foldするブロックでは、これまでの最小値をa、今見ている要素をbとしてa bの状態で実行が開始されます。dupしてa b b、[@]するとこの3つが配列にまとめられます。sortしてdumpするのは同じで、a<bならa b b、a>bならb b aになります。後ろ2つの大小比較で0 or 1を作り、先頭の要素は新しい最小値になります。この2つをswapして次のループに備えます。

最後に計算してきた最小値を捨てれば、出力だけがスタックに残り、自動的に出力されます。

Crystal（38B）

x=":"
while a=gets
p x>a ?(x=a;1):0end

GolfScriptを取ったことによって提出できるようになった言語です。これより1B長いものが書きあがって提出しようとしたところ、ほんの1分ほど前にx20さんが全く同一のコードを提出していました。コミュニケーションをとっていなかったため、お互い同じ言語を縮めていることに気づけませんでした。試しに0とendの間の改行をなくしてみたところ動いたので、そこで-1Bしました。

CrystalにおいてgetsはString? = String or Nilを返します。本来であればこれをStringと比較するとCEになるのですが、whileの条件式に書くことでNilではないという推論が働き、String型になってくれます。

while · GitBook

あとはまあ、Rubyとほとんど一緒です。CharとStringが別物のようで、x=?:と書くとCEでした。

><>（45B）

aa*v      ;
i~ >:i:0(?^68*-a*i68*-+:@(:1$-n?~

最後に焦りながら取った言語です。書きあがったのが終了3分前でしたが、提出場所を間違えているのに1分間気づかず、冷や汗を流しました。ほとんどゴルフできていません。例えば文字コードから数値に直す部分など、48を2回引くよりも48*10+48を1回引いたほうがどう考えても短くなります。というかそもそも、比較するだけなので定数を引く必要すらありません。仮の最小値を適切に大きくしておけばよいです。

最初は1行目に処理を書いて2行目で先頭に戻るコードを書いていたのですが、仮の最小値を持つ部分との兼ね合いで処理が2行目に来ました。すると2行目だけでループできることに気づき、先頭に戻る処理を省くことができました。これは数少ないゴルフしたポイントといって良いでしょう。

頭がGolfScriptになっていたので、コマンドの違いに苦労しました。popは;ではなく~、dupは.ではなく:、swapは\ではなく$、@でrotateする方向が逆……。

まとめ

時間中に触れたのは全部、以前に書いたことがある言語でした。意気込みとして「いろんな言語を触る」と言ってはみたものの、時間が圧倒的に足りません……。

RubyとPython3が取られたのは、結構ショッキングでした。Rubyの三項演算子はただでさえ正しく解釈されるために非自明な空白の入れ方をしないといけない上、_1が絡むといろいろ試すべきことが増えます。今回の短縮はx>_1 ? T:Fと書くと空白が2つ必要になる一方、演算子を逆にして_1<x ?T:Fと書くと1つで済むというものでした。

問題はかなり面白かったです。75分という短い時間でそこそこ盤面を広げるにはちょうどいい難易度でした。盤面を日本地図にするのも、提案されたときは結構度肝を抜かれましたが、何度かアンケートでバランス調整されたこともあってか、特に引っかかることなく楽しめました。（これは外部チームの手を出せるマスが広かったので不自由しなかっただけかもしれませんが……。）

時間がないとは言いましたが、これ以上長くすると配信に影響が出そうなので、触れない言語があったのはしょうがない話です。事前説明で聞いた話では、UnlambdaでもACできるアルゴリズムを開発してはいたそうです。すごすぎます。

大満足の大会でした。共に参加したx20さん、対戦してくださったうらさん、博多市さん、またこのような場を設けてくださったTSGの皆さん、本当にありがとうございました！