Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ASURA-the-great-robot

【><>】AtCoderに登録したら解くべき精選過去問 10 問を難解言語 Fish ><> で解いてみた① ><>とは何か編

Last updated at Posted at 2024-10-25

この記事では ><> の簡単な使い方の説明をしております．
実際に問題を解くのは次の記事です
② Practice～第3問編
③ 第4問～第7問編
④ 完結編

:tropical_fish: はじめに

こんにちは，みなさんAtCoderをご存じですか？（唐突）
AtCoderとは競技プログラミング（与えられた問題を解くプログラムを書く速さや正確さを競う競技）を開催しているサイトです．
昔に入茶してから飽きてしばらくやっていなかったのですが，最近やる気が再燃して，現在入緑目指して勉強中です．

ある日，AtCoderの使用可能言語一覧を見ていたところ，不思議なものを見つけました．

image.png

なんだこのアスキーアートは...

調べた結果，どうやらこれは><>という難解プログラミング言語であることが分かりました．（><>とかいてfishと読ませるようです．この記事では><>と書くことにします）

難解プログラミング言語とは，

難解プログラミング言語 (なんかいプログラミングげんご)とは、
意図的に読解が困難なように設計されたプログラミング言語である。英語では、Esoteric programming language （略してesolangとも）と言われる。

基本的には、実用性を目指したものではなく、ジョークのプログラミング言語の一種で、いわゆるハッカーの間では、この種のジョークはたしなみとみなされており、難解プログラミング言語に区分されるプログラミング言語はいくつも作られてきた。
Wikipediaより引用 難解プログラミング言語

とのことです．ハッカーのたしなみ...?
有名なところだとBrainf**k（ブレインフ〇〇ク）やWhitespaceがありますね．
AtCoderの使用できる言語とライブラリの一覧で確認したところ，AtCoderで使用できるesolangはBrainf**k，><>，Whitespaceあたりがあるようですね．（ざっと確認しただけですので確認漏れがあるかもしれません...）

さて，そんな><>ですがAtCoderで使用者がほとんどいません．AtCoderの適当なコンテストで「すべての提出」「言語：><>」で検索すれば使用者の少なさが分かるかと思います．

というかそもそも><>について説明している日本語の記事がほとんどありません．令和の世にこんなに検索しづらいプログラミング言語があるのかと驚くレベルです．
Qiitaで調べてみてもほとんどがFish (Unixシェル)の話でした．

なぜこんな言語がAtCoderに追加されたのか甚だ疑問ではありますが，調べていく中で愛着がわいたので><>を使って「AtCoder に登録したら解くべき精選過去問 10 問」を解いてみることにしました．

:fish: ><> Fish とは

いきなり問題を解き始めても，ここまでマイナーな言語だとコードを読んでも理解できる人が少ないと思いますので，まずは簡単な使い方の説明をしたいと思います．

ただ，私も><>に触れてからまだ1週間程度の"ぴちぴちの"新米なので，><>の上級者の方（いるのか?），あるいは><>界隈の方（あるのか?）がいらっしゃいましたら，間違いのご指摘や説明の補足などしていただけると幸いです．

なお，英語が得意な方でしたら，以下のWikiを読まれるとだいたい分かるかと思います．
というか，以下の解説はほとんどこのWikiを翻訳して説明を追加しただけです．

Hello ><> !

><>はHarpyonという方が2009年に開発されたもので，Befungeという言語に影響を受けているようです．Befungeは"コンパイルを可能な限りしにくくすることをコンセプトに開発された"言語（Esolang wikiから引用）らしいです．実際に><>とBefungeは自分自身を書き換えられる点や，スタックを用いる点などよく似てます．

><>やBefungeが他の言語と違うところはプログラムの命令は全て1文字であらわされ，ソースコードが2次元のグリッド上に配置されるところです．
また，プログラムは上から下に実行されるのではなく，グリッドの左上$(0,0)$から始まって右向きに進んでいき，命令によって方向転換することもあります．
他にも，変数などの概念はなくスタックを用いて値を取り扱います．

