👊

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

2022/05/17に公開

はじめに

背景

TSG Live!8 コードゴルフ挑戦してみた(day2) に引き続き、見逃したday1のお題についても挑戦してみます。
day1の時は、競技者が選べる言語の中にWhitespace,Jellyfishは入っていなかったので、Brainf**kのみとします。
なお、イベント情報については、上記day2の記事をご覧ください。

1日目

問題

次のような問題でした。

  • 入力はM.からなる長さ30の文字列+改行
  • 文字列の先頭は.M、最後尾はM.である
  • nマス目に爆弾があるならn文字目はM
  • nマス目に爆弾がないならn文字目は.
  • それぞれのマスについて、そのマスおよび隣接マスにある爆弾の個数を出力する。
  • 出力のスペースや改行は無視される。
    ※余談ながら、day2 の問題でも別に区切り文字出力は必要では無い気がしますので、改行出力分の文字数が縮められるはずです。

例:
入力: .M..M.MMMM....M.MM..M.MMM...M.
出力例: 111112233210011222111223210111

方針

動画の解説で、既に色々な方針が説明されており、例えば「M.を数字の桁30と見做して数値解釈し、×37する(末尾は切る)」というのは、言語によってはおそろしく短く実装できそうでした。
想定解のPythonで45Bでしたが、Rubyだと以下の31Bが考えられます。

解説の方針(Ruby31B)
p gets.tr("M.","30").to_i*37/10

しかし、ご存知の通りBrainf**kにそのような機能はネイティブには組み込まれていません。なので、愚直に「Mかどうか」の個数を記録していく方針としました。

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

TSG! LiveでのBrainf**k処理系は、day2の記事と同様、8bitセル、EOF=-1(255)、wrap-aroundあり、負の番地ありという前提で考えます。

まずは具体的な処理の内容ですが、Mかどうかは文字コードの偶奇で判断できるため、以下のような疑似コードをもとにしました。
※先頭が . なため、1文字目はただ捨てるだけで文字数分(改行含む)のループを回して対処できるのが嬉しいところです。

Brainf**k版の疑似コード
x=y=z=0
$stdin.getc
while c=$stdin.getc
  if c.ord.odd?
    x+=1; y+=1; z+=1
  end
  print x
  x,y,z=y,z,0
end

そしてBrainf**k版が次のコードです。

Brainf**k版50B
** 1文字読み捨て後入力ループ **
->,,+[
 ** 偶奇判定 **
 +[+[>]<+]
 ** 奇数時のみカウントアップ(3セル分) **
 <+[<+<+>>>]
 ** 数字化および出力 **
 -[-----<+>]<---.[-]
->,+]

一番の工夫は、実質8文字で済んでいる偶奇判定です。
ループ毎に判定対象は+2されていくのですが、元の数が偶数か奇数かによって、ループ位置にズレができます。
この判定を行う際、先に左に -1 のセルを設定しておくのが前提です。
※次図参照

これにより、次の <+[<+<+>>>] で、元が偶数なら残っていた -1 が 0 に変化するだけで追加処理なし、元が奇数なら x+=1 相当が真判定も兼ね、y,z も順次増加させることになります。

後は +48 すれば数字化できるので、出力すれば終わりです。
ループの次に進む前に、偶奇判定用の -1 をセットしておくのを忘れずに。

終わりに

TSG Live!のコードゴルフは、各言語で短時間に解が書けるよう、手軽でかつ工夫も考えられる、なかなか手頃な問題設定が考えられています。Brainf**kのような一見とっつきにくい言語をマスターする足がかりにも丁度良いのではないでしょうか。

Discussion