はじめに

Brainfuckでコードを書いてみたいな〜と思いましたが、コードを書くのがめんどくさそうだったので代わりにpythonに書いてもらうことにしました。
とはいえ、そんなに難しいものは作れないので、文字列を入力したらそれをそのまま出力するプログラムを作りました。

環境

python 3.6.9

実践

愚直な方法

最初に考えたのは、入力で受け取った文字列の各文字をASCIIに変換してその分愚直にポインタをインクリメントして出力しようと思いました。
コードで言うとこんな感じです。

makebf0.py


import os

#すでにhoge.bfというファイルがあれば削除
if os.path.exists("/hoge.bf"):
    os.remove("hoge.bf")

s = input()
array = []

#各文字のASCIIを取得
for si in s:
    array.append(ord(si))

f = open("hoge.bf", "w")
for ai in array:
    for i in range(ai):
        f.write("+")
    f.write(".>")

#改行
f.write("++++++++++++.")
f.close()

これを実行すると

$ python makebf0.py
brainf*ck
$ cat hoge.bf

hoge.bf

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.>++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++.>++++++++++++.

このようなコードが生成されます。

これではコードが長いし、面白くもないので生成されるコードを圧縮してみようと思います。

コードの改善

コードを圧縮するために考えたのはループを使って+の数を減らすことを考えました。
アルゴリズムとしてはループを回す回数をn、文字列のi番目の文字のASCIIをsiとすれば、min(si/n, si/n+1)をループの中でインクリメントして、端数をループの外でインクリメントまたはデクリメントしました。そのうち+の数が最小であるコードを生成するようにしました。
コードとしてはこんな感じです。

makebf1.py

import os
import math

if os.path.exists("./hoge2.bf"):
    os.remove("hoge2.bf")

s = input()
array= [] #文字siのascii
for si in s:
    array.append(ord(si))

f = open("hoge2.bf", "w")

MAX = 0
for ai in array:
    if MAX < ai:
        MAX = ai

list = [] #差分

#iの決め打ち
for i in range(MAX):
    if i == 0:
        continue
    sum = i 
    for ai in array:

        r1 = ai // i
        r2 = (ai + i) // i

        if ai - r1 * i > r2 * i - ai:
            r = r2 * i - ai
            sum += r2
        else :
            r = ai - r1 * i
            sum += r1

        sum = sum + r
        list.append(sum)

m = 10000000000
for i in range(len(list)):
    #print(li)
    li = list[i]
    if m > li:
        #print(li)
        m = li
        std = i

#ループを回す回数
for i in range(m):
    f.write('+')

flag = []
#ループ中身
f.write('[')
for ai in array:
    r1 = ai // m 
    r2 = (ai + m) // m 
    f.write('>')

    if ai - r1 * m > r2 * m - ai:
        flag.append(-(r2 * m - ai))
        for j in range(r2):
            f.write('+')

    else:
        flag.append(ai - r1 * m)
        for j in range(r1):
            f.write('+')


#ポインタをループカウンタに戻す
for i in range(len(array)):
    f.write('<')
f.write('-')
f.write(']')

#端数を処理する
for i in range(len(array))
    f.write('>')
    if flag[i] < 0:
        for j in range(-flag[i]):
            f.write('-')
    else:
        for j in range(flag[i]):
            f.write('+')
    f.write('.')

#改行する
f.write('>++++++++++++.')
f.close()

実行すると

$ python makebf1.py
brainf*ck
$ cat hoge2.bf

hoge2.bf

+++++++++++++++++++++[>+++++>+++++>+++++>+++++>+++++>+++++>++>+++++>+++++
<<<<<<<<<-]>-------.>+++++++++.>--------.>.>+++++.>---.>.>------.>++.>++++++++++++.

かなりコードが圧縮されました。愚直なコードでは921byteだったのに対し、圧縮されたコードでは158byteでコードを生成することができました。やったね。

終わりに

いかがでしたか

筆者はpythonについて書き慣れていなかったため、このコードを書いて少しpythonについて慣れることができました。またBrainfuckについても、おもしろい言語なのでもっと複雑なことができるようにしたいと思います。
もっと良いアルゴリズムや、コードについて良くない点などがありましたらぜひ教えていただきたいです。
ここまで読んでいただき、ありがとうございました。

参考にした記事

https://qiita.com/TomoShiozawa/items/25dcce1540085df71053
https://qiita.com/saba383810/items/39e20b11c71b3dfd2589

pythonでBrainf*ckのコードを書くコードを書いた