Pixels Camp Quizshow Challenge #2
Milking the COW to the last byte
After a treasure hunt we got to implement an interpreter for COW, an esoteric programming language with a very bovine instruction set. The second challenge started on September 9th and closed on September 16th. The actual goal, on top of implementing a valid interpreter in JavaScript, was to do it in the least amount of bytes possible.
This is how I went on to approach this code golf challenge and submit the smallest interpreter with just 426 bytes. If you want to skip all the steps and go straight to the final submission, here it is.
Get the core structure right
From a quick read on the specification I realized the interpreter would need to have memory, a memory pointer, a list of instructions, an instruction pointer and a register. It’d also need to be able to map instruction tokens or zero-based indices to actual commands.
At this point I neglected the code golf part; there was no need to start mangling variable names straight away (I never had to do that actually). Rather, I focused on avoiding repetition and writing compression-friendly code. To that end, this is what I came up with as the core structure of my interpreter:
This achieved all I needed at that point:
- Command names appear only once.
- The regular expression makes program tokenization very compact.
- Commands can be easily executed via commands[token]() or tokens[index]().
- It’s cheap to move back and forth between instructions by manipulating instruction_pointer.
- The code is highly compressible, as it contains very few reserved words. A switch block, for instance, could get a seemingly similar initial implementation; however, all those case and break words would remain in the compressed output.
My only qualm about this code was the assumption of key order from Object.keys, as it’s not guaranteed by the ES2015 spec. In practice, though, it works as expected in all modern JavaScript engines.
Make it work
Although getting to a low-byte solution was the end goal, I first needed to submit a working one, so golfing was postponed once again.
Before any further implementation I created a simple test suite, which was quite easy to do with some googling and the help of fellow contestants. Then, it was just a matter of implementing the language instructions and making sure all my tests ran as expected. But I didn’t know how exhaustive the test suite was on the other end, so I did it with all the bells, whistles and checks I could think of:
I knew there was still much room for improvement and most checks were probably unnecessary, but I wanted a valid solution that I could improve upon, rather than failing due to some bad input on the other end. After passing it through a compression tool I got 665 bytes, which was already pretty good, but still far away from the final submission.
Factor-out redundancy
Looking at the initial implementation one thing stood out, moo and MOO were identical, so I created a generic token-matching function to be used in both commands:
This was a simple change, but was enough to bring the byte count down to 636 after compression. And… still no code golf.
Remove edge case checks
I couldn’t see more refactoring opportunities at this stage, but all those checks were still in place. It was time to remove the safety belt and see how sloppy the interpreter could go. It turns out, the test suite was very forgiving and I was able to remove a lot of code and got a 578-byte solution.
Remove a not-so-edge case
I noticed the oom instruction was absent from my test suite. But my submissions were accepted, so… could it be that the same was happening on the server? This was a little stretch from the “complete interpreter” requirement, but as @chbm would say “this is golf, not COWLINT”, so I went ahead and removed oom from the interpreter. It worked! 550 bytes!
Finish with some serious golfing
From this point onwards it was all code golf. I made a lot of changes all over the interpreter, but it pretty much boiled down to:
- Create a write_char = output_char variable to avoid having output_char twice in the compressed output.
- Create a memory_value variable to hold the last value of memory[memory_pointer] in each iteration.
- Remove the new keyword from the regular expression.
- Use a parameter in arrow functions to avoid writing ().
- Replace if-else blocks with the ternary operator.
- Replace if blocks with an || shortcut.
- Replace ‘moo’ and ‘MOO’ strings with tokens[0] and tokens[7], respectively.
- Replace Array.from with the spread operator.
- Use a string template with tokens.join, so I could omit the parenthesis around the string parameter.
- Add undefined as a parameter to the c function. This meant that the minifier no longer compressed undefined to void 0, but instead used a single-letter variable. Given that c is only called with a single argument (the program), the remaining parameters will be, well, undefined. Also did the same for the registry variable to avoid an assignment.
- Use bitwise the | operator to initialize new memory positions.
- Do pointer assignments while accessing array positions.
- Omit the curly braces from arrow function bodies. This was possible because the previous steps turned all commands into expressions.
The final solution
After all that golfing I only had to compress the code and remove var declarations and unneeded parenthesis from the minified code. And that’s it, 426 bytes:
Conclusion
This was my first time doing this kind of challenge. It was a fun experience and I got to learn some dark corners of the JavaScript language. With a bit more time I think I could get close to the 410-byte mark; for instance, I forgot to optimize the regular expression, which could be simplified to something like /[mo]{3}/ig.
Also, keeping the source code readable until the end played an important role in my ability to do all that final golfing and still understand what was going on. Letting compression and code transformations to the minifier allowed me to focus on removing logic instead of shortening variable names or doing while-to-for transforms. As Knuth once told us, “early optimization is the root of all evil”, and that mantra served me very well for this challenge.
OOO MoO MoO MoO MoO MoO MoO MoO MoO MMM moO MMM MMM moO MMM MOO MOo mOo MoO moO moo mOo MMM moO MMM MMM moO MMM MOO MOo mOo MoO moO moo mOo MMM moO MMM MMM moO MMM MOO MOo mOo MoO moO moo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo mOo mOo mOo MMM moO moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo mOo mOo mOo MMM moO moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo mOo mOo MMM moO moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo OOO moO OOO mOo mOo MMM moO MMM MOO MOo moO MoO mOo moo mOo mOo MMM moO moO MMM MOO MOo moO MoO mOo moo moO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO MoO Moo mOo