プログラミング言語 Piet で、競技プログラミングの問題を解くコードを書いてみた。(描いてみた？)
実行環境の構築
今回は、Amazon EC2 上の Ubuntu 24.04 (AMI ID: ami-05d38da78ce859165) で実行環境を構築した。
また、Piet のWebページでは複数のインタプリタが紹介されているが、今回は
GitHub - your-diary/piet_programming_language: Interpreter for Piet Programming Language
を用いた。
とりあえず環境をアップデートする。
sudo apt-get update
sudo apt-get upgrade -y
インタプリタのインストールに用いるツールをインストールする。
sudo apt-get install -y rustup build-essential
rustup default stable
sudo apt-get install -y cargo で直接 cargo をインストールしてはいけない。
このコマンドで cargo をインストールすると、インストールされる rustc のバージョンが足りず、インタプリタのインストールに失敗してしまった。
インタプリタをインストールする。
まず、インタプリタのレポジトリで紹介されているコマンドを実行する。
cargo install --locked --git 'https://github.com/your-diary/piet_programming_language'
しばらく待つと .cargo/bin ディレクトリ内にインタプリタの実行可能ファイル piet_programming_language ができるので、これをパスが通っている場所にコピーする。
.cargo/bin ディレクトリは、設定を変更していなければホームディレクトリにあるだろう。
sudo cp ~/.cargo/bin/piet_programming_language /usr/local/bin/
今回のインタプリタの入出力の特徴
今回用いるインタプリタの入出力には、以下の特徴がある。
- 数値を出力すると、勝手に改行文字も出力される
- 文字を入力する際、空白文字 (改行文字も含む) は無視される
そのため、以下のような害が生じる。
- 数値を空白区切りで出力する際、最後の要素以外には組み込みの数値出力機能は使えない
- 文字列を読み込む際、「空白文字に当たったら終了」という判定ができない
今回は、これらの害に以下のように対処する。
- 組み込みの数値出力機能を使わず、自分で数値を文字列に変換して文字出力機能で出力する
- 文字の読み込みが失敗した場合は何も起きなかったかのように命令を無視することを利用した入力の終了判定を行う
今回解く問題では与えられないが、入力の文字列の長さが N などとして与えられるタイプの問題では、この情報を用いて文字列を適切に読み込むことができるだろう。
問題を解いてみる
今回は、
PracticeA - Welcome to AtCoder
を解くプログラムを実装してみた。
これは、3個の整数と1個の文字列が与えられるので、与えられる整数の和と文字列を空白区切りで出力する、という問題である。
また、制約には書かれていないが、公式の解答例でC言語の scanf の書式 %s を用いて文字列を読み込んでいることなどから、用意されているテストケースでは与えられる文字列に空白文字は含まれていなそうである。
方針
今回実装するプログラムは、以下の手順で処理を行う。
番兵を用意する
数値から変換した文字列の出力、および読み込んだ文字列の出力の際に用いる番兵として、0 をスタックに積む。
# 番兵
push 1
push 1
subtract
整数を読み込み、足す
整数を3個読み込み、それらの和を求める。
# 整数を読み込み、足す
in(number)
in(number)
in(number)
add
add
求めた整数の和を文字列に変換する
以下の命令列において、pointer で「直進」した場合は次の処理 (変換した文字列の出力) に進み、「右折」した場合は残りの命令列 (「1桁変換する」以降) を実行する。
また、この命令列の最後の divide を実行した後は、最初の duplicate に戻って実行を進める (ループする)。
# 変換が完了したかを判定する
duplicate
not
not
pointer : 0なら直進、そうでなければ右折
# 1桁変換する
duplicate
push 10
mod
push 8
push 6
multiply
add
push 2
push 1
roll
push 10
divide
まず、not を2回実行することで、変換中の値が 0 なら 0 に、0 以外なら 1 に変換する。
この値を用いて、pointer で分岐を行う。
今回の問題では入力の整数は全て正であり、その和も正になるため、変換する値が最初から 0 のケースは考えなくてよい。
変換を行う場合は、10 で割った余りを求めてそれに 48 を足すことで、変換中の値の1の位を文字に変換する。
変換した文字を roll 命令でスタックに格納し、変換中の値を 10 で割って1の位を取り除く。
このように変換を行うと、スタックにそれぞれの位を表す文字が下位から上位の順で積まれるため、変換後にスタックの上から順に文字を出力することで、上位から下位に向かって正しく整数の和を出力できる。
変換した文字列を出力する
以下の命令列において、pointer で「直進」した場合は次の処理 (空白の出力) に進み、「右折」した場合は残りの命令列 (out(char)) を実行する。
また、この命令列の最後の out(char) を実行した後は、「変換した整数を出力する」の duplicate に戻って実行を進める (ループする)。
# 変換が完了した残りを捨てる
pop
# 変換した整数を出力する
duplicate
not
not
pointer : 0なら直進、そうでなければ右折
out(char)
最初に、変換が完了した残りカスの 0 がスタックトップにあるので、これを pop で取り除く。
次に、スタックトップの値が 0 かを確認する。
0 でなければ変換した文字なので出力し、0 であれば番兵なので出力を終了する。
空白を出力する
整数の和と文字列の間の空白を出力する。
32 をそのまま描かずに 4×8 と表現することで、用いるピクセル数を節約できる。
# 空白を出力する
push 4
push 8
multiply
out(char)
文字を読み込んで出力する
以下の命令列において、pointer で「直進」した場合は次の処理 (改行の出力) に進み、「右折」した場合は残りの命令列 (out(char)) を実行する。
また、この命令列の最後の out(char) を実行した後は、最初の in(char) に戻って実行を進める (ループする)。
# 文字を読み込んで出力する
in(char)
duplicate
not
not
pointer : 0なら直進、そうでなければ右折
out(char)
in(char) で文字の入力を読み取ることを試みる。
ここで、今回のインタプリタの仕様により、空白文字は無視される (読み飛ばされる)。
文字を読み取った場合はそれがスタックに積まれ、入力の終端に達して文字を読み取れなかった場合は何もしないのでスタックトップは番兵の 0 となる。
そこで、in(char) を行った後のスタックトップが 0 でなければ文字を読み取ったと判断してそれを出力し、0 であれば入力の終端に達したと判断して次の処理に進む。
改行を出力して終了する
文字列の出力が完了したので、最後に改行文字を出力する。
そして、スタックに残っていた番兵を pop し、プログラムの実行を終了する。
# 改行を出力して終了する
push 10
out(char)
pop
実装
「方針」で用意した命令列を、色の組み合わせに落とし込んだ。
見やすいように16倍に拡大すると、以下のようになっている。
- 進行方向に1ピクセルの出っ張りを作る
- 進行方向の進むべき場所以外を黒で埋める
- 進行方向全てに次の命令を表す色を塗る
ことにより、CC の動作を無視し、DP のみを考慮すればいいように工夫した。
以下が、このプログラムの npiet によるトレースである。
「方針」の各部分に相当するプログラムを横に繋げた構造となっている。
また、「方針」で載せた命令列に無い命令列として、push と pointer を組み合わせて方向転換を行っている場所がある。
ImageMagick による画像の変換
Piet のソースコードは画像であるが、競技プログラミングではソースコードをテキストで提出することが求められることが多そうである。
ImageMagick を用いると、
magick convert program.png -compress none program.ppm
のようなコマンドにより、画像をテキストで表す PNM (PPM) 形式に変換できる。
出力の拡張子を .ppm ではなく誤って .pnm としてしまうと、-compress none オプションをつけていてもバイナリ形式で出力された。
また、今回掲載した「16倍に拡大」した画像は、
magick convert program.png -sample 1600% program-16x.png
のようなコマンドで作成した。
結論
処理系の特性を考慮しつつ、プログラミング言語 Piet で競技プログラミングの問題を解くコードを書く (描く？) ことができた。