「どういうこと？」と思った人も多いでしょう，以下に><>でHello Worldを出力する様子を示します．

hello1.fish
!v"Hello World!"r!
 >l?!;o

コードをグリッド上に配置したもの
image.png

実行した様子
hello-fish.gif

ご理解いただけたでしょうか？先ほどのプログラムはこのように書くこともできます．

hello2.fish
"!dlroW" v
v"Hello "<
>l?v;
^ o<

コードをグリッド上に配置したもの
image.png

実行した様子
hello-fish.gif

><>の面白さが理解いただけたでしょうか．
ポインタがちょこまか動き回りながら命令を実行するのが，><>の醍醐味です．

><> の仕様と命令

><>の仕様と命令について，サンプルコードを示しながら説明していきます．
><>にはオンラインの実行環境がいくつかあるので，以降はお手元の環境でも実行していただくとより理解が深まると思います．

仕様

先ほど軽く触れましたが，より詳細に説明をします．

  • プログラムの命令は全て1文字で表現され，コードは長方形のグリッド上に配置されます（これをコードボックスcodeboxと呼びます）
  • コードボックスの大きさは「行数の最大値×列数」になります
  • ><>には変数の概念がないですが，代わりにスタックがあります．スタックには数字を追加したり，追加した数字を用いて計算したりすることができます．スタックは空の状態から始まります
  • プログラムは命令ポインター(instruction pointer)によって実行されます
  • はじめに命令ポインターは一番左上のマスから右方向に命令を実行していきます．もしコードボックスの端に来てしまった場合，さながらマリオブラザーズのように反対側にジャンプします
  • プログラムは命令;が実行された場合終了します
  • 命令に存在しない文字を実行するとエラーを出します，また空白 は何も処理をしません
  • 実行時エラーが発生した場合，プログラムは強制終了し，エラーの内容にかかわらず "Something smells fishy..."（なんだか怪しいぞ...）と表示されます

エラー文が1種類しかないというのはいかにもジョーク言語っぽいですね．ユーモアがきいてます．これぞハッカーのたしなみですね． なお，AtCoderをやる上でエラーの原因が分からないのはちゃんと致命的です．気を引き締めていきましょう．

方向変更< > ^ v・ミラー\ / | _ # x

先ほどご覧いただいたとおり，><>のコードは命令を実行する方向を縦横無尽に変化させることができます．
< > ^ vはそれぞれ左，右，上，下を表しており，この命令を踏むと命令ポインターの移動方向が矢印の向きに変化します．

以下にサンプルコードを示します．(再掲にはなりますが，;でプログラムが終了します．)

spiral1.fish
>  v
> v 
 ;< 
^  <

コードボックス
image.png

実行した様子
image.png

ミラー\ / | _ #は命令ポインターの方向を鏡のように跳ね返します．ミラーを使えば上記のプログラムは以下のように書き直せます．

spiral2.fish
>  \
/ \ 
 ;/ 
\  /

コードボックス
image.png

実行した様子
image.png

なお，| _は命令ポインターをそれぞれ左右，上下に跳ね返します．対応していない方向からこれらの命令を踏んだ場合は何もしません．#は| _を複合したような機能を持っており，上下左右すべての方向に対応しています．

xは少し特殊で，ランダムな方向に命令ポインターを跳ね返します．

入出力 i n o

C++におけるcin，Pythonにおけるinputにあたる命令がiです．1文字入力を受けとってスタックに追加します．入力は全てchar型で受け取ることに注意してください．（つまり，1を入力すると，49がスタックに追加されます．ASCIIコード表を参照してください）
同様にcout，printに対応するのがnとoです．それぞれ数値，文字の出力に対応しております．スタックの一番上にある数字を取り出して，それを出力します．
以下にサンプルコードを示します．

io.fish
iino;
input
00
output
480

