How to encode shortest brainf_ck strings

6

This is an interesting one.

I have written a short program in objective-c to encode a string into a brainf_ck string, this is what it looks like:

NSString *input; // set this to your input string
NSMutableString *output = [[NSMutableString alloc] init];
int currentPosition = 0;
for (int i = 0; i<[input length]; i++) {
    int charPos = [input characterAtIndex:i];
    int amountToGo = charPos-currentPosition;
    if (amountToGo > 0) {
        for (int b = 0; b<amountToGo; b++) {
            [output appendString:@"+"];
        }
    }
    else {
        int posVal = abs(amountToGo);
        for (int b = 0; b<posVal; b++) {
            [output appendString:@"-"];
        }
    }
    currentPosition += amountToGo;
    [output appendString:@"."];
}
NSLog(@"%@", output);
[output release];

Now I could ask you to optimize that code.

Or, I could ask you to optimize the bf code it produces?

EXAMPLE: Output of 'Hello World!' from my code (365 chars)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.-------------------------------------------------------------------.

EXAMPLE 2: Now, looking at that code, I could probably shorten it by putting reset to zeros in, for a start... (290 chars - 75 improvement)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.[-]++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.[-]+++++++++++++++++++++++++++++++++.

But this takes it a step further... output of 'Hello World!' from some sample code I found on the internet: (111 chars, 179 on last, 254 on original!)

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

Now, I don't know how that loop works, but it does. My question is this:

  1. Explain how the loop in the last example works.
  2. Write some code that can turn any string into highly optimized brainf_ck, like the last example.

Alex Coplan

Posted 2011-08-15T19:58:06.957

Reputation: 209

Please see http://meta.stackexchange.com/q/24079/2509 concerning the spelling on the language on Stack Exchange sites, and I am making this CW in keeping with our policy on "tips" questions.

– dmckee --- ex-moderator kitten – 2011-08-15T20:21:35.607

sorry - thanks for editing if that was you – Alex Coplan – 2011-08-15T21:10:14.593

Answers

1

I can give question number 1. a go:

++++++++++

The first series of +'s defines first memory cell (cell0) to be a loop counter to 10.

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

Above is the loop that executes 10 times. The loop adds 7 to cell1, 10 to cell2, 3 to cell3 and 1 to cell4 for each iteration. After 10 iterations we have the following in the first 5 memory cells: 0, 70, 100, 21, 10

>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Above is kind of self explanatory, it just moves the memory pointer to the value that is closest to what is needed, does some minor inc's and dec's and outputs.

Plarsen

Posted 2011-08-15T19:58:06.957

Reputation: 1 740

great! - that makes sense. trying to write an algorithm to do that will be tricky though... – Alex Coplan – 2011-08-16T17:30:35.410