TSG LIVE! 4 ライブコードゴルフ大会 writeup + 解き直し ( Perl, sed, Haskell )

この記事は TSG Advent Calendar 2019 の 7 日目です。昨日（今日）は taiyoslime さんの「2019年駒場祭ライブコードゴルフ（実用言語編）」でした。

adventar.org

駒場祭2019でTSGが催した企画、『TSG LIVE! 4 ライブコードゴルフ大会』に参加した感想です。

↓ライブの様子はこちらからご覧になれます。

www.youtube.com

どんな問題が出たの？

お題

2桁の整数が100個、改行区切りで与えられる。それぞれの数について、九九表に存在するとき1、そうでないとき0を出力せよ。

詳しいルールは https://esolang.hakatashi.com/contests/komabasai2019/rule で見られます。

当日の方針

当日は、C言語、><>(フィッシュ)、LibreOffice Calc を同じチームである iLiss さんに任せて、自分は中央付近にあるスクリプト言語郡（Ruby、Perl、Pyrhon、Node.js）を取ったあと、取れる位置にある & 自分が書けそうな esolang (sed、Brainfuck、Whitespace) を取る方針で行きました。時間があったら GolfScript に挑戦したかったですが、書いたことのないものを時間内にやるのは難しいですね……。でも書けるものは書ききれたので良かったです。前回の NoSub を悔やんでいた iLiss さんが今回 C を取ってくれたのはいい話です。

最終的な盤面はこちらです。

f:id:n4o847:20191207191949p:plain

他の記事の宣伝

この問題にはいくつか解法がありますが、中でも作問陣が考えた「符号化」解法は、Ruby や Python で他の解法の追随を許さない強いコードが書けてしまいます。その解説や、その他実用言語（C言語、Node.js）での解法は昨日（今日）の taiyoslime さんの記事

taiyoslime.hatenablog.com

で書かれているのでそちらを是非読んでみてください。

また、><>(フィッシュ)、GolfScript、Aheui(아희)、Tetris による解法は 9 日目に kuromunori さんが、Brainfuck による解法は 18 日目に Szkieletor さんが書いてくれるらしいので、そちらも読んでみてください。

というわけでこの記事では、それら以外で縮めたら面白そうなものを取り上げて書いてみます。

Perl 編

ライブの最中、視聴者から「39 bytes になった」みたいなコメントがあったらしく……？（未確認）

それを目指していきたいと思います。

競技中に出したコードは以下です。 (55 bytes)

$a=<>,print((grep{$a%$_<1&&$a/$_<=9}1..9)?1:0)for 0..99

これなんで本番で思いつかなかったのか不思議なんですが、ループを行ごとに改善します。 (51 bytes)

$a=$_,print((grep{$a%$_<1&&$a/$_<=9}1..9)?1:0)for<>

変数への格納が長いので、正規表現で捕捉しましょう。 (48 bytes)

//,print((grep{$'%$_<1&&$'/$_<=9}1..9)?1:0)for<>

見つかったかどうかを 1 と 0 に置き換えるのが長いので、// (== 1) と組み合わせて数値に変換します。 (41 bytes)

print//-!grep{$'%$_<1&&$'/$_<=9}1..9for<>

判定部分を改善します。 (39 bytes)

print//-!grep$'%$_<($'/$_<=9),1..9for<>

39 bytes になりました！　わいわい

sed 編

Twitter でエゴサすると、 89 bytes になった人がいますね。それを目指していきたいと思います。

sed は演算するよりも埋め込みです。ということで当日 1 回目です。 (312 bytes)

/^\(1\|2\|3\|4\|5\|6\|7\|8\|9\|2\|4\|6\|8\|10\|12\|14\|16\|18\|3\|6\|9\|12\|15\|18\|21\|24\|27\|4\|8\|12\|16\|20\|24\|28\|32\|36\|5\|10\|15\|20\|25\|30\|35\|40\|45\|6\|12\|18\|24\|30\|36\|42\|48\|54\|7\|14\|21\|28\|35\|42\|49\|56\|63\|8\|16\|24\|32\|40\|48\|56\|64\|72\|9\|18\|27\|36\|45\|54\|63\|72\|81\)$/c1
c0

入力が 2 桁であることに気づいて 2 分後に出したのが当日 2 回目です。 (237 bytes)

/10\|12\|14\|16\|18\|12\|15\|18\|21\|24\|27\|12\|16\|20\|24\|28\|32\|36\|10\|15\|20\|25\|30\|35\|40\|45\|12\|18\|24\|30\|36\|42\|48\|54\|14\|21\|28\|35\|42\|49\|56\|63\|16\|24\|32\|40\|48\|56\|64\|72\|18\|27\|36\|45\|54\|63\|72\|81/c1
c0

さて、まだ無駄があります。まずはソートしてユニークします。 (113 bytes)

(1..9).map{|a|(1..9).map{|b|a*b}}.flatten.select{|x|x>9}.sort.uniq.join("\\|")

/10\|12\|14\|15\|16\|18\|20\|21\|24\|25\|27\|28\|30\|32\|35\|36\|40\|42\|45\|48\|49\|54\|56\|63\|64\|72\|81/c1
c0

十の位でまとめてみます。 (68 bytes)

