駒場祭 codegolf day2 writeup (or Haskellゴルフのすすめ)

この記事は TSG Advent Calendar 2018 の6日目です。
昨日は fiord さんのちょっとしたlsのtips でした。

今日は駒場祭のコードゴルフの writeup を適当に書いていきます。

駒場祭がありました

今年の駒場祭で TSG はライブ放送を行いました。強い人々が CTF や競プロ、AI のライブに参加していたのでそれらに関する記事もアドベントカレンダーでたくさん書かれています/書かれる予定ですが、私はまともなことは書けないのでコードゴルフについて書きます。
コードゴルフ大会ページ - 問題 - 提出一覧

Ruby 40byte

Rubyの提出一覧
問題を見て最初に思い浮かんだのが正規表現を用いる方法でした。とりあえずその方法を愚直に Ruby で書きました(44byte):

gets.gsub! /1(?!....1......1....1)/,?0;print

無駄に引数なしの print (引数がない場合グローバル変数 $_ を出力する)を使っていますが、それ以外はとても読みやすいコードです。
これを微修正したのが最短です(40bytes):

$><<gets.gsub(/1(?!....1.{6}1....1)/,?0)

$> は $stdout のエイリアスです。<< は IO の出力演算子です。
正規表現(否定先読み)で置換する方法が想定以上に強くて、最後までここから縮めることができませんでした。
(特に Ruby の)正規表現の威力は Rubyの正規表現で足し算 (2) 異なる桁数 - Lを探す日常などで散々触れてきたのでよく分かっていますし正規表現は大好きですが、コードゴルフで正規表現が最短になってしまうと個性が出にくくて悲しいですね。

Haskell 114bytes (→ 80 bytes)

Haskellの提出一覧
今回の大会で一番準備に時間をかけたのが Haskell です。
まず StackExchange を見ました。色々な知見が得られましたが、その中でも Use the list monad は Haskell の真髄の一つであるモナドが絶大な効果を発揮していて感心しました。
残念ながらリストや関数などの具体的な型に対するモナド演算をすぐに行えるほどのモナド力をまだ身につけていないので、とりあえずリストと関数型におけるモナド演算まとめを作成して大会に臨みました。
まず最初に提出したコードがこちらです(149bytes):

g x=[t|t<-[0..32],x!!t=='1',x!!(t+5)=='1',x!!(t+12)=='1',x!!(t+17)=='1']!!0
f x|i<-g x=(replicate i '0')++"1"++(replicate (49-i) '0')
main=interact$f

この時点で結構読みにくいです。g x で1を出力するべき添字を求めて、f x 内で(ガードとして) i に代入しています。あとは0をいっぱい繰り返して1を挟めば完成です。
ここでさっきのモナド演算まとめを眺めると、replicate が短くなりました(137bytes):

g x=[t|t<-[0..32],x!!t=='1',x!!(t+5)=='1',x!!(t+12)=='1',x!!(t+17)=='1']!!0
f x|i<-g x=([1..i]>>"0")++'1':([i..48]>>"0")
main=interact$f

微妙に '0' が "0" に変わっていたり ++ が : に変わっていたりします。ここでコンパイルエラーが生えまくりました。
次に、g x の唯一の要素を取り出すという操作を外に出して f x のガード内に移します。
さらに g x の条件を [0,5,12,17] のリスト上で回すようにすると、最短コードになります(114bytes):

g x=[t|t<-[0..32],all(\i->x!!(t+i)>'0')[0,5,12,17]]
f x|[i]<-g x=([1..i]>>"0")++'1':([i..48]>>"0")
main=interact$f

大会後

このまま大会終了まで Haskell はこの状態だったのですが、落ち着いて見るとまだまだ縮むことが分かります。
ここで縮めるような記事が writeup と言えるのかは知りませんがやっていきます。
まず方針を大幅に転換します。添字を求めてから文字列を生成するより、g x の条件の True/False を '1'/'0' に変換して結合した方が短い気がします。
その方針で実装したのがこちら(88bytes):

