9B分類

メニュー

更新履歴

カウンター

今日：2 合計：1660

HOJを始めた人にとって, まず取り組みやすいのが, 制限バイト数, あるいはBest解のバイト数が短い問題だと思います.
しかし, 例えば10Bや11B程度でも, 複雑な挙動をする再帰（乱歩と呼ばれる）は種類が多く,
なかなか全部理解しきれないのが現状です.

しかし, 9Bの1変数再帰は人間の手でも全て分類できる程度の分量です.
以下に分類表を挙げることにしましょう.

なお, ここに挙げたコードで, Best解が9B以下の問題は全て解けるというわけではありません.
ここのコードで解けないものについては, 再帰以外の方法, 特に無限ループ (0変数再帰) などの使用を検討すると良いでしょう.

また, 1変数再帰のうちでも, 多重再帰構文！を利用したものはここでは扱っていません.

Z字

本質的には8Bで書けるもの

a(X):Xsa(lX)
a()

の向きを変えたり大きくした場合になります.

小さい

a(X):Xsla(lX),a()
a(X):Xsra(rX),a()
a(X):Xsla(rX),a()
a(X):Xsra(lX),a()
a(X):sXla(lX),a()
a(X):sXra(rX),a()
a(X):sXla(rX),a()
a(X):sXra(lX),a()
a(X):Xlsa(lX),a()
a(X):Xrsa(rX),a()
a(X):Xlsa(rX),a()
a(X):Xrsa(lX),a()

大きい

a(X):Xssa(lX),a()
a(X):Xssa(rX),a()
a(X):sXsa(lX),a()
a(X):sXsa(rX),a()
a(X):ssXa(lX),a()
a(X):ssXa(rX),a()

太い

a(X):sXa(srX),a()
a(X):sXa(slX),a()
a(X):lXa(srX),a()
a(X):rXa(slX),a()
a(X):rXa(srX),a()
a(X):lXa(slX),a()
a(X):Xsa(srX),a()
a(X):Xsa(slX),a()
a(X):Xla(srX),a()
a(X):Xra(slX),a()
a(X):Xra(srX),a()
a(X):Xla(slX),a()
a(X):sXa(rsX),a()
a(X):sXa(lsX),a()
a(X):lXa(rsX),a()
a(X):rXa(lsX),a()
a(X):rXa(rsX),a()
a(X):lXa(lsX),a()
a(X):Xsa(rsX),a()
a(X):Xsa(lsX),a()
a(X):Xra(rsX),a()
a(X):Xla(lsX),a()
a(X):Xla(rsX),a()
a(X):Xra(lsX),a()

成長Z字

方向転換はZ字と同じ規則だが, sの個数が増えていくもの.

a(X):Xa(lXss),a()
a(X):Xa(rXss),a()
a(X):Xa(ssXl),a()
a(X):Xa(ssXr),a()
a(X):Xa(sXl),a(s)
a(X):Xa(sXr),a(s)
a(X):Xa(sXl),a(l)
a(X):Xa(sXr),a(r)
a(X):Xa(sXl),a(r)
a(X):Xa(sXr),a(l)
a(X):Xa(lXs),a(s)
a(X):Xa(rXs),a(s)
a(X):Xa(lXs),a(l)
a(X):Xa(rXs),a(r)
a(X):Xa(lXs),a(r)
a(X):Xa(rXs),a(l)
a(X):Xsa(sXl),a()
a(X):Xsa(sXr),a()
a(X):sXa(lXs),a()
a(X):sXa(rXs),a()
a(X):Xla(lXs),a()
a(X):Xra(rXs),a()
a(X):Xla(rXs),a()
a(X):Xra(lXs),a()
a(X):lXa(sXl),a()
a(X):rXa(sXr),a()
a(X):lXa(sXr),a()
a(X):rXa(sXl),a()

太く

a(X):Xa(sXsl),a()
a(X):Xa(sXsr),a()
a(X):Xa(sXls),a()
a(X):Xa(sXrs),a()
a(X):Xa(slXs),a()
a(X):Xa(srXs),a()
a(X):Xa(lsXs),a()
a(X):Xa(rsXs),a()

P字

原理的には, 特殊な初項で紹介した, 最初の2項に特殊な方向を持たせるもので,
ある段階以降はただの繰り返しになります.

a(X):sXa(XXr),a()
a(X):sXa(XXl),a()
a(X):Xsa(XXr),a()
a(X):Xsa(XXl),a()

でも通常再帰せずに書いた方が短いです. sの部分が巨大だと再帰で短縮ワンチャンありますが,
その場合も逆回りで書けば多重再帰構文！で書いた方が短く, あまり役に立たない再帰.

田4つ

a(X):Xa(XlX),a(s)
a(X):Xa(XrX),a(s)

なお, Y=Xl, Xrと変数変換することで

