AtCoder に登録したら解くべき精選過去問 10 問を Hexagony で解いてみた（言語解説編）

はじめに

drken さんの精選過去問 10 問を難解言語の Hexagony で解いてみました．難解言語の Whitespace で解いてみたに続いて難解言語編の第 2 弾です．

仕様がわからないと読み手もつまらないかなーと思って書いてたら，長くなってしまったので前後編に分けます．問題解説編はこちら

TL; DR

実質お絵描き

Hexagony とは？

Martin Ender 氏によって開発された言語で，言語名は Hexagon と Agony から成る造語です．

この言語では，ソースコードを六角形の盤面のように解釈します．

helloworld.hxg

   H ; e ;
  d ; Q 4 ;
 ; l ; r ; o
l ; ; o ; Q 2
 g 4 ; @ . >
  ; w ; < \
   ; P 0 /

スペースや改行を取り去っても実行には影響がありません．

helloworld-min.hxg

H;e;d;Q4;;l;r;ol;;o;Q2g4;@.>;w;<\;P0/

六角形の大きさはソースコード長によって変わりますが，正六角形となるように（必要に応じて）パディングがなされます．

命令の実行について

命令ポインタが 6 つ用意されており，最初はそれぞれ頂点を指しています．

   0 . . 1
  . . . . .
 . . . . . .
5 . . . . . 2
 . . . . . .
  . . . . .
   4 . . 3

任意の時点においてちょうど一つのポインタがアクティブで，実行開始時は 0 番のポインタがアクティブになっています．

実行の各ステップにおいて，まずアクティブな命令ポインタが指している命令が実行されます（それはそう）．その後，命令ポインタは一マスぶん移動します．移動の方向は，0 番は右，1 番は右下，2 番は左下，...と時計回り方向ですが，それを変える命令も用意されています．
各ポインタを一回ずつ進めたときの位置を示しておきます．

   . 0 . .
  . . . . 1
 5 . . . . .
. . . . . . .
 . . . . . 2
  4 . . . .
   . . 3 .

ここで，0 番のポインタが元々 1 番のポインタが指していたところに達した場合でも勝手に進行方向が変わる訳ではないことに注意が必要です．

ポインタが六角形の外に飛び出たときは反対側の辺の対応する位置から戻ってきます．以下にその例を示します．

   . . . .
  a b c d e
 . . . . . .
. . . . . . .
 f g h i j k
  . . . . .
   . . . .

   . a . .
  . . b . .
 g . . c . .
. h . . d . .
 . i . . e .
  . j . . f
   . k . .

   . . k .
  . . j . .
 . . i . . e
. . h . . d .
 . g . . c .
  f . . b .
   . . a .

   . g . .
  . h . . a
 . i . . b .
. j . . c . .
 k . . d . .
  . . e . .
   . f . .

a からアルファベット順に k の位置まで移動し，その後は a に戻ってきます．

特殊なのが以下のような場合です．

   h i j k
  . . . . .
 . . . . . .
a b c d e f g
 . . . . . .
  . . . . .
   H I J K

g の次にポインタが行く場所は（後述する）メモリポインタの状態によります．移動する時点でメモリポインタが指している値が正の場合は H へ，0 または負の場合は h へ移動します．

k や K の次はどちらも a へ移動します．

メモリについて

メモリの構造も六角形が関係しています．

       / \ / \ / \ / \
  ... |   |   |   |   | ...
     / \ / \ / \ / \ / \
... |   |   |   |   |   | ...
     \ / \ / \ / \ / \ /
  ... |   |   |   |   | ...
       \ / \ / \ / \ /

AA で表現するのがやや難しいですが伝わっていますか？ この / や | の一本一本が記憶領域を表しています．（仮想的には）これが無限に広がっていて，必要に応じてその任意の辺に任意長の整数値を割り当てることができます．また，初期値は 0 であることになっています．

メモリポインタについて

命令ポインタが 6 つあるのに対して，メモリポインタは 1 つしかありません．メモリポインタはメモリ上のある一辺および向きを保持しています．「どこどこの位置の | の辺・上向き」とか「どこどこの位置の / の辺・右上向き」といった具合です．

向きは，値自体には影響しませんが，各命令でメモリ操作をする際に影響してきます．

命令セット

この言語は，ASCII の範囲の印字可能文字全てが役割を持っています．

デバッグ用

