brhfl.com

A quine is a program that does nothing but output its own source code. In various programming challenges (notably, on PPCG) the word is often generalized to refer to those which are somehow related to this behavior – print the source code backward, input n and print n copies of the source, etc. An interesting challenge from 2013 floated to the top of PPCG this week a few weeks ago (I’ve been sitting on this post for a while), Print every character your program doesn’t have. While I don’t particularly feel the need to dive into everything I attempt on PPCG, this was a very interesting challenge in how seemingly trivial decisions that appear to shrink the code could have very well ended up growing it.

The premise was, for the printable ASCII set, print every character not present in your source code. In dc, the sort of baseline solution to beat is one which simply contains and comments out every single printable ASCII character, # !"$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ – 95 bytes. So that’s the thing to beat. Even if I couldn’t beat it, I’m not sure I would have submitted that – it’s just so boring¹. My strategy was to:

• Use as few characters as possible in order to
• Print every character from the ASCII printables unless
• It’s in a prepopulated list of characters used in the code

The program, then, starts by pushing a list of ASCII code points that we need to exclude onto the stack, which I’ll get to after the fact. The meat of the program is [l.dP]s;34s.[dl.!=;s,l.1+ds.127>/]ds/x. This defines two macros, ; and / and runs / (as main essentially). Originally I had thought I would name all of my registers (macros included) with characters otherwise already used in the code, so as to not add bytes to the exclusion list. But because I (probably) needed every digit between 0 and 9, my list was already going to be partially incrementally generated, and since I needed > and < which are just a few code points away from 9, it was actually beneficial to introduce the ‘missing’ characters into the code to factor more into the incremental generation process. Theoretically, I could comment out some of these characters, but then I’d have to add the comment character, # to the list as well.

The macro / is rather straightforward. It duplicates top of stack, compares it to the counter ., runs the printing macro ; if they don’t match, ‘drops’² the top of stack (which has an extra value on it if ; ran), increments the counter ., and continues running as long as we’re still below 127. The macro ; does nothing save for printing the ASCII value of . and leaving some padding on the stack – since / always deletes an item from the stack, we want it to be unimportant unless it’s removing an item from the list of exclusions.

Our list of exclusions is 120d115 112 108 100 93 91 80 62[d1-d48<:]ds:x45 43. We’re printing from low to high, so we make sure that from top to bottom, the stack is also arranged low to high. Since we compare our current ASCII value to this list of exclusions every time, we need to make sure there’s always something on the stack to compare to, so our largest/last value is duplicated. There’s a little decrementing macro in there to automatically push every value from 62 to 48 – the digits 0-9 as well as the aforementioned nearby characters that I used for macro names, etc. I tried generating the list in a handful of different bases – either to reduce bytes with fewer digits or to reduce exclusions with fewer possible numerals. In every case, the code to switch bases plus the overhead of adding that command to the exclusions list made it longer than simply using decimal.

This was an interesting challenge, one that I didn’t readily think I could beat the straightforward solution to. Many of the things that worked in my favor were counterintuitive – like introducing more characters that I had to exclude.