JOI ソートをBrainFuckで解く - APCC：パソコン部のブログ

JOIソート(JOI 2020/2021 一次予選 (第1回) 第2問)をbrainfuckで解いていきます。

この記事では「brainfuckの各文字の意味するところ」を理解している想定しています。if文の書き方などの基本的な法則に関しては文中で補足しますが、各文字の意味するところがわからない方はWikipediaなどを眺めるといいかも知れません。

BrainFuckは比較的文字列操作に強いです。 JOI 2020/2021 一次予選 (第1回) ではAよりBのほうが解きやすいかも知れません。

（Aは読めばわかると思うんですが、数値の受け取りとソートさえやってしまえば大丈夫で多倍長もいらないのでライブラリ貼るだけみたいなところがありますが、BrainFuck的に面白くないですよね）

https://atcoder.jp/contests/joi2021yo1a/tasks/joi2021_yo1a_b

さて、この問題でやらなきゃいけないことは大きく以下の3つです。

Nを読み捨てる
Sに含まれる各文字をカウントする
出力する

さて、順番に見ていきましょう。

1.Nを読み捨てる

Sを読み取る方法には「改行を待つ」やり方と「Nの回数文字取得する」のに種類がありますが、困ったことにNは10進表記された状態で与えられるので扱うのが面倒です。

ということでNの情報は無視してしまいましょう。

さて、「〇〇が来るまで無視」の書き方ですが、ループなのでとあえず角括弧と入力を書きます。

[,]

さて、改行（0x0A)が来たら次に進んでほしいです。

BrainFuckのループはポインタの指す先が0だと終了するので、10を引くことでこの機能を実現できます。

+[,----------]一行読み捨てる(=LFが来るまでループ)

さて、次に入力の解釈を実装していきましょう。

BrainFuckは0の場合になにかするより0でない場合になにかするほうが得意なので、「Jでない場合」のようなコードを書くことを考えます。

今回は「一旦全部数えておいて、該当しない文字のカウンタは引いておく」ということをしていきます。

,>>>+>+>+
<<<<<

入力値のすぐ近くにカウンタを置くと後で困りそうなので作業用に少しメモリを空けておきましょう。

入力にJが含まれるか検出します。いきなり判定すると入力された値を破壊してしまうので一旦値をコピーしておきます。

[>+>+<<-]

このコードの実行後のメモリの内容は以下のようになります。

（0）（入力された値）（入力された値）（1）（1）（1）

（1）はそれぞれ左から順にJ,O,Iのカウンタです。初回実行時なので1が入っています。

「入力された文字がJでなければ3番地をデクリメント」を実装しましょう。

まずはJを意味する74回値をデクリメントします。

>>
----------------------------------------------------------------------
----

次はif文です。まずはWhileを書きましょう。

  [Jでなければ
    Jカウンタを1減らす
    >-<
  ]

これだと無限ループするので、Whileが落ちるように0を代入します。

  [Jでなければ
    Jカウンタを1減らす
    >-<
    if文なので繰り返し実行されないように0を入れておく
    [-]
  ]

[-]は0を代入するコードです。多分一番有名レベルのBrainFuck構文です。

同様にO,I,改行も判定していきましょう。

値のコピー
  <[<+>>+<-]
  >
  Oかどうか判定
  ----------------------------------------------------------------------
  ---------
  [Oでなければ
    Oカウンタを1減らす
    >>-<<
    if文なので繰り返し実行されないように0を入れておく
    [-]
  ]
  <<
値のコピー
  [>+>+<<-]
  >
  Iかどうか判定
  ----------------------------------------------------------------------
  ---
  [Iでなければ
    Iカウンタを1減らす
    >>>>-<<<<
    if文なので繰り返し実行されないように0を入れておく
    [-]
  ]
  >
  改行かどうか判定
  ----------
  [
    改行でないならループから脱出しないようにゴミを入れておく
    <<->>
    if文なので繰り返し実行されないように0を入れておく
    [-]
  ]

値のコピーの挙動がおかしなことになってますが（もっとたくさんメモリ確保しとけばよかった…）落ち着いて読めば読めると思います。

あとはこれをループにします。開始時にゴミを入れないと速攻でループが終了してしまうので気をつけましょう。

+[,----------]一行読み捨てる(=LFが来るまでループ)
+ゴミを入れておく
[入力ループ開始
,入力の受け取り
>>>+>+>+

最後は出力です。JOIを表示するためにメモリに(74)(79)(73)を入れておきましょう。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++

あとはメモリのカウンタを減らしながらJ、O、Iを出力しましょう。

>[<<<.>>>-]J
>[<<<.>>>-]O
>[<<<.>>>-]I

これで全てです。お疲れ様でした。

この記事の内容で解ける問題は結構多いと思うので、よければチャレンジしてみてください。楽しいBrainFuckライフを！

コードのリンクを貼っておきます。改行判定部分のコメントミスってますね。ごめんなさい。

https://atcoder.jp/contests/joi2021yo1a/submissions/24599607

コメントする コメントをキャンセル

コメントするコメントをキャンセル