AKA Learn You A Brainfuck For Great Good
As part of the Advent of Code, my challenge has been to try and solve several of the puzzles using Brainfuck: a minimalist esoteric programming language with only 8 instructions. I wrote at length about this process (and how i use a custom transpiler to save myself from having to having to copy and paste snippets of unreadable gibberish) in this earlier post.
Last night, i have completed what is probably going to be my last attempt of the year: part 1 of day 9. The resulting file is monstrous: 296261 instructions, that took six and a half hours to run after compiled by an optimizing compiler (bfc), and i had to tune the compiler's option for it not to segfault... Turns out bubble-sorting 11k+ elements in brainfuck is slow, who would have thought? :D
And since this was such a challenge, i thought i'd write a quick something about how i wrote this monstrosity, and how to write brainfuck programs in general.
since writing the first post, a few things have changed. First: part2 exists. But, most importantly: part 1 now runs in 80 minutes, and no longer in 6 and a half hours!
Turns out there were two big ways of optimizing that implementation:
- the
followfunction checks whether the tail is close enough to the head; if we keep that boolean on the stack, we can avoid adding the tail to the list of points that need to be sorted later - doing an insertion sort into the list while creating it is much faster than fully creating it then doing a bubble sort, at the price of being significantly more complex