実行した様子
io-fish.gif

1回目のiで0を受けとりスタックに48を追加，2回目のiでも同様に0を受けとりスタックに48を追加．
nでスタックの一番上の48を出力，次のoでASCIIコードにおける48の0を出力します．

スタックに数字・文字列を追加する 0～9，a～f，" '

変数がない><>においてスタック操作は大変重要です．0～9の整数はスタックにその数字を追加する命令です．また，a～fの命令は10～15をスタックに追加します．
" はもう一度 " を踏むまで，プログラムを文字として読み取りスタックに追加します． ' は " と同じ機能を持っています．

str_num.fish
12345nnnnn v
/          /
\"Hi!"ooo;
output
54321!iH

コードボックス
image.png

実行した様子
str-num-fish.gif

このプログラムでは1 2 3 4 5の順でスタックに追加し，上から順に5回nしたのち，'H' 'i' '!' の順でスタックに追加し，上から順に3回oしています．
スタックの一番上から出力されるので，Hi!と表示させたい場合は!iHの順でスタックに追加しなければならないことに注意です．とはいえ，これでHello World!ができるようになりましたね．

hello3.fish
"!dlroW olleH" oooooo oooooo;

スタックにさかさまに"!dlroW olleH"を追加し，12文字分 o することで文字を出力しています．

スタックの上から2つの数字を使って計算する + - * , %

先ほどの説明をうけて，「1729や-1をスタックに追加したい場合どうするんだ...?」と考えたのではないでしょうか．><>にはスタックに数字を追加する命令が0～fまでしかないので，それを超過する数やそれ未満の数を追加する場合は，0～fを足し合わせたりかけ合わせたりして表現することになります．

+ - * , %はそれぞれ，足し算，引き算，掛け算，割り算，余りを計算する命令です．一般的には割り算は/を用いますが，><>では/はミラーの命令なので代わりに,を使っています．そのため，私はしょっちゅう書き間違えます

スタックにA Bがあるときに+を実行すると，スタックの上から2つ(A B)取り出して，A+Bを新たに追加します．他の命令も同様です．もし，スタックに２つ以上の数字がなければ魚の匂いが漂います(Something smells fishy...)．なお，計算の命令以外でもスタックから値を取得する命令は，値を取得できない場合に魚の匂いを発するので注意してください．

また，割り算はfloatの割り算になります．つまり$5\div2=2$ではなく，$5\div2=2.5$となります．AtCoderをする上ではint型の割り算をしたいときのほうが多いので，先に余りを計算して引いておくなど工夫が必要です．
加えて，0除算でも魚の香りが漂うので注意してください．

calc.fish
01-n " "o ccc** 111** + n " "o aaa** 999** + n;
output
-1 1729 1729

実行した様子
calc-fish.gif

$0-1=-1$と，$12^3+1^3=1729$，$10^3+9^3=1729$を計算し，出力するプログラムです．
他の言語の感覚的に，$0-1$は0-1と書きたくなりますが，><>では01-と書きます．つまり$12^3$は12*12*12ではなく，ccc**です．

スタック操作 : ~ $ @ { } r l

><>ではスタックに数字を追加する以外にも様々な操作をすることができます．

  • :はスタックの1番上の数を複製します
  • ~はスタックの1番上の数を削除します
  • $はスタックの上から2つの数を入れ替えます．(ABCD-> ABDC に並び替えます)
  • @はスタックの上から3つの数を右にシフトします．(ABCD -> ADCB に並び替えます)
  • { }はそれぞれスタック全体を左・右にシフトします
  • rはスタック全体をひっくり返します．(ABCD -> DCBA に並び替えます)
  • lはスタックのサイズを，スタックに追加します．(スタックが空の時に実行すると0を追加します)

一気に説明してしまいましたが，変数の代わりにスタックを使う><>にとって，これらは非常に大切な命令です．がんばって覚えていきましょう．

