👊

TSG Live!8 コードゴルフ挑戦してみた(day2)

2022/05/15に公開

はじめに

背景

恒例の? 東大TSGのTSG Live!でのコードゴルフ大会、2022年五月祭版day2(2022/5/15)をリアルタイムで視聴していましたので、参加者のつもりで挑戦してみました。
day1は残念ながら見逃してしまいましたが、余裕があれば後日挑戦しようと思います。
今回の対象言語は(いつもながらの)Brainf**kと、Whitespaceに加え、以前修得したJellyfishです。

イベントについて

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

  • TSG Live! day1
    コードゴルフ大会は5/14 15:00- ( 動画の4:10頃から )
  • TSG Live! day2
    コードゴルフ大会は5/15 15:00- ( 動画の2:37頃から )

2日目

問題

次のような問題でした。

  • 標準入力より、各行0-9a-jの各1文字ずつをつなげた2文字ずつの文字列が入力される。
    ※確認し忘れましたが、おそらく行数は固定だったと思います。Jellyfishでは10行を前提として実装します。
    → 後日、10行固定だったことが確認できました。なので、下のJellyfishの解はそのまま通るものです。
  • 文字列の0-9は十干(甲乙丙丁…)、a-jは十二支(子丑寅…)を表すものとする。
  • 文字列の表す干支(十干十二支)となる年を1つずつ、空白文字(任意個数の空白/タブ/改行等)で区切って出力する。
  • なお、その年は西暦とし、1以上で干支が合致していれば任意の年を選んでよい。

例えば今年の干支は「壬寅」であり、文字列としては8cが対応します。

共通の方針

リアルタイムでの想定解法として、2文字の文字コードx,y ( x: 48~57, y:97~108 ) に対し、

z=mod(x-y,12)\times 5+x+\alpha

が挙げられていました。( αは実際の年に合うように調整する差分 )
が、実際には mod の計算は不要で、
z=6x-5y+\alpha

の計算でできます。

他の言語では、0-9,a-j をまとめて36進法等で見る解法もあったようですが、私の対象とした3言語では、上の計算で十分対応できると判断しました。

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

TSG! LiveでのBrainf**k処理系は、かつて採用していたesolang-boxのesotopeから、esmoer という改良版に変わったようです。仕様としては estope と変わらないようなので、8bitセル、EOF=-1(255)、wrap-aroundあり、負の番地ありという前提で考えます。

行頭はEOF判定のため+1すること、引き算で負になるところは wrap-around で+256相当になることを考えると、実は次の計算で済みます。

z\equiv 6(x+1)-5y-1~mod~256

ただ、計算結果は2桁~3桁と、桁数不定なので、divmodのループを回して十進数化することにします。

Brainf**k版93B
,+[
 ** add (x plus 1)*6 **
 [->++++++<]
 ** sub y*5 plus 1 **
 ,[->-----<]>-
 ** divmod loop **
 [
  ** divmod **
  +[>[+>>>]<[>--------->+>]<<<-]
  ** make digit from reminder **
  -[----->+<]
  >++++++
 >-]
 ** print loop **
 <[ .[-] <<]
 ** pass thru a newline **
 ,.
,+]

ちょっと変則的なのはdivmodの部分で、予め+1してから処理を行い、10で割った商は+1、余りは-9された状態でセルに保存されます。なので、ループとしては商が1になったところが終了地点となります。

Whitespaceでの解法(94B)

Whitespaceは…。
本当に、素直に z=6x-5y+261 を計算しているだけなので、特に言う事はありません。
なお、ループはEOF時例外で異常終了させられるので、特に終了判定は必要ありません。

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

Whitespace-stn版94B
nsssnnstnsssttsntssnnstnssststntssntsstssstssssststntssstnstnstntnssnsnsnnssnsssnsnstntstttntn

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

アセンブリコード
# メインループ
mark MAIN       # nss,s,n(+0)
  # x入力と6倍
  call GETC     # nst,,n(null)
  push 6        # ss,stts,n
  mul           # tssn
  # y入力と5倍分の減算
  call GETC     # nst,,n(null)
  push 5        # ss,stst,n
  mul           # tssn
  sub           # tsst
  # 差分補正と出力
  push 261      # ss,stssssstst,n
  add           # tsss
  puti          # tnst
  # 改行の読み込み・出力
  call GETC     # nst,,n(null)
  putc          # tnss
  jump MAIN     # nsn,s,n(+0)

# 1文字入力用サブルーチン
mark GETC       # nss,,n(null)
  push 0        # ss,s,n
  dup           # sns
  getc          # tnts
  retr          # ttt
  ret           # ntn

Jellyfishでの解法(25B)

Jellyfishについては、以前の記事Jellyfish(esolang)の紹介をご覧ください。
テスト実行は TIO というところでできるようです。

今回、入力データが数値解釈できないのでどうしたものかと思ったのですが、関数dを使うと「文字列の文字コードをn進数の各桁として数値変換する」という処理ができることに気付き、こちらを活用しました。
しかも、「文字コードとしての各桁は0~n-1の範囲になければならない」という制約もなくガバガバ親切仕様です。なので、例えば n=6 で0aを変換すると、48\times 6+97=385と計算してくれます。

そこで以下のように、各行に対し z=(6x+y)-6(0x+y)+261を計算し、一括出力するコードを実装しました。

Jellyfish版25B(最終行改行なし、入力は10行固定)
P
+261
-dS
*6
d LJr10
0 0

要点を掻い摘んで説明すると、以下のように処理を分担しています。

  • 10行分の入力
    コード南東の L のブロック ( 南が 0、東が Jr10 の2引数 )
    これで各行の文字列がリストとして扱われ、以降の計算は全てベクトル演算として一括に行われます。
  • 6x+yの計算
    3行目の d のブロック ( 南が 6、東が S を経由し、上記 L のブロックを参照 )
  • 0x+yの計算
    コード南西の d のブロック ( 南が 0、東が上記 L のブロックを参照 )
  • (6x+y)-6(0x+y)+261の計算
    コード中の *,-,+ で、それぞれ6倍、減算、差分調整が行われます。
  • 出力
    コード北西の P が、南の + により調整の完了したリストを、空白区切りで一括出力します。

終わりに

私の守備範囲はesolangに分類されるので、なかなか参加者の方も手を出し辛かったようですが、組めるとアドバンテージになり、かつ、爽快なところなので、是非取り組む人が増えると良いなと思います。

Discussion