記号	役割
`	実行時には除去されるが，ソース上でこれに続く記号が実行されるたびにデバッグ情報を出力する．

特殊文字

記号	役割
.	何もしない．パディングの際にも用いられる．
@	プログラムを終了する．

英数字

記号	役割
[A-Za-z]	メモリポインタが指す位置に対応する値を格納する．
[0-9]	メモリポインタが指す位置の値を $10$ 倍し，対応する値を足す（値が負だった場合は引く）．

たとえば g という命令では，メモリの内容にかかわらず $103$ を書き込みます．それに続けて 4 という命令を行うとメモリには $1034$ が格納されることになります．この $1034$ という値は後々重要になるので覚えておきましょう．

また，たとえば指していた値が $-2$ だった場合に $8$ を実行すると $-28$ になります．面白い設計だと思いませんか？

算術演算

「メモリポインタが指す値」という表現などが冗長でつらいですね．

L -> \ / <- R
      | <- P

いま，メモリポインタが P の位置を上向きに指しているとします．このとき，左手側（L）が左オペランド，右手側（R）が右オペランドとなります．メモリポインタの向きが変わっても同様です．少々頭の体操になるかもしれませんね．

R -> \ / <- P
      | <- L

メモリポインタが P を左下向きに指していた場合はこんな感じですね．

記号	役割
(	P をデクリメントする．
)	P をインクリメントする．
+	加算．P = L + R．
-	減算．P = L - R．
*	乗算．P = L * R．
:	除算．P = L / R．
%	剰余算．P = L % R．
~	符号反転．P = -P．

丸括弧のどちらが何に対応しているかがわかりづらいですね．私は文字コードの大きい方が大きくする方と覚えましたが間違えがちでつらいです．また，除算は / でないことと，C-like な除算でなく Python-like な除算であることに注意しましょう．（負の場合にどうのこうの，といった話です．知らない人は調べましょう．）

入出力

難解言語と言いつつ入出力が充実しているのはいいですよね．Brainf*cker からすると甘えに見えるかもしれません．

記号	役割
,	標準入力から一文字読み，P に格納する．EOF のときは $-1$ とする．
?	標準入力から数字又は符号が現れるまで読み捨て，P に格納する．EOF のときは $0$ とする．
;	P を $256$ で割った剰余（正とする）に対応する文字を標準出力に書き出す．
!	P を 10 進数表記で標準出力に書き出す．

; は P の値自体を書き換えることはしません．

さて，ここで先程の $1034$，g4 の出番です．g4; とすることで改行（0x0A）を出力します．（初期状態とは限らない）メモリに直接 $10$ を書き込む術はないので，こうした小技が生きてきます．スペースの場合は P0; などとします．

フロー制御

六角形ならではの遊びです．枝分かれや板（鏡？）のような文字を用いて命令ポインタの進行方向を変えます．

コマンド	E	SE	SW	W	NW	NE
/	NW	W	SW	SE	E	NE
\	SW	SE	E	NE	NW	W
_	E	NE	NW	W	SW	SE
|	W	SW	SE	E	NE	NW
<	??	NW	W	E	W	SW
>	W	E	NE	??	SE	E

たとえば，東向きに進んできた命令ポインタが / を実行すると北西向きに進むようになります．?? の部分はメモリが関わっていて，P が正なら進行方向から右向き，そうでなければ左向きに 60 度ずれた向きに変わります．

また，アクティブな命令ポインタを変更する命令は次の通りです．

記号	役割
[	一つ前の番号のものをアクティブにする．0 の前は 5 とする．
]	一つ次の番号のものをアクティブにする．5 の次は 0 とする．
#	P を $6$ で割ったあまりのポインタをアクティブにする．

これら三つの命令を実行する場合，現在アクティブなポインタを一つ進めてからアクティブなポインタを変更します．次の実行ステップでは，新しいポインタは移動する前に命令を読んで実行します．命令ポインタの位置が非アクティブになるごとに元の位置に戻ったりすることはないので，注意したりしなかったりしましょう．

残りのフロー制御がもう一つあります．

記号	役割
$	命令ポインタを一つ進める．（実質的に）次の命令を無視する．

メモリ操作

記号	役割
{	メモリポインタを左に進める．
}	メモリポインタを右に進める．
"	メモリポインタを左に戻す．=}= と等価．
'	メモリポインタを右に戻す．={= と等価．
=	メモリポインタの向きを反転させる．
^	P が正なら右へ，そうでなければ左へメモリポインタを進める．
&	P が正なら R，そうでなければ L の値を P にコピーする．

以上が Hexagony で使える命令になります．