a(Y):Yra(YY),a(sl)
a(Y):Yla(YY),a(sr)

などと変形できて, 田の字を描くのは明白になります.

直線

ただの直線

sをたくさんつけても180度方向転換しかしないため, 直線を往復しかできないです.

a(X):Xlla(sX),a()
a(X):lXla(sX),a()
a(X):rXra(sX),a()
a(X):llXa(sX),a()
a(X):Xa(sXll),a()
a(X):Xa(llXs),a()

2列直線

特殊な2倍関数を理解するとこのような形になる理由がよく分かるかもしれません.
「正方形を何周もしたあげく最後のsが足りない」ようなXに収束し, 後半は再帰の境目から見て後ろに進んでいます.

a(X):Xa(XsX),a(l)
a(X):Xa(XsX),a(r)

3列直線

a(X):Xa(lXsl),a()
a(X):Xa(rXsr),a()
a(X):Xa(lXls),a()
a(X):Xa(rXrs),a()
a(X):Xa(slXl),a()
a(X):Xa(srXr),a()
a(X):Xa(lsXl),a()
a(X):Xa(rsXr),a()

斜め

a(X):XXa(rX),a(s)
a(X):XXa(lX),a(s)
a(X):XXa(Xr),a(s)
a(X):XXa(Xl),a(s)
a(X):Xa(lXsr),a()
a(X):Xa(rXsl),a()
a(X):Xa(lXrs),a()
a(X):Xa(rXls),a()
a(X):Xa(slXr),a()
a(X):Xa(srXl),a()
a(X):Xa(lsXr),a()
a(X):Xa(rsXl),a()

うず

再帰の基本.

a(X):XXla(sX),a()【0,2,4,6,8】
a(X):XXra(sX),a()【0,2,4,6,8】
a(X):XlXa(sX),a()【1,3,5,7,9】
a(X):XrXa(sX),a()【1,3,5,7,9】
a(X):lXXa(sX),a()【0,2,4,6,8】
a(X):rXXa(sX),a()【0,2,4,6,8】
a(X):sXla(sX),a()【1,2,3,4,5】
a(X):sXra(sX),a()【1,2,3,4,5】
a(X):slXa(sX),a()【1,1,2,3,4】
a(X):srXa(sX),a()【1,1,2,3,4】
a(X):lsXa(sX),a()【1,2,3,4,5】
a(X):rsXa(sX),a()【1,2,3,4,5】
a(X):Xla(XXs),a()【0,1,3,7,15】
a(X):Xra(XXs),a()【0,1,3,7,15】
a(X):lXa(XXs),a()【0,1,3,7,15】
a(X):rXa(XXs),a()【0,1,3,7,15】
a(X):XXa(sX),a(l)【0,0,1,1,2,2】
a(X):XXa(sX),a(r)【0,0,1,1,2,2】
a(X):XXa(Xs),a(l)【0,0,1,1,2,2】
a(X):XXa(Xs),a(r)【0,0,1,1,2,2】
a(X):Xra(XX),a(s)【1,2,4,8,16】
a(X):Xla(XX),a(s)【1,2,4,8,16】
a(X):rXa(XX),a(s)【1,2,4,8,16】
a(X):lXa(XX),a(s)【1,2,4,8,16】
a(X):Xa(Xss),a(l)【0,2,4,6,8】
a(X):Xa(Xss),a(r)【0,2,4,6,8】

うず変種

a(X):Xa(sXlX),a()
a(X):Xa(sXrX),a()
a(X):Xa(XlXs),a()
a(X):Xa(XrXs),a()

最初の例を変数変換すると

a(Y):Yra(sYY),a(l)

となること見ると少しは理解しやすいかもしれません.

ジグザグ

Z字を作る独特な方向転換手順を, 2倍ずつすると片側に進んでいきます.
sを増やすことで, どんどん歩幅が増えていますね.

a(X):XXa(sXl),a()
a(X):XXa(sXr),a()
a(X):XXa(lXs),a()
a(X):XXa(rXs),a()

乱歩

なお, 慣例上乱歩と呼ばれることが多いというだけで, 実際には当然規則的です.
巨大なフラクタルを描くのですが, 壁で位置が矯正されるため, 非常に規則認識しにくいものになります.

次の6種は, 互いにミラー形や変数変換で説明できて, 似た形になることが分かります.

a(X):Xa(XsXl),a()
a(X):Xa(XsXr),a()
a(X):Xa(XXl),a(s)
a(X):Xa(XXr),a(s)
a(X):Xa(lXX),a(s)
a(X):Xa(rXX),a(s)

その他の乱歩.

a(X):Xa(sXXl),a()
a(X):Xa(sXXr),a()
a(X):Xa(lXXs),a()
a(X):Xa(rXXs),a()
a(X):Xa(lXsX),a()
a(X):Xa(rXsX),a()