Hi,
Thanks CvxFous, an extremely enjoyable challenge! I feel like the format along with the time constraint was chosen really well.
I scored 23rd with 3700 score. Although it is good, I am still a little disappointed with myself, the guys in the first few positions were very clearly on a different level of generation and optimisation. I used greedy techniques, which was probably what separated the first few places from the rest. However, I can’t even begin to think how to globally optimize for a problem like this
My main breakthroughs were because of the brainfuck algorithms page and this other one which talks about language optimization when compiling from brainfuck to C. The first one had some really neat tricks like [-] to 0 a cell, [>] to move to the rightmost empty cell, etc. The second one gave me the idea to try and post-process my code (which is not really relevant to the contents of the code, although the contents are still interesting).
The biggest breakthrough was definitely the post-processing. I.e. generating some functional code first, then searching for recurring patterns, replacing them with loops and checking the instruction count gain/loss. This allowed me to go from ~6k instructions to 3,9k. Given my algorithm was greedy and post-processing was such a success, any pre-processing optimizations actually ended up giving me worse results.
I tried:
- Analysing letter frequency and trying to keep the most frequent ones on the memory, unless the alternative had really poor score
- Doing pre-seeding on the memory to have random letters from the start, to allow reaching others easier
- Using
[-]--and[>]type fastmoves - Others, which I forget
Although before post-processing these yielded improved code-lengths, it proved that overall they achieved solutions which optimized worse with loops.
Yeah, anyway, great fun. Thanks for the challenge!