How to encode shortest brainf_ck strings 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&lt;[input length]; i++) {
    int charPos = [input characterAtIndex:i];
    int amountToGo = charPos-currentPosition;
    if (amountToGo &gt; 0) {
        for (int b = 0; b&lt;amountToGo; b++) {
            [output appendString:@"+"];
        }
    }
    else {
        int posVal = abs(amountToGo);
        for (int b = 0; b&lt;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!)


  ++++++++++[>+++++++>++++++++++>+++>+&lt;&lt;&lt;&lt;-]>++.>+.+++++++..+++.>++.&lt;&lt;+++++++++++++++.>.+++.------.--------.>+.>.


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


Explain how the loop in the last example works.
Write some code that can turn any string into highly optimized brainf_ck, like the last example.
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. 

[&gt;+++++++&gt;++++++++++&gt;+++&gt;+&lt;&lt;&lt;&lt;-]


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

&gt;++.&gt;+.+++++++..+++.&gt;++.&lt;&lt;+++++++++++++++.&gt;.+++.------.--------.&gt;+.&gt;.


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.