［今日のPiet］最大値を求めるPiet - 趣味プログラミングの部屋

今日のPietです。

拙作「GridPietGenerator」を使って、テキストベースで書かれた「処理フローファイル」から、

所望の処理をするPietソースコード画像を生成します。

今回のテーマは「最大値」です。

最大値を求めるPietソースコード

概要

スタックに格納されている数列の最大値を求めるPietソースコードを作ります。

仕様

スタックが次の状態になっているとします。

$[\cdots|a_1,\cdots,a_{N},N$

スタックトップに要素の個数Nがあります。

続いてN個の数 $a_N,\cdots,a_1$ が、順にスタックに積まれています。

今回作るPietソースコードは、この状態からスタートして、

数列 $a_N,\cdots,a_1$ の最大値 $r$ を求め、スタックを次の状態に変更します。

$[\cdots|r$

今回作ったPietソースコードは、上記の処理に入出力処理を加えたものになります。

つまり、標準入力に数値を入力して、

正数なら、数列の値としてスタックに積み、入力を継続する
負数なら、数列の入力を停止して、最大値を出力する

という流れになります。

処理フローファイル

今回作った処理フローファイル（max.txt）はこちら。

push1 dup sub     #[N(=0)
:input            #[...|N
inn               #[...|N,p
dup push1 dup sub #[...|N,p,p,0
gt if::input_end  #[...|N,p
push2 push1 roll  #[...|p:N
push1 add         #[...:p(=>a_N)|N+1(=>N)
goto:input        #[...|N
:input_end        #[...|N,p
pop               #[...:a_1,...,a_N|N
########################################
## max
##  [...|a_1,...,a_N,N
##  ==> [...|max(a_n)
########################################
:max             #[...|a_1,...,a_N:N
push2 push1 roll #[...|a_1,...,N,a_N
dup              #[...|a_1,...,N,a_N,a_N(=>r)
push3 push2 roll #[...|a_1,...,a_N,r,N
dup              #[...|a_1,...,a_N(=>a_c),r,N,N(=>c)

:max_loop        #[...|a_1,...,a_c,r,N,c
dup if::max_end  #[...|a_1,...,a_{c-1},a_c(=>s),r,N,c
push1 sub        #[...|a_1,...,a_{c-1}(=>a_c),s,r,N,c-1(=>c)
push4 push2 roll #[...|a_1,...,a_c,N,c,s,r
dup              #[...|a_1,...,a_c,N,c,s,r,r
push3 push2 roll #[...|a_1,...,a_c,N,c,r,r,s
dup              #[...|a_1,...,a_c,N,c,r,r,s,s
push3 push1 roll #[...|a_1,...,a_c,N,c,r,s,r,s
gt if:max_nop:   #[...|a_1,...,a_c,N,c,r,s
push2 push1 roll #[...|a_1,...,a_c,N,c,s(=>r),r(=>s)
:max_nop         #[...|a_1,...,a_c,N,c,r,s
pop              #[...|a_1,...,a_c,N,c,r
push3 push1 roll #[...|a_1,...,a_c,r,N,c
goto:max_loop    #[...|a_1,...,a_c,r,N,c

:max_end         #[...|r,N,c
pop pop          #[...|r
########################################
## /max
########################################

:output          #[...|r
outn             #[...|   ==>r
end

生成されたPietソースコード

出来上がったソースコードがこちら

最大値を求めるPietソースコード

npiet実行結果

試しに数列「2,5,4,1,3」の最大値を求めてみます。

数列と、数列の終端を表す負数を入れると、

./npiet max.ppm -tpic
? 2
? 5
? 4
? 1
? 3
? -1
5

正しく最大値が出力されます。

解説

入力

まず、1行めから10行めは、数列 $\{a_n\}$ を入力する部分です。

2-8行めがループになっており、5行めに入力終了判定の分岐があります。

正の数を入れるとスタックにその値を積んでループ継続し、

負の数を入れるとループから脱出します。

さきほどのように、「2,5,4,1,3,-1」の順に入力すると、

数列入力終了時点（10行め実行直後）でのスタックの状態は次のようになります。

[00000 : 2] [00001 : 5] [00002 : 4] [00003 : 1] [00004 : 3] [00005 : 5]

上記はスタックに格納された値ひとつひとつを"[ ]"で括り、

[スタックボトムからの距離:値]と表記したものです。

入力した順にスタックボトムから値が格納されていることと、

スタックトップに数列の個数「5」が格納されていることがわかります。

最大値判定

16-38行めで最大値を計算します。

22-35行めがループになっており、スタックに格納した数列の末尾から

値を一つずつ取り出しながら最大値を求めます。

つまり、ループが一回実行されるごとに、数列は１ずつ短くなっていきます。

22行め完了時点で、スタックは次のようになっています。

$[a_1,\cdots,a_c,(その時点での最大値),(元の数列の長さ),(その時点での数列の長さ)$

今思ったけど、「元の数列の長さ」って、

毎度とっておく必要なかったな。。。

ループでのスタックの変化の様子を確認してみます。

22行め完了時点でのスタックの状態を順に並べてみると次のようになります。

[00000 : 2] [00001 : 5] [00002 : 4] [00003 : 1] [00004 : 3] [00005 : 3] [00006 : 5] [00007 : 5]

[00000 : 2] [00001 : 5] [00002 : 4] [00003 : 1] [00004 : 3] [00005 : 5] [00006 : 4]

[00000 : 2] [00001 : 5] [00002 : 4] [00003 : 3] [00004 : 5] [00005 : 3]

[00000 : 2] [00001 : 5] [00002 : 4] [00003 : 5] [00004 : 2]

[00000 : 2] [00001 : 5] [00002 : 5] [00003 : 1]

[00000 : 5] [00001 : 5] [00002 : 0]

地道に追っていくと、スタックは正しく変化していることがわかります。

特に、スタックトップがその時点の数列の長さになっていることもわかります。