ルール
- 入力として正の整数 N を与えたら 4 から始まる合成数の数列の 1 番目から N 番目までの合計を出力してください
- N は最大で 100 とします
WhiteSpaceについて
WhiteSpaceは、ご存じの通り、空白・タブ・改行のみが意味を持つプログラミング言語ですが、それをアセンブリ言語として取り扱えるようツールを作成しました。
概要は先日の記事WhiteSpaceアセンブラ・逆アセンブラの紹介をご覧ください。
今回はそのツールを用いてコードを組みました。
出力例
アセンブリソースsum_cnum_seq.wssを直接実行したり、あるいはWhiteSpaceコードにアセンブルし、それから実行した例です。入力の数値は標準入力から与えています。
※出力時、改行は省略しているため、echoコマンドで改行を補っています。
なお、アセンブル時に-Rでコード情報のレポートを出力している通り、作成されたWhiteSpaceコードは171bytesとなっています。
$ ruby whitespace.rb sum_cnum_seq.wss <<< 2 ; echo
10
$ ruby whitespace.rb sum_cnum_seq.wss <<< 4 ; echo
27
$ ruby whitespace.rb -a -R -n sum_cnum_seq.wss
** Code summary **
size statistics:
inst: 42
byte: 171bytes
label statistics:
null: used 3 times, registered at ip 5, line 9
+0(0b): used 2 times, registered at ip 10, line 16
-0(0b): used 2 times, registered at ip 38, line 50
$ ruby whitespace.rb sum_cnum_seq.ws <<< 10 ; echo
112
$ ruby whitespace.rb sum_cnum_seq.ws <<< 100 ; echo
7059
コード
コードについては、githubのサンプルとしても挙げています。
内容としては、素直に試し割りしながら合成数判定をし、加算を行うものです。
ただそうすると、個数のカウンタ、加算する候補の数、和の3種類のデータを同時に扱うことになりますが、これはスタックのみでは困難です。( swap命令を使っても、トップから2つ目までしか操作できない )
そこで、数値入力(geti)の時のまま、ヒープアドレス0でカウンタを管理し、他の2データをスタックで管理するようにしました。カウンタを操作する時のみ、一時的にヒープからカウンタを引き出し、デクリメントした上でまた保存し直すことになります。
# カウンタはヒープアドレス0で管理、和と加算候補を積む
push 0
dup
dup
dup
geti
# メインループ
mark null
pop # ループの最初は余分な1要素があるはず
push 1
add
# 試し割り用のループ ( 負の除数で回す )
push -1
mark +0
push 1
sub
# 除数が小さくなり過ぎたら非合成数
copy +1
copy +1
dup
mul
sub
jneg null
# 割り切れない場合は剰余が負なのでループを進む
copy +1
copy +1
mod
jneg +0
pop
# 合成数なので加算
swap
copy +1
add
swap
# カウンタをヒープから引き出してデクリメント
push 0
dup
retr
push 1
sub
dup
jzero -0 # 指定個数足したら終了処理へ
# カウンタをヒープに保存し直してループを進む
stor
dup
jump null
# 終了処理、余分な要素を捨てて合計を出力
mark -0
stor
pop
puti
アセンブルした生のWhiteSpaceコードは次の通りです…と言いたいところなのですが、QiitaではWhiteSpaceのコードを正常に表示できないようです。
仕方がないので、空白・タブ・改行をs,t,nで置き換えたコードを次に示します。
※これは、ツールで出力形式(-Tオプション)をstnと指定することで、生成することができます。
$ ruby whitespace.rb -a -n -T stn sum_cnum_seq.wss
$ more sum_cnum_seq.wsv
sssnsnssnssnstnttnssnsnnssstntsssssttnnsssnssstntsststsstnstsstnsnstssntsstnttns
tsstnstsstntsttnttsnsnnsntstsstntssssntsssnsnstttssstntsstsnsntstnttssnsnsnnnsst
nttssnntnst
おまけ1
Brainf**kを予定されてた方が欠場されたので、さっくり組んで載せることにしました。単純な試し割りによる判定です。
** 1 char read ahead loop **
>,+[
** parse one line as a number **
[
** mod 10 negative **
+[>[+>>]<[>----------->]<<-]
>[<<+[->>++++++++++<<]>>>,+>]
<]
** summation loop **
<[>>++++<<[
** trial division loop
>>>>++<+[-
** divmod **
<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
** when not divisible: restore the divisor **
>>>[<[->+<]>>>>]
** when divisible: add to the sum and decrement the count **
<[>>[-]<<[-]<[-<+<+>>]<<<->>>>>>>]
** judge if the divisor is too large or not **
<<[
+[>[->>]<[>>]<<-<+>]
<<[-<+>]
+>>>[[-]>]<<[<->[-]>]
]
<<]
<+<<]]
>>[-]
** divmod sliding loop to create digits **
<[+[>[+>>>]<[>--------->+>]<<<-]>->-]
** print the answer **
<[>+++++++[-<++++++++>]<++.[-]<<]
++++++++++.
,+]
$ cat input.txt
2
4
10
100
$ bff sum_cnum_seq.bf < input.txt
10
27
112
7059
おまけ2
このような依頼があったため、Pxemにもチャレンジしてみることに。
なんとなく、WhiteSpaceのようなスタック構造と、Brainf**kのような制御(ループ)構造を持ったようにも見えたので。
処理系は、Rubyで動作するrpxemを使いました。
なお、この言語はファイル名自体をプログラムと解釈するという珍しいものです。ファイルの内容は、データとしてスタックに取り込むか、あるいはコードとしてサブルーチン的に実行するか(.e命令)ができるのですが、今回後者を利用しました。
ファイル名部分は、条件付き加算で、合成数判定(試し割り)をファイル内コードで実施しています。
.t.s01.-10.y01.-.+.c.c.!.m.v.c.m.%01.-.y.s.s.s00.-.c.c.c.c.a.v.a01.-.v.w.s00.-.c.a
$ rpxem xx.-03.-._.t.m.w01.-.+.e.w.c.v.+.v.m01.-.-.t00.-.a.m.a.s.n.pxe <<< 2; echo
10
$ rpxem xx.-03.-._.t.m.w01.-.+.e.w.c.v.+.v.m01.-.-.t00.-.a.m.a.s.n.pxe <<< 4; echo
27
$ rpxem xx.-03.-._.t.m.w01.-.+.e.w.c.v.+.v.m01.-.-.t00.-.a.m.a.s.n.pxe <<< 10; echo
112
$ rpxem xx.-03.-._.t.m.w01.-.+.e.w.c.v.+.v.m01.-.-.t00.-.a.m.a.s.n.pxe <<< 100; echo
7059
終わりに
操作するたびにスタックが伸びたり縮んだりするさまを考えながらプログラミングするのが結構面白いWhiteSpaceです。また、別記事WhiteSpaceでQuineでも取り上げましたが、ゴルフとしてもとっつき易い面がありますから、一度試してみてはいかがでしょうか。