はじめに
AtCoder の 2025 年版言語アップデートにて、Befunge-93 が追加される予定です。
https://atcoder.jp/contests/language-test-202505
そこで、今回は Befunge を使って AtCoder Beginners Selection の 11 問1を解いてみました。
Befunge とは
Befunge とは、コンパイル困難な言語として Chris Pressey によって 1993 年に開発されたプログラミング言語です。
「2次元グリッド上にコードを配置し、命令ポインタが上下左右に移動しながら命令を実行する」「自身のコードを書き換えるような命令が用意されている」といった特徴があります。
実際にコードを実行すると以下のようになります。
ポインタが上下左右に動きながら、中央の文字が書き換えられているのがわかります。
言語仕様
AtCoder のジャッジでの挙動を元に解説していくため、他の環境とは異なる仕様になっている部分もあると思われます。
正確な Befunge の仕様は Wikipedia や Esolang wiki をご参照ください。
コードエリア
- コードの長さは $25$ 行 $80$ 列で固定2
- 左上端を $0$ 行 $0$ 列目とする
- 提出したコードの足りない部分は
- 値は 32bit 符号付き整数として管理される
- 命令
pで ASCII コードの範囲外の値にも書き換えることができる
- 命令
スタック
- 値を 64bit 符号付き整数で格納するスタックが 1 つだけ用意されている
- スタックが空のときに値を取り出そうとしたときは $0$ が得られる
命令
演算
-
+-*/%: スタックから値を $y, x$ の順で取り出し、$x - y$ などを計算した結果をスタックに追加する -
`: スタックから値を $y, x$ の順で取り出し、$x \gt y$ なら $1$ を、そうでなければ $0$ をスタックに追加する -
!: スタックをポップして、その値が $0$ のときは $1$ を、それ以外のときは $0$ をスタックに追加する
実行
-
<v^>: 実行の向きを変える -
?: 実行の向きをランダムな方向に変える -
_|: スタックをポップして、その値が $0$ のとき実行の向きを 右/下 にし、それ以外のとき実行の向きを 左/上 にする- ポップした値がスタックの一番上から消える点に注意。後の処理でその値を使いたい場合はあらかじめ
:などで複製しておく必要があります
- ポップした値がスタックの一番上から消える点に注意。後の処理でその値を使いたい場合はあらかじめ
-
- 命令が定義されてない文字も同様に何もしません
-
#: 次の命令を無視する- 次の命令が
- 次の命令が
-
@: プログラムの実行を停止する- 最後にこの命令を実行しないと、プログラムが無限に実行され続けて TLE になります
リテラル
-
0～9: その数値をスタックに追加する -
": 次の"に辿り着くまでコードエリア上の値をスタックに追加する
入出力
-
&: 入力から値を 1 つ読み取り、スタックに追加する- 64bit 符号付き整数の範囲を超える値が入力された場合は、64bit 符号付き整数の最大値/最小値が追加されます
-
~: 入力から文字を 1 つ読み取り、その文字の ASCII コードをスタックに追加する- 入力を全て読んだ後に
~を実行すると、$-1$ がスタックに積まれます
- 入力を全て読んだ後に
-
.: スタックをポップしてその値を数値として出力し、その後- 「空白区切りで出力せよ」といった問題でいちいち空白を出力しなくても自動的に空白区切りになります
- 必ず数値の後に空白が出力されるため、問題によっては文字に変換して出力する必要があるかも……
-
,: スタックをポップしてその値に対応する文字を出力する
スタック
-
:: スタックの一番上の値を複製する -
\: スタックの上位 2 つを入れ替える -
$: スタックの一番上の値を削除する
コード操作
-
p: スタックから値を $y, x, v$ の順で取り出し、コードエリアの $y$ 行 $x$ 列目の値を $v$ に変更する- スタックが 64bit 、コードエリアが 32bit と型が違うため、キャストされてコードエリアには $v$ の下位 32bit しか記録されません
-
g: スタックから値を $y, x$ の順で取り出し、コードエリアの $y$ 行 $x$ 列目の値をスタックに追加する- 例えば 2 行 1 列目の値を取り出したいときは
12gの順で実行します - 内部的には 1 次元の配列で管理されているため、
99*(=81)1gとしても 2 行 1 列目の値が取得できます3
- 例えば 2 行 1 列目の値を取り出したいときは
実行環境
問題を解くにあたって、デバッグには HTML5 Befunge93 Interpreter を、実行テストには AtCoder のコードテストを利用しました。
HTML5 Befunge93 Interpreter は AtCoder のジャッジと一部動作の異なる部分があるのでご注意ください。
- 命令
p,gで指定する行・列の順番が逆 -
pで値を書き込んだとき、その値を $\bmod 65536$ したものが書き込まれる - スタック内の値は JavaScript の Number 型
- ……etc
実際に解いてみる
0. PracticeA - Welcome to AtCoder
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65718451
&&&++. > ~ : 1+ v
^ , _ @
和を求める部分は 3 回数値を受け取って足すだけで OK です。数値受け取り & は改行区切り/空白区切りどちらでも機能するのでラクチン。
文字列を受け取る部分が少し厄介です。文字列の長さが与えられないため、実際に受け取った文字を見ながら終点を判定する必要があります。
今回は、入力を最後まで受け取った後さらに ~ で文字を受け取ろうとすると $-1$ がスタックに積まれるのを利用して判定しました。
1. ABC086A - Product
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65699062
&&*2%v
"Odd"_"nevE",,,,@,,,
問題文の通りに実際に積を計算して、偶奇で左右に分岐させます。
奇数のとき 2 行目で左に移動しながらコードの左端に辿り着きますが、左端からさらに左に移動した場合は同じ行の右端に移動します。いわゆるトーラス形状ですね。
2. ABC081A - Placing Marbles
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65695562
&9%.@
数値として受け取って $ \bmod 9 $ するだけです。先頭に余計な 0 がついていてもそれを取り除いて数値として読んでくれます。
3. ABC081B - Shift only
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65736723
v
& > 00g .@
v _^# : -1 <
>0&v
> :2% #v_ 2/ \ 1+ \
>$ :00g ` #v_ 00p ^
>$ ^
ループや分岐が入ってきて一気に Befunge らしいコードになってきました。
分岐の命令だけでは _ の左右か | の上下にしか分けることができませんが、> #v_ と書くことで右と下への分岐をコンパクトに書くことができます。
この問題をスタックだけで解くのは厳しかった4ので、コード上の座標 $ (0, 0) $ に答えをメモしています。
$ (0, 0) $ の値を初期化していないためコード内の文字 v が最初に入っていますが、これは数値としては $ 118 $ で、解の上限を上回っているため問題なく AC できます。
4. ABC087B - Coins
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65737334
&&&&v
v> 30p 20p 10p 00p
v > 552** :21p 2* :11p 5* 01p 0 90p
> 90g.@
> 20g v -1 _^# :g22 $<
> 22p 10g v -1 _^# :g21$ <
< > 12p 00g v -1 _^# :g20 <
90g 1+ 90p ^ > 02p 22g 21g * 12g 11g * 02g 01g * + + 30g - #^ _
うまくやれば多重ループを減らせますが、今回は愚直に 3 重ループで書きました。
== のような比較演算はありませんが、引き算 - した結果が $0$ になるかで判定可能です。（右下端、=X?の部分）
最終行の答えに 1 を足す部分が右端からはみ出してしまったので、左側に続きを書いています。1 行の文字数上限 80 文字は意外と厳しい……
5. ABC083B - Some Sums
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65742290
&&& 25* 50p 1+ 20p 1- 10p 0 00 p v > 00g.@
v : p090 < _^# : -1 <
_v#: < /g05 p09 +g09 %g05 :
>$ 90g 10g ` #v_ ^
> 20g 90g ` #v_ ^
> : 00g+ 00p ^
比較演算子が ` の $\gt$ しかないため、$\ge$ の比較をしたいときは一工夫必要です。今回は $ s \ge A $ の代わりに $s \gt A-1 $ としましたが、$ \neg (s \lt A)$ とした方が自然ですね。5
6. ABC088B - Card Game for Two
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65720829
v
//00: temp, 0x:1-51, 1x: 52-100, 20: 52, 21,22: tempxy, 23: 100
v
> 69*2-02p 455**:32p v
g00 0 p00 _ v# :< -1g00 p /g20 \ %g20 :
&
: & _ v# :< -1 pg21g22 +1 gg21g22 p22p21 /g20 \ %g20
> $$ 0 00p v
+1 g00_ v# -g23 < g00 $< v g /g20 \ %g20 : p00:
\ g00 -1 _ ^# :<
> 32g 00p v
- p00 -1 _ v# : g00 <
>$.@
恐らくこの 10 問の中で一番実装が難しいです。ソートする部分を自前で実装する必要があります。
定番はバブルソートと思いますが、Befunge は 1 行に 80 個しかデータを置けないため、100 個のデータを比較ソートするのも実装がそこそこ面倒です。そこで今回は代わりにバケットソートを使って実装してみました。
整数 $ n $ の出現回数を座標 $(n \bmod 52, n/52)$ へ記録することにして、記録に使う部分を全て値 $ 0 $ に初期化 (6 行目) → 出現回数をカウント (8 行目) → 整数 $ n $ を昇順に見てそれぞれ出現回数分スタックに積む (10 行目) という流れで、$ a $ をソートしたものがスタックに乗るようにしています。
最後にソートされたデータを交互に足し引きを繰り返す部分ですが、降順かつ末尾に $ 0 $ が並んだ数列 $ a $ に対して ans ← a[i] - ans を $ 100 $ (偶数)回実行することにより、カウントや偶奇による分岐をサボりました。6
7. ABC085B - Kagami Mochi
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65717630
v
& //00:ans, 0x:1-51, 1x: 52-100, 20: 52
v > 00g.@
> 000p 69*2-02p v _^# :-1 < <
> & :02g/12p 02g%22p 22g12gg2% #^ _ 122g12gp 00g1+00p ^
先ほどと同様に、整数 $ n $ の出現済みフラグを座標 $(n \bmod 52, n/52)$ に記録していきます。
初めて出現した整数に出会う度に答えに 1 を足すだけなので、先ほどの問題よりもやることが少ないです。
8. ABC085C - Otoshidama
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65722186
vNYmgs // 01: N, 02: Y, 03: m, 04: g, 05: s
> 01-:.:..@
> & 10p &8/5/5/5/ 20p 9 40p v
v p04 -1 g04 _ ^# g04 < < <
v> 20g 10g - 40g 4* - : 0 \` #^ _ : 9% #^ _ 9/ 30p
v>> 52* 10g * 5 40g * - 20g - : 0 \` #^ _ : 9% #^ _ 9/ 50p
> 30g. 40g. 50g. @
4 問目の ABC087B - Coins と違って、こちらではしっかり連立方程式を解く方法で実装してみました。
シンプルに 2 重ループで解いても間に合うとは思います。（未検証）
9. ABC049C - 白昼夢
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65723621
<_v#+1:~
>$$ v
> "SEY",,,@
vp06p05p04p03p02p01p00 _^# : <
>"dream" 00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 60g 50g ^
v > $ > $ > $ > $ >
>"dreamer" 00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 50g-#v_ 60g-#v_ ^
v > $ > $ > $ > $ > $ > $ >
>"erase" 00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 60g 50g ^
v > $ > $ > $ > $ >
>"eraser" 00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 50g-#v_ 60g ^
v > $ > $ > $ > $ > $ >
>"ON",,@
スタックなので後ろから処理する操作は実装しやすいです。
見ての通り同じような処理をしている部分が多いので、for ループのように書いたり移動方向の >v<^ を書き換えたりして圧縮するのも面白そうです。
10. ABC086C - Traveling
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65723944
vNtxytxydt
& @,,,"Yes"<
> 020p 030p 040p v
v _ ^# : < -1 <
v> &50p &60p &70p
> 30g 60g - : 0 ` #v _ 0\- v
> > 40g 70g - : 0 ` #v _ 0\- v
v > > + 80p
v> 50g 20g - 90p
v> 80g 90g - 2 % #v _
> 80g 90g ` #v _ 50g20p 60g30p 70g40p^
@,,"No"<
今更ですが、コード上の処理が走らない部分には自由に文字を書けます。
このコードでは 1 行目に変数を $N, t',x',y',t,x,y,d,dt$ の順で格納する予定であることをメモしています。
スタックをあまり使わず、変数のような感覚で命令 p g を使うようにするとかなり実装しやすくなります。代償として、Befunge らしさが損なわれます。
おまけ ABC244C - Yamanote Line Game
精選 10 問ではありませんが、インタラクティブ問題でも動かしてみたくなったのでこちらの問題も解いてみました。
インタラクティブ問題では 出力の末尾に LF (10 進で 10) を入れ忘れると TLE する ので気をつけましょう。
提出 : https://atcoder.jp/contests/language-test-202505/submissions/65830775
v (n, 0): data area : 31bit x 80 = 2480bit
v (n, 1): 2^n
v (n, 2): 0: N, 1: loopcount, 23: nb
> & 02p 1 0 v +1 g21 *2 p1g21 : <
> : 12p 48* - |
> : 0\ 0p 1+ v $ <
| - **852 : <
v p21 $ < : g21 $ <
> 12g 1+ :12p :: 48*1-/ 22p 48*1-% 32p 22g0g 32g1g / 2% |
^ p0g22 + g1g23 g0g22 p23 %-1*84 p22 /-1*84 : _@# : & ,*25 . <
$ N $ が最大 $ 1000 $ と大きく、$ 2N+1 = 2001 $ 個の整数の使用フラグを $ 80 \times 25 = 2000 $ 文字しか使えないコード領域に記録するには工夫が必要です。
今回は 1 つの座標に 32bit の情報を入れられることを利用して、整数 $ x $ の使用フラグを $ x/32 $ 文字目の $ x \bmod 32 $ 桁目に保存するような方法で実装しました。7
おわりに
難解プログラミング言語というと簡単な計算でも実装が難しくわかりにくいコードになる印象でしたが、Befunge は数値の入出力と基本的な演算が命令として用意されていて、比較的書きやすく感じました。
また、処理を 2 次元グリッド上に配置していくのは shapez8 などの工場建設ゲームを彷彿とさせて、とても面白かったです。
参考文献
- Befunge について
- Befunge 実行環境について
- AtCoder Beginners Selection を難解プログラミング言語で解いてみた記事たち