さて，今回のサンプルコードはクイズです．
スタックに12345を追加した後，様々な命令を実行します．最終的にスタックがどうなるのかを考えてみてください．

quiz.fish
12345 @ ~ { ~ : } r $ l ;
答え

quiz-fish.gif

stack
3 5 3 2 4
  • 12345 最初の状態です
  • 12534 @で345 -> 534に右シフトされます
  • 1253 ~で4が消えます
  • 2531 {で全体が左にシフトします
  • 253 ~で今度は1が消えます
  • 2533 :で3が複製されます
  • 3253 }で全体が右にシフトします
  • 3523 rで全体がひっくり返ります
  • 3532 $で23 -> 32に入れ替わります
  • 35324 lでスタックのサイズ4が追加されます

スタック作成 [ ]

[命令を実行するとスタックの一番上の数を取り出し，取り出した値分スタックから数字を新しいスタックに移します．]命令を実行すると新しいスタックの数字を全て元のスタックに追加します．

これは実際のプログラムの動作を見た方が分かりやすいと思うので例を示します．

new_stack.fish
123456 4 [ r ] ;

new-stack-fish.gif

1 2 3 4 5 6 がスタックに追加されたのち，4を追加して[を実行したので，スタックの上から4つ(3 4 5 6)が新しいスタックに追加されます．その後rで順番をひっくり返し(6 5 4 3)，]でもとに戻したので，最終的にスタックの中身は1 2 6 5 4 3になります．

条件分岐 ? = ( ) ・スキップ !

><>にもif文があります．?はスタックの一番上の数を取り出し，それが0であれば次の命令をスキップします．0以外の数であれば通常通り実行します．

= ( ) はC++における== < > にあたります．スタックの上から2つの数を取り出し，条件を満たすならば1，満たさないならば0をスタックに追加します．= ( ) を実行した後 ? を実行すれば比較の結果に応じて処理を変えることができるようになります．

!は次の命令をスキップする命令です．?の後ろに置けば，0以外の数であれば次の命令をスキップ，0であれば通常通り実行するような，反対の処理を行うことができます．

less_than.fish
12(?;  22(?;  32(?;   ;

image.png

$1<2$なので一番最初の(で1がスタックに追加され，直後の?で;がスキップされずに実行されます．

greater_than.fish
12)?;  22)?;  32)?;   ;

image.png

$3>2$なので3番目の)で1がスタックに追加され，直後の?で;がスキップされずに実行されます．

さて，ここまでくれば一番最初に出したHello World!のプログラムが読めるようになっているはずです．一度戻ってどのような仕組みで実装されているか読み解いてみてください．スタックの長さを取得するl命令と?を組み合わせてスタックが空になるまでoしています．

レジスタ &

><>には変数が存在しませんが，1つだけ数字を保存して置ける場所があります．それがレジスタです．&を実行するとスタックの一番上の数字を取り出して，レジスタに保存します．レジスタに数字を保存してある状態でもう一度&を実行するとレジスタから数字を取り出して，スタックに追加します．
レジスタ・スタックともに空のときに&を実行すると魚の匂いが立ち込めます．

スタックを作成した場合，スタックごとに新しいレジスタが作成されます．

便利な反面，レジスタが空か空ではないかによって処理の内容が真逆になるので使用には注意が必要といえるでしょう．

register.fish
12345 & }} & ;

実行した様子

register-fish.gif

1 2 3 4 5を追加した後，&を実行して5をレジスタに保存します．2回右にシフトして(1 2 3 4 -> 4 1 2 3 -> 3 4 1 2)，最後に5をレジスタからスタックに戻しています(3 4 1 2 5)．

ジャンプ .

.はスタックの上から2つの数字を取り出し，それぞれを横・縦のインデックスとして，コードボックス上のマスへ実行ポインターをジャンプさせます．ポインターの方向は変化しません．
また，ジャンプした地点の命令は実行されないことに注意してください．

jump.fish
21.
0123456>l?!;nv
       ^ o" "<

