I started the puzzle very optimistically and did a breadth-first search into the next N characters, looking for the runes having states closer to the sentence I want to spell. I came up with the idea of using a lookup table to store the shortest distances going from one letter to another, taking into account going over zero and using [-] to reset the rune. At that time I did not see the loops part and did not use them. The result length was 5.9k which was disappointing for me.
Then I looked at the repetitions in the output Brainf**k code and put them into loops. I liked the generality of this approach. The restriction here is that the memory state has to remain intact after the loop finishes. I also searched, for every number of repetitions required, the optimal loop counter and increment/decrement setting. For example a 13x loop of (.) will be >+[<.>++], after this my score dropped to about 4.4k, which I believed could have been better.
Then I looked at the redundancies within the magic phrase itself, and hand-optimized on a case by case basis. I checked the average of the phrase and whether it is better to initialize the runes to M's first, I checked the frequencies of words and letters and initialise the runes with them. Other cases like GAAVOOOLLU, BALROG and the two words case are very interesting and have been optimized individually. The validation cases turned out to have very similar performances as the test cases.
In order to get to this level I have completely taken the program offline and worked on it on my Visual Studio. I also created a versioning tool to keep track of the best outputs of each test case, and the version of the program used to achieve it. This helped me a lot to manage mistakes and keep track of breakthroughs.
Finally I cleaned up the code and gained a few characters by observing that '<>', '+-', are redundant, and that any character other than a '.' at the end is useless. Also a program starting with > or < can be trimmed. I am now ranked #17 with length 3378.