👊

TSG Live! 6 コードゴルフ挑戦してみた

2021/05/17に公開

esolang

codegolf

Brainfuck

whitespace

tech

はじめに

背景

以前「Jellyfish(esolang)の紹介」で、TSG主催のコードゴルフ大会に参加させていただいたことがあるのですが、先日の2021/5/15(土),16(日)にもオンラインのTSG Live!というイベントでコードゴルフ大会をされていました。
残念ながらリアルタイムで視聴し、参加者のウデマエと疑似的に競り合うことはできなかったのですが、後日どこまで縮められるかということで挑戦してみました。
なお、今回の対象言語は(いつもながらの)Brainf**kと、Whitespaceです。
※リアルタイムだと書く人いないから競り合うも何もなかったのでは、というツッコミはご遠慮ください

イベントについて

TSG Live!は、以下のYoutubeのページでライブ配信されていました。コードゴルフ以外にも様々な種類の大会を行っていて、色々楽しめると思います。

TSG Live! 1日目
コードゴルフ大会は当日13:30-15:00 ( 動画の3:40頃から )
TSG Live! 2日目
コードゴルフ大会は当日12:30-14:00 ( 動画の2:09頃から )

1日目

問題

次のような問題でした。

4桁の数字が32行並んでいる。
各行が

0123, 1230, 2301, 3012 なら 1
3210, 2103, 1032, 0321 なら 0

を出力せよ ( つまり32文字出力する )。
間に改行など ( angel注: 任意の文字数の空白、タブ、改行 ) を挟んでもよい。

大抵の場合は、01 や 03 等の特定パターンを検出できれば良いのですが、それだと 1230 や 3210 に対応できません。そこをどううまくまとめるのかがポイントになるように思います。

Brainf**kでの解法(48B)

ということでBrainf**kでの方針ですが、素直に mod(連続する2文字のコードの差, 4) で見ることにしました。
出力結果には、入力の0～3を流用できれば良いのですが、ただピッタリ選ぶのは難しいので、改行文字のコード10を掛け算のネタとして活用するくらいにします。
Rubyでの疑似コードは次の通りです。

Ruby疑似コード

while c1=STDIN.getbyte
  c1+=1   # Brainf**kでのEOF検出の副作用
  c2=STDIN.getbyte
  r=(c2-c1)%(-4)  # 0 または -2
  r+=1 if r!=0
  STDIN.getbyte; STDIN.getbyte  # 2文字読み捨て
  putc r+STDIN.getbyte*5-1  # 改行コード10を利用して+49して出力
end

これを、Brainf**k版で実装したのが、以下の48Bになります。

Brainf**kF版48B

,+[                      * 1文字先読みしてのループ
 >,[<[+<<]>[<---<]>>+]   * c2マイナスc1 mod マイナス4 の実装
 <[+>]                   * 非0ならプラス1
 ,,,[-<+++++>]<-.        * 49足して出力
,+]

さて、工夫ポイントとしては mod -4 の部分です。
素直に実装するなら2文字の差を取ってから [<[+<<]>[<---<]>>-] になるのですが、差をとる分のロスが気になります。
ここで、余りの位置に差を取る対象の数を置いて計算を開始することで、差を取ると同時に mod を計算することができます。これによりロスを吸収しているのが工夫ということです。
この場合、余りの位置の数を消費しきれない懸念があるため、そこを「負数をカウントアップして処理する」ようにしています。ループ最後の - を + に替えているのはそのためです。
※ 03 のパターンのみ「消費しきれない」のですが、残る -2 は mod を計算した場合と同じなので結果オーライです。

Brainf**k後日更新版(42B)

※2021/5/22追記

前章で工夫だとして色々語ってしまったわけですが、素直に先頭2文字の差を取った方が話が早いことに気付きました。
更新版のコード(空白・コメント含む)は以下の通りです。

Brainf**k更新版(42B)

,+[               * 1文字先読みしてのループ
 >,[-<->]         * 先頭2文字の差分(1補正付)
 +<[--[-<]>-]     * x%4/2
 ,,,++[->++++<]>. * 改行文字(10)から48を作って加算し出力用に
,+]

ポイントは3行目の+<[--[-<]>-]で、これだけで mod 4 の値を2で割った商まで一気に出せてしまうところです。( 余りは処理を抜けた後、すぐ右隣りのセルに保存されています )
これは、mod 4 と言いながら余りが 0,2 しかなく実質 mod 2 計算で、その場合大幅な簡略化ができることを失念していたというところですね。

Whitespaceでの解法(参考,52B)

続いてWhitespaceです。ただ、大会での対象コードの一覧には挙がってなかったようなので、あくまで参考になります。
方針としては、動画中にあった y=mod(mod(x,217),2) をそのまま実装するのがおそらく一番適切でしょう。
Whitespaceのネイティブコードだと見辛いので、空白・タブ・改行を s,t,n に変換したバージョンを載せます。

