【Markov Algorithm】FizzBuzzを書く
縛りFizzBuzz お題募集中 ←こういうのやってみたかった
ちゃんと'Fizz' 'Buzz' 'FizzBuzz'と出力し、
改行区切りは使用上(多分)無理なのでカンマ区切り
初めて書いた。
この記事絶対に伸びない
Markov Algorithmとは
文字置換だけでチューリング完全（何でもできる的）なやつ
規則を上からチェックしていき、もし実行できるなら一度だけ実行、
↑に戻る
実行できる置換規則がないまたは停止規則がある場合は終了
停止規則は◯◯が含まれるとき××に置換してからプログラムを終了させる。
前書き
完成品は一番下に置いてあります。
この記事は下記サイトで実際に動作を確認しながら読まないと多分何言ってるかわかりません。さぼりました。
入出力の形式
入力の方法は数字
15
出力
1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz
方針
長さ[ 入力 ]の空リストを作る
┗ 数字を1ずつ減らしながら左側に_を出力する
空リストの中身を1から順に埋めていく
┣ _の間をカンマで区切る┗
1ずつ増やしながら右側にコピーする
Fizz Buzz に置き換える
┣ 各桁の和が3で割り切れるならyを付け足す┣ 一の位が
0か5ならYを付け足す┗
yかYがついている数字の数字部分を消し、yをFizz、YをBuzzに置き換える
書く
空リスト
デクリメントを実装する
デクリメント
繰り下がりをどうしようか、、
1ケタずつ見ていくしか無いか
端っこをEにして、dの左の数字を減らして
繰り下がらなかったときはdをDに変える感じにしよう
[E15dE]
0d:d9 //次の桁も減らす
1d:D0 //それ以降の桁は減らさない
︙
9d:D8
0D:D0 //Dを左に動かす
︙
9D:D9
これで一旦Dが左についたときにデクリメント出来た。
リスト
Dが左についたときに左側に_を出して、dを元の位置に戻すから、
一回Dをbとかにおいて
E0b:Eb //一番上の桁の0を消す(一番上)
ED:_Eb //空リストを追加する
b0:0b //bを左に動かす
︙
b9:9b
bE:dE //bをdに戻す
で、終わったらEdEはいらないから
EdE:E //消す
1...Nのリスト
カンマ区切り
次は_をカンマ区切りするから、
[________...]
__:_,_ //カンマ区切りする
コピー
数字をコピーするから
とりあえずcをコピー用の文字で、Cをコピー中の文字として、
[Ec_,_,_,.....,_E,]
Ec_:Ec1, //リストの最初を1にする
c1,:1,c1 //cnを右側にコピーする
︙
c9,:9,c9
c11:1c1
︙
ん？、、、
100通り書かないといけない？
どうしよ、、、
少女検索中...
いいこと思いついた！
別の文字に置き換えればいいのか！！ ※嘘です調べました
（oの数が降順なのは昇順にするとECoが全てに適応されてしまうから）
[Ec1,_,_,.....,_E,]
Ec0:0ECoooooooooo
︙
Ec9:9ECo
で、oとCを右に動かせばいいから
o,:,o
o0:0o
︙
o9:9o
C,:,C
C0:0C
︙
C9:9C
動かしきったら数字に戻して、
Eに情報を伝えるために左に行くlを作って、
[E,Cooooooooo_,_, … ,_E,]
Coooooooooo:l0
︙
Co:l9
,l:l,
0l:l0
︙
09:90
El:Ec
これを数字の右側に動かして、
[1Ec,1_,_, … ,_E,]
Ec:ooooooooooo
ooooooooooo_:i
インクリメント
数字をインクリメントするには
0は1、1は2、...8は9、9は0にして次の桁も同じルールでインクリメントするから、
iをインクリメントする文字、Iをインクリメントしない文字にして、
[1,1i,_, … ,_E,]
0i:I1
︙
8i:I9
9i:i0
0I:I0
︙
9I:I9
左にiのまま行き切ったら桁を追加するから
[1,2, … ,9,i0,_, … ,_E,]
,i:,I1
で、Iが左に行き切った時終わったかを感知しないといけないから、右にEを置いて、右に動くoを流用して、左に動くlも流用して、lが戻ってきたことを感知するeを用意すると、
[1,2, … ,99,I100E,]
,I:Eeo
,o_:l,_
el:l
Ee:
oE:
倍数判定
sを判定しながら右に動かす文字とすると
事前に,sを一番左側に置いておいて、、、
5の倍数は一番下の桁を見ればわかるからどうにかして3の倍数を判定しないといけない、、、
どうしよ、、、
あ！
mod3の結果の個数分xを出してxが3つ揃ったら消せばいいじゃん！！
[,s1,2, … ,100,]
じゃあ
xxx:
s0:0s
s1:1sx
s2:2sxx
s3:3s
s4:4sx
s5:5sxx
s6:6s
s7:7sx
s8:8sxx
s9:9s
x0:0x
︙
x9:9x
xが残ってたらxを次に移す準備としてtに置き換えて
[,1sx,2, … ,100,]
xx:t
x:t
次に5の倍数かを判定するから
sの左が0か5ならYに置き換えるから(Buzzだから)
[… 5s, …]
0s:Ys
5s:Ys
0Y:Y
︙
9Y:Y
で、さっき放置していた3の処理をして、、
sと,が隣り合っていたら3の倍数だから、yに置き換えるから
[… 3s, …]
s,:ye,
0y:y
︙
9y:y
倍数判定が終わったら次の文字に進むから
[… 2,ye,4 …]
[1st,2, …]
ye,:y,s
st,:,s
'y'と'Y'の順番が逆だから入れ替えて
[… ,14,Yy, …]
Yy:yY
'y'と'Y'を'Fizz'と'Buzz'を入れ替えて
後ろの,s、最初の,を消して
[,1,2,3 … 99,Y,]
y:Fizz
Y:Buzz
,s:
,::
与えられた文字が1だった時の例外処理だけしたら
1,1oooooooooo:1
完成だぁぁぁ！！！！！！！
完成
※長いので注意
完成品
完成品
;0:0;
;1:1;
;2:2;
;3:3;
;4:4;
;5:5;
;6:6;
;7:7;
;8:8;
;9:9;
;:dE,
E0b:Eb
0d:d9
1d:D0
2d:D1
3d:D2
4d:D3
5d:D4
6d:D5
7d:D6
8d:D7
9d:D8
0D:D0
1D:D1
2D:D2
3D:D3
4D:D4
5D:D5
6D:D6
7D:D7
8D:D8
9D:D9
ED:_Eb
b0:0b
b1:1b
b2:2b
b3:3b
b4:4b
b5:5b
b6:6b
b7:7b
b8:8b
b9:9b
bE:dE
EdE:E
Ec_:Ec1,
__:_,_
Ec0:0ECoooooooooo
Ec1:1ECooooooooo
Ec2:2ECoooooooo
Ec3:3ECooooooo
Ec4:4ECoooooo
Ec5:5ECooooo
Ec6:6ECoooo
Ec7:7ECooo
Ec8:8ECoo
Ec9:9ECo
o,:,o
o0:0o
o1:1o
o2:2o
o3:3o
o4:4o
o5:5o
o6:6o
o7:7o
o8:8o
o9:9o
C,:,C
C0:0C
C1:1C
C2:2C
C3:3C
C4:4C
C5:5C
C6:6C
C7:7C
C8:8C
C9:9C
ooooooooooo_:i
Coooooooooo:l0
Cooooooooo:l1
Coooooooo:l2
Cooooooo:l3
Coooooo:l4
Cooooo:l5
Coooo:l6
Cooo:l7
Coo:l8
Co:l9
,l:l,
0l:l0
1l:l1
2l:l2
3l:l3
4l:l4
5l:l5
6l:l6
7l:l7
8l:l8
9l:l9
El:Ec
Ec:ooooooooooo
0i:I1
1i:I2
2i:I3
3i:I4
4i:I5
5i:I6
6i:I7
7i:I8
8i:I9
9i:i0
0I:I0
1I:I1
2I:I2
3I:I3
4I:I4
5I:I5
6I:I6
7I:I7
8I:I8
9I:I9
,i:,I1
,I:,Eeo
,o_:l,_
el:l
Ee:
oE:
xxx:
s0:0s
s1:1sx
s2:2sxx
s3:3s
s4:4sx
s5:5sxx
s6:6s
s7:7sx
s8:8sxx
s9:9s
x0:0x
x1:1x
x2:2x
x3:3x
x4:4x
x5:5x
x6:6x
x7:7x
x8:8x
x9:9x
xx:t
x:t
0s:Ys
5s:Ys
0Y:Y
1Y:Y
2Y:Y
3Y:Y
4Y:Y
5Y:Y
6Y:Y
7Y:Y
8Y:Y
9Y:Y
0y:y
1y:y
2y:y
3y:y
4y:y
5y:y
6y:y
7y:y
8y:y
9y:y
s,:ye,
ye,:y,s
st,:,s
Yy:yY
y:Fizz
Y:Buzz
,s:
1,1oooooooooo:1
,::
:,sEcE;
出力
入力
100
1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz,16,17,Fizz,19,Buzz,Fizz,22,23,Fizz,Buzz,26,Fizz,28,29,FizzBuzz,31,32,Fizz,34,Buzz,Fizz,37,38,Fizz,Buzz,41,Fizz,43,44,FizzBuzz,46,47,Fizz,49,Buzz,Fizz,52,53,Fizz,Buzz,56,Fizz,58,59,FizzBuzz,61,62,Fizz,64,Buzz,Fizz,67,68,Fizz,Buzz,71,Fizz,73,74,FizzBuzz,76,77,Fizz,79,Buzz,Fizz,82,83,Fizz,Buzz,86,Fizz,88,89,FizzBuzz,91,92,Fizz,94,Buzz,Fizz,97,98,Fizz,Buzz
あとがき
何かの役に立ったかはわかりませんが知的好奇心をくすぐれたなら幸いです。
最後までお読みいただき、ありがとうございました！！
訂正などがあればコメントお願いいたします。
コード5日で書いたのに記事書くの数か月かかった！！！
感想