コードボックス

image.png

実行した様子

jump-fish.gif

$(2, 1)$にジャンプするプログラムです．$(2,1)$とは左上を$(0,0)$としたとき，右に2マス，下に1マス進んだ位置となります．今回だと0 1 2 3 4 5 6が書いてある行の2が書いてあるマスです．
ジャンプした地点は実行されないので2より後ろの命令から実行され，3 4 5 6がスタックに追加され，スタックが空になるまでnされます．

プログラムの読み込み・書き換え g p

><>ではなんとプログラムを実行中に書き換えることができます．

gはスタックの上から2つの数字を取り出し，それぞれを横・縦のインデックスとしてコードボックス上のマスを読込み，書いてある文字をスタックに追加します．
例えばスタックに0 5がある状態でgを実行すると，$(0, 5)$のマスに書いてある文字をスタックに追加します．iと同じで文字のASCIIコードを追加することに注意してください．マスになにも書いていない場合0が追加されます．（空白が書いてある場合は32(SPC)がスタックに追加されます）

pはスタックの上から3つの数字を取り出し，後ろの2つを横・縦のインデックスとして，コードボックス上のマスに先頭の数を書き込みます．例えばスタックに65 0 5がある状態でpを実行すると，$(0, 5)$のマスの書いてある文字をA(ASCIIコードで65)に書き換えます．
これはoと同じで，ASCIIコードに対応する文字を書き込みます．
gとは違いコードボックスの領域外にも書き込むことができ，領域外に書き込んだ場合コードボックスがそこまで拡張されます．例えば3×2の大きさのコードで0ffpを実行して$(15,15)$に0を書き込んだ場合，コードボックスは16×16まで拡張します．（AtCoder版のインタープリタはこの辺りの仕様が若干異なります．以下のサンプルコードもAtCoder上では動かないことに留意してください）

rewrite.fish
  "v"00p ";"0ap

実行前
image.png

実行後
image.png

実行した様子

rewrite-fish.gif

vと;を書き込むことでプログラムを終了させるサンプルです．
vを$(0,0)$，;を$(0,10)$に書き込んでいます．

実行環境

><>はコンパイルが困難な言語であるため，コンパイラではなくインタープリタを使って実行することになります．コンパイラとインタープリタの違いは以下の記事が参考になります．

esolang wikiに複数種類のインタープリタが紹介されていましたので，その中から使いやすいものを紹介します．

公式のインタープリタです．Pythonで作成されています．
a.fishを実行したい場合，python fish.py a.fishというコマンドで実行できます．

既に上で紹介しているオンラインインタープリタです．ブラウザで即座に使用することができるのでお勧めです．TypeScriptを用いて作成されているようです．

Rustで作成されているインタープリタです．私は使用していませんが，AtCoderで使用されているインタープリタはRustで作成されているらしいので，AtCoderを><>でやるならばこれを使った方がいいのかもしれません．

結びに

以上で><>の使い方説明は終了です．><>の魅力はわかってもらえたでしょうか？
私は「難解プログラミング言語は総じて命令が少なくて書きにくいもの」と思っていたので，こんなにも命令の種類が多く，書きにくい言語があるものかと驚きました．

次回からはAtCoderの精選過去問10の解き方の解説に移ります．

「><>のことはもうわかったからコードだけ見せてくれ」という人のために私が提出したコードを以下に掲載しておきますので，よかったら参考にしてください．

提出したコード

おまけ

調べてみたらEsolangでAtCoderの精選過去問10問を解く，といった内容の記事はQiitaそこそこ見つかりました．難解プログラミング言語にかける情熱を感じますね．

↓これはQiitaではないですが，有名な記事なので紹介しておきます．

AtCoderで使用できない言語でも，インタプリタを自作してソースを埋め込むことでAtCoderに提出できるようされているようです．すごい(小並感)．これぞハッカーのたしなみなのでしょうか...?

6
2
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?