LebGeeks

Joe

Member

[Exercise] Generate Brainfuck strings

This exercise deals with Brainfuck.

The goal is to write a program (in the language of your choice) that takes a string as an input and outputs the corresponding Brainfuck program that prints that string to the screen.

What you will need:

- You will need a way to run Brainfuck programs. The easiest is to grab an interpreter from somewhere (here for example) or even better yet, write an interpreter yourself.

- A basic understanding of Brainfuck would help. The language is a bit weird but it's easy to get used to. Basically you need to understand the following code (taken from Wikipedia).

+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

- Practicing some basic arithmetics in Bf wouldn't hurt much. Take a look at these exercises, doing these exercises is highly recommended.

- Note that the output for a single string is never unique. There are literally infinite amounts of ways to print something on the screen. If participation is high enough, we could find a way to compare implementations.

Joe

Member

Re: [Exercise] Generate Brainfuck strings

Ok here's a very primitive approach:

def genbf(chvalue):
    bfcode = "+" * chvalue # modify value of the cell
    bfcode += "." # print the approrpriate char
    bfcode += "[-]" # reset the cell value to 0

    return bfcode

print("".join(genbf(ord(x)) for x in "lebgeeks"))

This code can very easily be turned into a one liner.

The simplicity of the code makes me realize how we should compare our programs: the length of the output bf program.

I think I can greatly reduce the size of the output by adopting an approach similar the the Wikipedia Hello World and initializing 4 or 5 counter cells.

geek

Member

Re: [Exercise] Generate Brainfuck strings

Another single-cell approach:

def inc_succ_bf(first, second):
    if second > first:
        return "+" * (second - first) + "."
    elif second < first:
        return "-" * (first - second) + "."
    else:
        return "."

string = "lebgeeks"
print("".join(inc_succ_bf(ord(x), ord(y)) for x, y in zip("\0" + string[:-1], string)))

This is delta encoding; @rahmu's is unary encoding.

Joe

Member

Re: [Exercise] Generate Brainfuck strings

@geek: It's funny. I came up with an extremely similar approach before even seeing your own:

def f(l):
    """ transforms [a, b, c, d, ..., z] -> [a, b-a, c-b, d-c, ..., z-y]
        ex: [3, 12, 10, 20] -> [3, 9, -2, 10]
    """
    a = 0
    for i in l:
        yield i - a
        a = i

    # if input is a list, the code is equivalent to the following one liner.
    # return (a - b for a, b in zip(l, [0]+ l[:-1]))

for i in f(ord(x) for x in "lebgeeks"):
    sign = "+" if i > 0 else "-"
    print(abs(i)*sign)

Next steps:

- multi cells and how to decide which initial setup is optimal. (I'll start with the one given by the Wikipedia example: 70 100 30 10).

- Write large numbers as multiple of factors. For instance 25 should be +++++[>+++++<-] instead of 25 "+" signs.

Any tips?

Joe

Member

Re: [Exercise] Generate Brainfuck strings

Here's a simple approach using 4 cells initialized at values (70; 100; 30; 10).
Since it's so easy to create comments in Bf, I've modified the output to show the state of the cells at any point and make my code clearer.

intro = "intro: ++++++++++[>+++++++>++++++++++>+++>+<<<<-]> (70; 100; 30; 10)\n"
print(intro)


def char_bf(s):
    current_state = [70, 100, 30, 10]
    current_position = 0

    for i in (ord(c) for c in s):
        bf = ""
        b = min(enumerate(x-i for x in current_state), key=lambda x: abs(x[1]))

        target_position = b[0] - current_position

        # mv the cursor to the target cell
        move_sign = ">" if target_position > 0 else "<"
        bf += move_sign * abs(target_position)

        # set the target value
        val_sign = "-" if b[1] > 0 else "+"
        bf += val_sign * abs(b[1])

        current_position = b[0]
        current_state[b[0]] = i

        bf += "."

        yield chr(i), bf, str(tuple(current_state)).replace(",", ";")
        
        
string = "Hello Lebgeeks!"
for i in (char_bf(string)):
    print(" ".join(i))

Output

intro: ++++++++++[>+++++++>++++++++++>+++>+<<<<-]> (70; 100; 30; 10)

H ++. (72; 100; 30; 10)
e >+. (72; 101; 30; 10)
l +++++++. (72; 108; 30; 10)
l . (72; 108; 30; 10)
o +++. (72; 111; 30; 10)
  >++. (72; 111; 32; 10)
L <<++++. (76; 111; 32; 10)
e >----------. (76; 101; 32; 10)
b ---. (76; 98; 32; 10)
g +++++. (76; 103; 32; 10)
e --. (76; 101; 32; 10)
e . (76; 101; 32; 10)
k ++++++. (76; 107; 32; 10)
s ++++++++. (76; 115; 32; 10)
! >+. (76; 115; 33; 10)

Joe

Member

Re: [Exercise] Generate Brainfuck strings

And just for fun here's an implementation of the above code ... in Brainfuck.

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

To make myself perfectly clear, this is a Brainfuck program that once executed will produce a Brainfuck program that once executed will output the words "Hello Lebgeeks!". :)

NuclearVision

Member

Re: [Exercise] Generate Brainfuck strings

Here's my code in python, I'll be writing another one involving deriving cells values from one! but that's my code for now

printable=list(""" !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~""")
#s=raw_input("enter string!");
s="Hello Lebgeeks!"
print "".join([str(i*("+")+".>") for i in [ 32+printable.index(str(i)) for i in s]])

For instance, "Hello Lebgeeks!" produced

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

I used this bf compiler

Last edited by NuclearVision (April 1 2014)

NuclearVision

Member

Re: [Exercise] Generate Brainfuck strings

Okay I got to a more elegant output, by rewriting my code from scratch:

printable=list(""" !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~""")
#s=raw_input("enter string!");
s="Hello Lebgeeks!"
def makebf(n):
       return "++++++++++["+">"+(n/10)*"+"+"<"+"-"+"]"+">"+(n-10*(n/10))*"+"+"."

print ">".join([makebf(n) for n in [32+printable.index(str(i)) for i in s]])

"Hello Lebgeeks!" produced:

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

Last edited by NuclearVision (April 1 2014)