【Markov Algorithm】文字置換のみでFizzBuzzを書く

# 【Markov Algorithm】FizzBuzzを書く
**縛りFizzBuzz お題募集中**　　　~~←こういうのやってみたかった~~
ちゃんと`'Fizz'` `'Buzz'` `'FizzBuzz'`と出力し、
改行区切りは使用上(~~多分~~)無理なのでカンマ区切り
初めて書いた。
<sub>~~この記事絶対に伸びない~~</sub>
## Markov Algorithmとは
**文字置換だけでチューリング完全（何でもできる的）なやつ**
<br><br>
規則を上からチェックしていき、もし**実行できるなら**一度だけ実行、
**↑に戻る**
実行できる**置換規則がない**または**停止規則がある**場合は終了
<br><br><br>
停止規則は◯◯が含まれるとき××に置換してからプログラムを終了させる。
## 前書き
完成品は一番下に置いてあります。
この記事は下記サイトで実際に動作を確認しながら読まないと多分何言ってるかわかりません。~~さぼりました。~~

https://mao.snuke.org/tasks/1
## 入出力の形式
入力の方法は数字
```
15
```
出力
```c
1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz
```
## 方針
<details>
<summary>長さ<code>[ 入力 ]</code>の空リストを作る</summary>
　┗ 数字を<code>1</code>ずつ減らしながら左側に<code>_</code>を出力する
</details>
<details>
<summary>空リストの中身を<code>1</code>から順に埋めていく</summary>
　┣ <code>_</code>の間をカンマで区切る<br>
　┗ <code>1</code>ずつ増やしながら右側にコピーする
</details>
<details>
<summary><code>Fizz</code>  <code>Buzz</code> に置き換える</summary>
　┣ 各桁の和が<code>3</code>で割り切れるなら<code>y</code>を付け足す<br>
　┣ 一の位が<code>0</code>か<code>5</code>なら<code>Y</code>を付け足す<br>
　┗ <code>y</code>か<code>Y</code>がついている数字の数字部分を消し、<code>y</code>を<code>Fizz</code>、<code>Y</code>を<code>Buzz</code>に置き換える
</details>

## 書く
### 空リスト
デクリメントを実装する
#### デクリメント
繰り下がりをどうしようか、、
<br><br>
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通り書かないといけない？
どうしよ、、、
<br><br><sub>少女検索中...</sub>
いいこと思いついた！
別の文字に置き換えればいいのか！！　※嘘です調べました
（`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
```
完成だぁぁぁ！！！！！！！
# 完成
※長いので注意
## 完成品
<details>
<summary>完成品</summary>

```
;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;
```
</details>

## 出力
入力
```
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
```
# あとがき
何かの役に立ったかはわかりませんが知的好奇心をくすぐれたなら幸いです。
**最後までお読みいただき、ありがとうございました！！**

訂正などがあればコメントお願いいたします。
<sub><font color="gray">~~コード5日で書いたのに記事書くの数か月かかった！！！~~</font></sub>

<font color="なんでこんなところまで見てるの、、、、？びっくりなんですけど？？？　こんなところまでお付き合いいただきありがとうございました！！！Esolangのアドベントカレンダーを見つけたので急いで書ききってみました笑笑　最近FizzBuzzしか書いてない気がする、、、それはそれで面白いんですけどね（笑）　次は何でFizzBuzz書きましょうか、、、一つは明日投稿予定です！！ではまた～"><font color="white">感想</font></font>