How to encode shortest brainf_ck strings

Question

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.

Answer 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.