/1[024568]\|2[014578]\|3[0256]\|4[02589]\|5[46]\|6[34]\|72\|81/c1
c0

一の位でまとめると伸びてしまいます。 (76 bytes)

/[1234]0\|[28]1\|[1347]2\|63\|[1256]4\|[1234]5\|[135]6\|27\|[124]8\|49/c1
c0

[1234]0 と [1234]5 が一緒？ (69 bytes)

/[1-4][05]\|[28]1\|[1347]2\|63\|[1256]4\|[135]6\|27\|[124]8\|49/c1
c0

ここで、入力→出力を以下のような表にしてみます。

	0	1	2	3	4	5	6	7	8	9
1	1		1		1	1	1		1
2	1	1			1	1		1	1
3	1		1			1	1
4	1		1			1			1	1
5					1		1
6				1	1
7			1
8		1
9

うーん、規則性なし！ｗ

結局十の位でまとめたやつの 3[0256] が 1[024568] の部分集合なので 67 bytes になりました。

/1[48]\|2[014578]\|[13][0256]\|4[02589]\|5[46]\|6[34]\|72\|81/c1
c0

Haskell 編

Haskell ゴルフは駒場祭 codegolf day2 writeup (or Haskellゴルフのすすめ) - Lを探す日常とかを見て、かねてからやりたかったやつです。

ビット埋め込みはあまり Haskell っぽさが出なくて学習に向いてないと思ったので後回しにします。

まず九九表を生成する方針で愚直に書きます。この時点でちょっとてこずりました。 (103 bytes)

import Control.Monad
main=replicateM_ 100$do
 a<-readLn
 print$fromEnum$elem a[x*y|x<-[1..9],y<-[1..9]]

do 構文を展開してみます。 (100 bytes)

import Control.Monad
main=replicateM_ 100$readLn>>=print.fromEnum.flip elem[x*y|x<-[1..9],y<-[1..9]]

縮むかと思ったけど、 do 構文ってゴルフ的にも結構えらいんですね。

限界を感じたので、「Haskell ゴルフ」とかでググった記事を読み漁ります。すると String -> String を IO () にできる interact がえらいというのが随所で書いてあるので使います。 (86 bytes)

main=interact$unlines.map(show.fromEnum.flip elem[x*y|x<-[1..9],y<-[1..9]].read).lines

え、めっちゃえらい。あと、各行処理は (>>=f).lines が短いらしい。lines :: String -> [String] の各要素を f :: String -> String に渡して、 String が [Char] であることからひとつのリストにまとめるんですね！　この辺 Haskell って感じでめっちゃいいですね。 (78 bytes)

main=interact$(>>=show.fromEnum.flip elem[x*y|x<-[1..9],y<-[1..9]].read).lines

こうなると九九表の生成も Haskell チックな演算子を使うと嬉しくなる気がします。 (76 bytes)

main=interact$(>>=show.fromEnum.flip elem((*)<$>[1..9]<*>[1..9]).read).lines

ここで、もう一つの解法であるビット埋め込みを試してみると (76 bytes)

main=interact$(>>=show.(`mod`2).div 0x20101814325195b35d400.(2^).read).lines

で並びました。埋め込みを使わなくても並ぶことができたのは嬉しいです。

あとは elem を中置にし、 [1..9] をまとめて 74 bytes です。

r=[1..9]
main=interact$(>>=show.fromEnum.(`elem`((*)<$>r<*>r)).read).lines

fromEnum が長いんですが、ここは関数合成を使っているのでググったテクニックを使ってもあまり縮まなかった……。

感想

自分のコードゴルフ経験は部内の大会以外だと AtCoder 上のゴルフくらいで、そこだと決まった一部の言語で争うことになるので、他の言語を練習するというのもいいですね。Haskell ゴルフは今回始めてやってみましたが、ここで Functor・Applicative・Monad が活きてくるのエモいですね。

上で挑戦したものもまだ縮むかもしれないので、見つけた方はぜひ報告お願いします。

明日は smallkirby さんの「TSGに連れて来られるまでのお話とpwnの学び始めを懐かしんだ後に適当なpwnのwriteupを書いたら発狂して湖に飛び込みYoutuberデビューする予定」です。

追記

コメントの 39 bytes はこれらしいです。

Perl 39bytesとしてこんなのを考えていました
$_=1x$_,print/^(1{1,9})\1{0,8}$/+0for<>
— こたつがめ (@kotatsugame_t) 2019年12月7日

これで各種倍数の判定ができるのは知らなかったので驚きなんですが、色々使えそうなテクニックですね。

Perl 32 bytes が出てきました。

（ファイル提出ができるなら）Perl 32Bになりました。https://t.co/A5jJ24fgTR
— %20｜1970 (+38, -1) (@henkoudekimasu) 2019年12月7日

バイト列を直接埋め込んでいるんですねー。当日使ったシステムにはファイル提出機能もあるので有効そうです。

Whitespace で書いていただきました。

一応折角なので、Whitespace(119)です。https://t.co/vysElTh6CY
アセンブリコード(自作ツールで動くやつ)はこちら。https://t.co/grJdnSoXvo
— angel (as ㌵㌤の猫) (@angel_p_57) 2019年12月19日

本番中はこんなクソコードを書いていたんですが、ちゃんとゴルフすると短くなりますね。