brhfl.com

Code golf is a quirky little game – complete the challenge at hand in your preferred programming language in as few bytes as possible. Whole languages exist just for this purpose, with single-character commands and little regard for whitespace. dc always seemed like a plausible language for these exercises, and I recently attempted a few tasks which I would not ordinarily use dc for, notably 99 Bottles of Beer.

It’s a simple enough task – count down from 99, perform some string concatenation, and be done with it. But a bit of a spanner is thrown into the works in that last verse – suddenly, you need to factor in pluralization; you need to change the 2^nd line; and you need to restart the counter at 99:

[…]
3 bottles of beer on the wall, 3 bottles of beer.
Take one down and pass it around, 2 bottles of beer on the wall.

2 bottles of beer on the wall, 2 bottles of beer.
Take one down and pass it around, 1 bottle of beer on the wall.

1 bottle of beer on the wall, 1 bottle of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.

My initial attempt was 269 bytes long:

[ bottle]sa[[s]P]sb[ of beer]sc[ on the wall]sd[, ]se[.]sf10sg[[Take one down and pass it around]Pq]sh99si[ll1<b]sj[li1<h[Go to the store and buy some more]P]sk[99+dsl]sm[li1-dddslsi0=mn]sn[lidslnlaPljxlcPldPlePlinlaPljxlcPlfPlgPlkxlePlnxlaPljxlcPldPlfPlgdPPli0<x]dsxx

It used two counters (l and i) and a lot of wasteful negotiating between the two in order to balance out the pluralization and beer count reset. A couple of bytes could be shaved off here and there – use the stack instead of a variable load for the decrement loop conditional, use the ASCII value 46 instead of the three-character string [.], but ultimately the design was flawed. Refactoring brought me where I am now, 237 bytes:

299si[lid1-dsi3/li3>vdn[ bottle]P1<n]sm[[s]P]sn[ of beer]so[ on the wall]sp[, ]sq46sr10ss[[Take one down and pass it around]Pq]st[d4<t[Go to the store and buy some more]P]su[99+]sv[lmxloPlpPlqPlmxloPlrPlsPluxlqPlmxloPlpPlrPlsdPP3<z]dszx

Unfolded…

1. Initialize our counter i to 299: 299si
   
2. m decrements the counter, duplicates that value (we need it at the end to check if our loop should keep going), divides it by 3, checks our counter, and runs v to add 99 if we’re at our final print. It prints (number of beers) bottle, and runs n to print “s” if we have multiple beers: [lid1-dsi3/li3>vdn[ bottle]P1<n]sm
   
3. n is our pluralizer, all it does is print “s”: [[s]P]sn
   
4. Just a string: [ of beer]so
   
5. Just a string: [ on the wall]sp
   
6. Just a string: [, ]sq
   
7. Save a byte using ASCII instead of a string (period): 46sr
   
8. Save a byte using ASCII instead of a string (linefeed): 10ss
   
9. t is largely just a printed string, but the quit command acts as an else in conjunction with the macro (u) that calls it: [[Take one down and pass it around]Pq]st
   
10. u runs t if we’re not on the last verse. It would then print the ‘Go to the store’ string, except that we used that quit command to back out: [d4<t[Go to the store and buy some more]P]su
    
11. v magically produces 99 additional beers. Nice!: [99+]sv
    
12. Our main loop runs the printing macros, prints the simple strings, checks the counter and runs itself if we still have song to sing. The trailing x command starts the loop running: [lmxloPlpPlqPlmxloPlrPlgPluxlqPlmxloPlpPlrPlgdPP3<z]dszx
    

Decreasing the byte count (golfing the code, so to speak) required getting rid of as much bulky counter manipulation as possible. dc starts with a default precision of 0 places, so we can use one counter decrementing by one every time from 299 to give us two values: how many beers (i/3) and which print operation we’re on (i).

dc as a golf language, then

dc seems like it would make for a good golf language – it is stack-based, all commands are a single letter, and whitespace is generally unnecessary. Yet far more verbose languages have far smaller answers, largely because dc’s command set is so limited. Everything string-related is a stack operation; there are no string manipulation abilities. Strings aren’t even truly concatenated, they’re just printed without newlines. There are 17 printing commands¹ in those 237 bytes. I could theoretically do some of this printing in a loop, but I need so many conditionals that various P loops would likely add as much as it golfs. Not to mention ordering would rotate back and forth because of the stack.

Speaking of the stack, one might think there’s efficiency to be gained via stack manipulation, but there just aren’t many commands for that either. It’s a theoretically infinite stack (like RPL), so there’s no concept of rolling over, and there’s no RPN z level for repetition. There’s no picking (arbitrary roll), nor is there even a standalone drop. You basically do things that push and pop, and the only manipulation you get is a single-level swap (reverse). dc expects you to use registers.

Decrementing (or incrementing) a counter is quite wasteful. You need to load it onto the stack, li, decrement it, 1-, duplicate the value (because presumably you need it for something and d now is shorter than li later), d, and then store the new value, si.

Two things hadn’t occurred to me before this exercise – it’s smaller (albeit less readable) to store a single-character string low on the ASCII table with its value; and a byte can be shaved off of storing and immediately running a macro a by duplicating vs. storing and loading ([1+]dsax vs [1+]salax). Not particularly useful in day-to-day life, but good for the ol’ brain.

dc is certainly not intended as a full-featured language (it is, after all, just the ‘desk calculator’). Nor was it designed with ‘golfing’ in mind, and its limitations are quite apparent here. But it’s still my go-to calculator on the CLI, abusing it in this manner makes for a good exercise, and the end result wasn’t half bad.