昔作ったやつが出てきたのでここで供養
BrainFuckとは？
BrainFuckは、おふざけで作られた難解プログラミング言語の一種です。何がふざけているかと言うと、百聞は一見にすかずなので以下のコードを見てみよう。
以下はHello worldを出力するプログラムである。
++++++++[>++++++++<-]>++++++++.<+++++[>+++++<-]>++++.<+++[>+++<-]>--.<[><-]>.<++[>++<-]>-.<+++++++++[>---------<-]>++.<+++++++++[>+++++++++<-]>++++++.<+++[>---<-]>+.<++[>++<-]>-.<++[>--<-]>--.<+++[>---<-]>+.<
まさにBrainFuckである。頭おかしい。
今日はこれで遊ぼうと思い、Pythonで文字列を出力するプログラムを作った。
この記号は何を示しているの？
BrainFuckは8種類の記号しか使われていません。> ポインタをインクリメント （右にずらす）
< ポインタをデクリメント (左にずらす）
+ ポインタの値をインクリメント
- ポインタの値をデクリメント
. ポインタの値を出力
, 入力から1バイト読み込んで、ポインタが指す値に代入
[ ポインタの指す値が0なら、後の]までジャンプ(要するにwhile)
] ポインタの指す値が0でなければ、前の[までジャンプ。
https://qiita.com/TomoShiozawa/items/25dcce1540085df71053
< ポインタをデクリメント (左にずらす）
+ ポインタの値をインクリメント
- ポインタの値をデクリメント
. ポインタの値を出力
, 入力から1バイト読み込んで、ポインタが指す値に代入
[ ポインタの指す値が0なら、後の]までジャンプ(要するにwhile)
] ポインタの指す値が0でなければ、前の[までジャンプ。
https://qiita.com/TomoShiozawa/items/25dcce1540085df71053
ポインタとはデータの入る箱みたいなもので、<>で現在地の移動、+-でポインタに入っているデータの値を変化させることができます。
また、[]はwhileのような役割を果たします。
例えば"A"を出力するときは、AのASCIIコードは65なので、以下のようにすればいいはず。
+++++++++++++[>+++++<-]>.
これはPythonで書き換えるとこういう事である。i = 13
text = 0
while i > 0:
text += 5
i -= 1
print(chr(text))
text = 0
while i > 0:
text += 5
i -= 1
print(chr(text))
伝わったか微妙だが、多分これでイメージできたはず。
次に、どのようにPythonからBrainFuckのコードを作るか、そのアルゴリズムを見ていこう。
アルゴリズムを考える
文字コードを取得して、それだけ+を増やしていけばいけそうだが、なるべくコードを短くすることを目標にします。そこで、とりあえず平方数で近づいてから微調整する方法を考えます。
例えば、e(101)からk(107)に移動したいとき、+2を2回繰り返した後に+を2つ繋げるようにする感じです。
こんな具合でやっていけば、なんとかなりそう。
ソースコード
作ったPythonのコードはこんな感じ。moji = str(input("words:"))
code = [""]
now = 0
j = 0
for i in moji:
a = ord(i)
flag = 0
roop = -1
while flag == 0:
roop += 1
if abs(now - a) <= roop**2 + ((roop+1)**2 - roop**2 - 1 ) / 2:
flag = 1
surplus = abs(now - a) - roop**2
if (surplus < 0 and now < a) or (surplus > 0 and now > a):
fix = "-" * abs(surplus)
elif (surplus > 0 and now < a) or (surplus < 0 and now > a):
fix = "+" * abs(surplus)
else:
fix = ""
if a > now:
code[j] = str("+" * roop) + "[>" + str("+" * roop) + "<-]>" + str(fix) + ".<"
else:
code[j] = str("+" * roop) + "[>" + str("-" * roop) + "<-]>" + str(fix) + ".<"
now = a
code.append("")
print(code[j])
j += 1
mojiにHello world!を入力すると、このように出力される。code = [""]
now = 0
j = 0
for i in moji:
a = ord(i)
flag = 0
roop = -1
while flag == 0:
roop += 1
if abs(now - a) <= roop**2 + ((roop+1)**2 - roop**2 - 1 ) / 2:
flag = 1
surplus = abs(now - a) - roop**2
if (surplus < 0 and now < a) or (surplus > 0 and now > a):
fix = "-" * abs(surplus)
elif (surplus > 0 and now < a) or (surplus < 0 and now > a):
fix = "+" * abs(surplus)
else:
fix = ""
if a > now:
code[j] = str("+" * roop) + "[>" + str("+" * roop) + "<-]>" + str(fix) + ".<"
else:
code[j] = str("+" * roop) + "[>" + str("-" * roop) + "<-]>" + str(fix) + ".<"
now = a
code.append("")
print(code[j])
j += 1
++++++++[>++++++++<-]>++++++++.<
+++++[>+++++<-]>++++.<
+++[>+++<-]>--.<
[><-]>.<
++[>++<-]>-.<
+++++++++[>---------<-]>++.<
+++++++++[>+++++++++<-]>++++++.<
+++[>---<-]>+.<
++[>++<-]>-.<
++[>--<-]>--.<
+++[>---<-]>+.<
++++++++[>--------<-]>---.<
眠くて環境構築する気が湧かなかったのでBrainFuckの実行はこのサイトで行った。+++++[>+++++<-]>++++.<
+++[>+++<-]>--.<
[><-]>.<
++[>++<-]>-.<
+++++++++[>---------<-]>++.<
+++++++++[>+++++++++<-]>++++++.<
+++[>---<-]>+.<
++[>++<-]>-.<
++[>--<-]>--.<
+++[>---<-]>+.<
++++++++[>--------<-]>---.<
https://kachikachi.net/brainfuck/
すると、ちゃんとHello world!が出力された。うれしい。
課題
ただ、調べてるともっと短いコードでHello world!を出力するBrainFuckのコードを見つけたので、必ずしも最適解を出すとは限らない。あんまり思いつかないのであとはよろしく。