Whitespace-stn版52B

nssnsssnsnstntttttsssttsttsstntsttssstsntstttnstnsnn

記事「WhiteSpaceアセンブラ・逆アセンブラの紹介」で使えるアセンブリコードでは次の通りです。

アセンブリコード

mark   MAIN     # 0000: nss,,n ( labal: null )
  push +0       # 0004: ss,s-,n
  dup           # 0008: sns
  geti          # 0011: tntt
  retr          # 0015: ttt
  push +217     # 0018: ss,s-ttsttsst,n
  mod           # 0030: tstt
  push +2       # 0034: ss,s-ts,n
  mod           # 0040: tstt
  puti          # 0044: tnst
  jump MAIN     # 0048: nsn,,n ( label: null )

2日目

問題

次のような問題でした。

to と kyo をそれぞれ10個ずつランダムに並べた50文字1行(改行あり)の文字列が入力される。
文字列中の tokyo の個数分の t あるいは kyoto の個数分の k どちらか一方のみを出力する。
出力中の大文字・小文字は区別されない ( 小文字の代わりに大文字でも良い )。また、任意個数の空白・改行を混ぜても良い。

( この大会の趣旨が東大vs京大だったためか ) tokyo, kyoto どちらを数えるか選択肢があります。加えて大文字・小文字をどうするか、空白等を混ぜるか、色々選ぶところがあります。
また、esolang的には最後の改行の対処も地味に重要です。

共通の方針

こちらの解説スライドに幾つか方針があるのですが、管理のし易さを考えて、次の状態遷移図に沿って実装することにしました。

なお、出力としては「tokyo の個数分の t」を選んでいます。
これは私が東大びいきだから…ではなくて、文字の塊として kyo の方が1文字多くなっていて、状態遷移の時に読み捨てし易い点と、Brainf**kの場合に改行入力と to を同一視できる点からの選択です。

Brainf**kでの解法(45B)

Brainf**kでは、単純に「1文字読んでコードが偶数なら to、奇数なら kyo」と判断するようにしました。気になる改行の処理ですが、これは to 入力と同一視して支障がないので、全く何もしなくて済むようになります。
※「kyoto の個数分の k」とする場合、同一視で支障が出ることに注意

mod 2 計算の時、元の値も保存しておくことで、後の t 出力に役立てます。
ということで、コードは以下のようになります。

Brainf**k版45B

,+[                      * 1文字先読みループ
 -[->+>[->>]<[>+>]<<<]   * 値保存型 mod 2 計算
 >>[-<,<<[.>]>>>>]       * 奇数(k入力)の分岐内で t が残っていれば出力
,,+]

奇数(k入力)の分岐内で余分な1文字読み捨てと、t が残っている場合の出力を行っています。
いずれにせよこの分岐に来たら、目いっぱい右移動しておくことで t 出力の起こらない、まっさらな領域へと移っておきます。

Brainf**k後日更新版(35B)

※2021/5/23追記
記事を公開して間もなく、mod 2 の実装がぬるかったことに気付いてしまいました。

ということで、以下の35B版に更新しました。

Brainf**k版35B

,+[                  * 1文字先読みループ
 [-[-<++<]>>]        * 値保存型偶奇判定
 <[,<<[.>]>>>>>]>    * 偶数判定(k入力)で t が残っていれば出力
,,+]

ポイントは、もともと mod 2 を計算していたところを「偶奇判定」に替えたところです。
余りそのものを求めずに、ループを抜けたところでの位置関係で判定できるようにしています。開始が4(偶数),3(奇数)の場合の処理の例として以下の図をご覧ください。

これにより、,+ で1増加していることを加味すると、次のように処理に生かせます。

k(107)入力 … 1増加した108が偶数なので、すぐ左隣を見て t 出力の判断に移れる
t(116)入力 … 1増加した117が奇数なので、3セル左に116が残り、これが出力用の t に使える

なお、この偶奇判定は移動の向きを反転する等幾つかバリエーションがあるのですが、このパターンが一番縮むようです。
いやはや、こういうのが一発で出てこないところ、まだまだ未熟さを感じました。

Whitespaceでの解法(79B)

Whitespaceでは、Brainf**kの場合と違って、文字の塊の2文字目 o,y の文字コード 111,121 の mod 3 の値で判断することにしました。1文字目にすると、数値の保存や読み捨てがやや煩雑になるからです。
なお、EOF時例外で異常終了させられるので、最後の改行については特に考えなくてすみます。

では、実装したコードの、空白・タブ・改行を s,t,n に変換したバージョンです。

Whitespace-stn版79B

sssnnssnnstsnnstsnsssttntsttntsnsnnsnsnstsnsnnntsntnssnsnnnsssnsnssnstntstttntn