f x=concat[show$sum[1|t<33,all(\i->x!!(t+i)>'0')[0,5,12,17]]|t<-[0..49]]
main=interact$f

さっきのコードと比べて、t の範囲が32以下から49以下に変わり、t < 33という条件が加わりました。これによって33以上の場合は常に0を返そうとしています。
次に all ... 部分が一つ内側の内包表記の中に入っています。これは StackExchange のこの回答の最後にある真偽値を数値に変える式です。
これを show すると文字列が得られるので、それらを concat しています。
ここでまたモナド演算まとめを見てみましょう。concatMap には素晴らしい略記法がありますね。
略記したらこうなります(84bytes):

f x=show=<<[sum[1|t<33,all(\i->x!!(t+i)>'0')[0,5,12,17]]|t<-[0..49]]
main=interact$f

4bytes も縮みました。
ふと f を別関数に分ける必要がないことに気付きます。まとめましょう(83bytes):

main=interact(\x->show=<<[sum[1|t<33,all(\i->x!!(t+i)>'0')[0,5,12,17]]|t<-[0..49]])

こうなってラムダ式が2つも出てくるとポイントフリー欲が湧いてきますが、現段階では短くなりません。まずは別のところを考えます。
もう一度方針を転換して、しぶとく生き残って来た all をとうとう捨てます。入力が'0'か'1'しか存在せず、出力も'0'か'1'しか存在しない、これを活用できないか。
同じチームの satos さんが C 言語の解法で入力の特性をうまく利用して偉く*1なっていました(後述)が、Haskell も違う方法で縮められます。
4つとも'1'なら'1'を、ひとつでも'0'が含まれていたら'0'を返すもの。それは minimum です(84bytes):

main=interact(\x->[minimum$(\i->x!!(t+i))<$>[0,5,12,17]|t<-[0..32]]++([0..16]>>"0"))

1文字増えましたが、ポイントフリーにすることで縮みます(80bytes):

main=interact(\x->[minimum$(x!!).(t+)<$>[0,5,12,17]|t<-[0..32]]++([0..16]>>"0"))

2つ前のコードと比べると、17個の"0"を生成する部分が余計に生えてしまっていますが、その前の部分はだいぶコンパクトになりました。
これが記事を書いている時点で私が発見した中の最短コードです。

その他の言語

Kotlin も少しゴルフのテクニックを調べましたが、結局縮めないまま時間が来ました。
C# は適当に書いたので長いです。適当すぎて最初は System.Console.Write を System.out.println と書くなどしていました。
C言語も(satos さんはブログで書かないと思うので)触れておくと、試合中「これは偉い」と二人で盛り上がっていたのは s[0]&s[5]&s[12]&s[17]|48 (一部改変)という式です。入力の'0', '1'(つまり48, 49)をうまく出力につなげることができました。v[99] と99個取っておいたおかげで v の51文字目以降は全て0で埋められていて、上の偉い式で(|48 とあわせて)ちゃんと'0'が計算されるようになっています。
実際には赤チームもこのビット演算には辿り着いていて、差は添字でなくポインタを直接回したところで生まれたようです。
Whitespace は satos さんが独自コンバータで書いていました。
Unlambda, Befunge-98, Hexagony の3言語は時間が足りず解けませんでした。特に Hexagony が解けなかったのは悔しいので、独自コンバータを作ろう(そしてアドベントカレンダーのネタにしよう)と思っています。

まとめ

盤面の通り今回は8対3で大勝利を収めることができました。satos さん、その他大会に関わった皆さん、お疲れ様でした！
今後も(特に Haskell や Hexagony で)精進していきます。
明日、TSG Advent Calendar 2018 7日目はこーしーずさんの「駒場祭CTF day3 なにかのwriteup」の予定です。

*1:解法が偉い=解法が強い=解法がすごい