Qiita Engineer Festa 2024(キータ・エンジニア・フェスタ 2024) - Qiita
において、約1ヶ月で38記事という大量の記事の投稿を要求されることがわかった。
そこで、あまりコストをかけずに記事数を稼ぐ方法を考えた結果、「Welcome to AtCoder を様々な言語で解く」ことを思いついた。
単に解くだけでなく、使用する言語仕様の解説を入れれば、記事として一応成立するだろう。
Welcome to AtCoder
PracticeA - Welcome to AtCoder
Welcome to AtCoder では、以下の形式で整数 $a$, $b$, $c$ および文字列 $s$ が入力として与えられる。
a
b c
s
この入力をもとに、与えられた整数の和 $sum = a + b + c$ および文字列 $s$ を、以下の形式で出力することが求められる。
sum s
Whitespace の言語仕様
Whitespace は、空白、タブ、改行の3種類の文字で命令を表すプログラミング言語である。
これら以外の文字はすべて無視される。
Whitespace が扱う記憶域には、「スタック」と「ヒープ」がある。
「スタック」は、よくある先入れ先出しのデータ構造である。
「ヒープ」は、キーを指定して対応する値を保存できる連想配列のようなものである。
スタックに格納する要素、ヒープで扱うキーや値は、いずれも整数のみである。
整数の長さ (桁数) に制限は無い。
命令は、以下の要素を順に繋げることで表される。
- カテゴリー
- 種類
- 引数
「カテゴリー」は、以下のいずれかである。
カテゴリー | 意味 |
---|---|
空白 | スタック操作 |
タブ、空白 | 演算 |
タブ、タブ | ヒープアクセス |
改行 | フロー制御 |
タブ、改行 | 入出力 |
「種類」は、各カテゴリー内の具体的な命令の種類である。これは後述する。
「引数」は、命令によって有無および有る場合は何を書くかが決まっている。
有る場合、「数値」または「ラベル」である。
「数値」は、符号つきの2進数で表す。(負の値も補数を用いずそのまま表記する)
1文字目のタブまたは空白で符号を、残りのタブまたは空白で値を表す。改行で終端を表す。
タブや空白の意味は以下のようになっている。
文字 | 符号 | 値 |
---|---|---|
空白 | + | 0 |
タブ | - | 1 |
たとえば、+2 は「空白、タブ、空白、改行」、-3 は「タブ、タブ、タブ、改行」と表す。
「ラベル」は、任意のタブと空白の列で表し、改行で終端を表す。
以下、今回使用する命令の種類を示す。
全命令の一覧は、Whitespace Tutorial を参照してほしい。
スタック操作
種類 | 引数 | 意味 |
---|---|---|
空白 | 数値 | 指定の数値をスタックにプッシュする |
改行、空白 | なし | スタックトップの値をスタックにプッシュする |
改行、タブ | なし | スタックトップの値とその次の値を入れ替える |
改行、改行 | なし | スタックから値を1個ポップして捨てる |
演算
種類 | 引数 | 意味 |
---|---|---|
空白、空白 | なし | 加算 |
空白、タブ | なし | 減算 |
空白、改行 | なし | 乗算 |
スタックから値を2個ポップし、それらの値の演算結果をプッシュする。
減算は、「スタックトップの次の値」から「スタックトップの値」を引く。
ヒープアクセス
種類 | 引数 | 意味 |
---|---|---|
空白 | なし | ストア |
タブ | なし | ロード |
ストアは、スタックトップの値を、スタックトップの次の値をキーとしてヒープに書き込み、これら2個の値をポップする。
ロードは、スタックトップからキーをポップし、そのキーに対応する値をヒープから読み出し、読み出した値をプッシュする。
フロー制御
種類 | 引数 | 意味 |
---|---|---|
空白、空白 | ラベル | ラベルを設定する |
空白、改行 | ラベル | 無条件で指定のラベルにジャンプする |
タブ、空白 | ラベル | 値をポップし、それがゼロなら指定のラベルにジャンプする |
タブ、タブ | ラベル | 値をポップし、それが負なら指定のラベルにジャンプする |
改行、改行 | なし | プログラムの実行を終了する |
入出力
種類 | 引数 | 意味 |
---|---|---|
空白、空白 | なし | 値をポップし、それを文字コードとする文字を出力する |
空白、タブ | なし | 値をポップし、その値を十進数で出力する |
タブ、空白 | なし | 1文字入力を受け取る |
入力を受け取る際は、キーをポップし、受け取ったデータをポップしたキーを用いてヒープに格納する。
文字の入力を受け取ったら、その文字コードを格納する。
数値の入力を受け取る命令も存在するが、これは1行全体を読み込んで数値として解釈するものである。
数値として解釈できない行を読み込むと、ランタイムエラーが発生する。
今回は、全ての数値の読み取りを1文字ずつ読み取る処理に共通化することにしたため、この命令は使用しなかった。
答案の方針
ヒープのキー 0 を数値の合計、キー 1 を入力受け取り用に用いる。
以下の流れで処理を行う。
- 数値の合計を 0 に初期化する
- 以下を 3 回繰り返す (繰り返しのカウンターをスタックに置く)
- 読み取った数値となる 0 をスタックに置く
- 空白か改行を読み込むまで1文字ずつ読み込み、読み取った数値を更新する
- 読み取った数値をヒープに置かれた数値の合計に加算する
- 数値の合計を出力する
- 空白を出力する
- 以下を繰り返す
- 1文字読み込み、読み込んだ文字をそのまま出力する
- 読み込んだ文字が改行ならば、繰り返しを終了する
提出コード
命令を管理しやすいよう、各命令の前に命令の内容を表記した。
また、コメントは **
で囲って表した。
最終行の *
の後の改行までがプログラムに含まれる。
**initialize_sum**push_+0
push_+0
store **read_and_add_3_times**push_-3
label_0
**read_a_number**push_+0
label_1
push_+1
read_character
push_+1
retrieve push_+0xa
subtract if_0_goto_2
push_+1
retrieve push_+0x20
subtract if_0_goto_2
**a_digit_is_read**push_+10
multiply
push_+1
retrieve push_+0x30
subtract add goto_1
**done_reading_a_number**label_2
push_+0
retrieve add push_+0
swap
store push_+1
add duplicate
if_negative_goto_0
**done_read_and_add_3_numbers**discard
push_+0
retrieve output_number
push_+0x20
output_character
**read_and_echo_a_line**label_3
push_+1
read_character
push_+1
retrieve duplicate
output_character
push_+0xa
subtract if_0_goto_4
goto_3
label_4
end
*
*