tl;dr: We had a codegolf challenge recently. My C-solution was 246 byte, the perl-winner was 191. I decided to give notes for C-golf beginners
Note: Most of this blog post is incredibly boring. A better way than to
read through it is to just skip through the git-repository and refer to the
explanations here everytime you don't know why a change works or what it
does. To make this easier, I added ankers to every paragraph, named by the
commit of the change it explains. So if you want to know, how a specific change
works, you can add
#commitid to the url of this post, with
the full id of that change. If you want to read the more interesting
stuff, from about here it starts
to get non-obvious I think.
At the rgb2rv10 we again had a codegolf event. C is generally not a preferred language for golf, but I use it, because I know it best and my experiences with it are not that bad. My C solutions are most of the times longer then the shortest solutions in perl or similar languages, but they are competitive. That's why I decided to make a blogpost explaining this years C solution as an example to show some basic C-golfing techniques.
This years challenge was to implement an interpreter for esocalc, a two-dimensional language for arithmetic expressions. Follow the link for a more detailed specification. This challenge is primed to be solved in C. This is also reflected by the length of the different solutions: The shortest C solution is 246 bytes, the shortest Python solution is 227 and the shortest Perl solution is 191 bytes. For a codegolf-challenge this is an impressively small gap between C and scripting languages.
You can follow this post by checking out the code
on github. The oldest commit is the one we are starting with and we will refine
it until we reach the 246 byte solution in
master. You can test it by
compiling it (
gcc -o golf golf.c should suffice in most cases, the shortest
needs a longer commandline, which is put in the Makefile, so you should
it). You can run it through the testsuite used in the contest by running
GOLF_BIN="./golf prove -l".
The first step is to implement an easily readable, working version. This is done in the first commit. Though you yourself might have come up with a different implementation, this is pretty straightforward I think. We just read the whole esocalc-sourcecode and walk through it, executing every instruction as we go. The stack is statically allocated and of a fixed size, but that's no problem because we only have a limited testsuite anyway.
The next step is obvious: We remove comments and move to one-letter variable names, thus reducing readability, but also size considerably. We will leave most of the whitespace for now, because else it is hard to follow the changes.
An important lesson for C-golfers is the following: for is never longer then
while and most of the times shorter. An endless loop with
while takes one
character more then a
for-loop. We will later see more instances when
be considerably shorter. Also, we see the
else-constructs in the
control-flow instructions. It is considerably shorter to use a ternary operator
in most cases, because in C, most statements are also expressions, so we can
write them as cases in
?: - or use the short-circuiting
&& if there is no
else-part. We will see more of that later. Lastly we collapse multiple
variable declarations into one to save
int-keywords. These three changes are
what happend in the next version.
We continue in our path and notice, that we every
char-literal takes three
bytes, while the number it represents often only takes two in decimal.
Let's fix that.
We also have two temporary variables
b, that we shouldn't need.
We can get rid of them,
by thinking up a single statement for arithmetic operations.
The next step
uses a real detail of C: If you don't give a type for a global variable, a
parameter or the return type of a function,
int is assumed. If a function is
not defined, a prototype of
int foo() is assumed, meaning we can pass
arbitrary arguments and get an
int. The libc is linked in by default. All
these facts means, we can drop all
includes and put our variables in the
global scope to remove all
int-keywords. This is a very basic, but very
usefull technique. It has one important caveat, you should look out for: If you
need the return value of a libc-function and it is not
int, you should
think about wether it can be safely converted. For example on amd64 an
has 32 bits, but a pointer has 64 bits, therefore pointers as return values get
truncated (even if you assign them to a pointer).
We can save more
by using a parameter to
main. This is also a very basic and often seen trick
in C-golfing. You get up to 3 local variables for free this way. In our case
there is an additional benefit: The first parameter to
main is the number of
arguments, which is 1 for a normal call (the first argument is the name with
which the programm was called). This means, we get the initialization to 1 for
A trivial optimization
gets instead of
gets always adds a terminating zero-byte,
so we need to grow our buffer a little bit.
If we now look at our code, all the
case-keywords might annoy us. If we see
a lot of repititions in our code, the obvious tool to use in C are
the structure of the cases and replace every case by a short 1-letter identifier.
The same goes for the arithmetic operations: Four times the same long code cries
for a define.
define is not always a good solution. You have to weigh the additional
overhead of the keyword and the needed newline against the savings and number
we eliminate the variable
i. Skilled C-coders use pointer-arithmetic quite
often (no matter how bad the reputation is). In this case it would be a bad
idea, if we were not explicitely allowed to assume that all programs are
correct and stay in the bounds given (because bound-checks are a lot harder
Another example of savings by
the next change.
Here we moved two statements into the
for-loop, thus using the semicolons we
need there anyway and saving two bytes.
So the next big thing that catches our eyes are the
break-keywords. Everytime you see long identifiers or keywords you should
think about wether a different program-structure or a different libc-builtin
may help you save it.
switch-construct can almost always be replaced by an
else if construct (which is why we learned to use
switch anyway). This
is often shorter, but as we learned, the ternary operator is even shorter. So in
the next step
we use a giant ternary expression instead of a
switch-structure. This brings
one major problem:
return is one of the few things that's a statement, but
not an expression. So we can't use it in
?:-expressions (because the branches
have to be expressions). We use
exit() instead, which is an expression, but a
void-expression, so again we run into problems using it in
?:. We work
around that for now by using
(exit(0),1) instead. If you connect expressions
, they are evaluated in succession (contrary to using boolean operators
for example) and the value of the last one is becoming the value of the whole
expression - so our
exit-expression evaluates to 1 in this case.
exit is still pretty long (especially with the added parens and
comma-expression), so we want to avoid it too. Here comes a notable quote of
the organisator of the competition into action: “The return value isn't
important, as long as the output is correct. So it doesn't matter if you
segfault or anything”. This is the key to
the next change:
Instead of exiting orderly we just create the conditions for a segfault by
assigning zero to
p, which is dereferenced shortly thereafter, thus creating
a segfault when we want to exit. This is one of my favourite optimizations.
There still is some repitition in our code. We still assign to
d more often
then not. But our big nested ternary operator doesn't return anything yet. So our
is to return the new value for
d in all subexpressions (if need be by using a
comma). This does not save a lot, but still a few bytes.
Now the sources of bytes to save are getting scarcer. What still is a pain is
the explicit stack of a fixed size. Here another deep mistery of C (or more
specifically the way modern computers work) comes into play:
The call stack. We can actually
use this as our stack.
The way this works is, that we use a pointer to an address in the memory area,
the operating system reserved for our call stack and grow down (contrary to the
illustration on wikipedia, the stack grows downwards. But this is a minor
detail). By writing to this pointer and decrementing, we can push to the stack.
By incrementing it and reading we can pop something from the top of the stack.
To get a valid stack-address we could use the address of a local variable (for
s itself). Local variables are at the bottom of the stackframe, so we
do not overwrite anything important if growing down. There is however a
problem: We call
printf which push a few stackframes to the
callstack. Our stack would get smashed by these calls. Therefore we just
subtract a sufficiently high number from it to reserve space for the
stackframes of the function calls. 760 is the minimum amount needed in my
setup, everything up to 99999 should save at least one byte.
This still is unsatisfactory, so we will hack a little more and use the fact,
that the testsuite only uses quite small programms and a quite small stack is
needed. So we just
which is absolutely crazy. I discovered (by accident), that you will always end
up with a pointer to your program-array, using around 200 bytes of the end
(most probably some earlier deeply nested call in the startup of the binary
will write an appropriate address here by accident). This of course is
borderline cheating, but it saves 6 bytes, so who cares. From now on it's
absolutely forbidden to compile with optimizations, because this will destroy
this coincidence. Oh well.
So, if we are already doing unreliable horrific voodoo which will curl up the
fingernails of every honest C developer, we can also
save two bytes
by not setting
p to zero, but instead just doubling it. You will then end up
with some address, that is hard to predict, but in all cases I tried leads to
crashing just as reliable. This means, we exit our program in just one byte. Neato!
There is not a lot we can save left now. What might still annoy us and is a
very good tip in general are all this numbers. Even if most characters have
only 2 bytes as a decimal, they still only have one byte as a character (not a
char-literal!). We can
by passing a verbatim character as the first argument to the
interpret it as a
char, we stringify it (with
#a) and dereference it (with
*#a), getting the first
char. This opens a problem: A space is a
significant character in the interpreted source code, so we need to use it as
an argument. But a space is not significant at that point in the C source code,
so we simply can not pass it to our makro. The solution to this is to move the
whole ASCII-table. So instead of comparing
*p we compare
be choosen. Thus we don't need to pass a space, but some other char, that is
n positions away and everyone is happy. Kind of. We also need to avoid single
quotes, double quotes (though we can avoid this by using emtpy string (think
about why this works), but too many bytes!!!), parenthesis and chars outside of
ASCII (because this will break our C-file). These constrictions make
pretty much the only choice. This means, we have to include a DEL-character in
our source-code, but the compiler is quite happy about that (the wiki isn't,
github isn't, the editor isn't, but who cares). This is my second most favourite hack.
This leaves us with 253 bytes. To get below 250, we use buildflags instead of defines. Usually such flags are counted by the difference they add to a minimal compiler call needed. In this case, we have a 186 byte C-file (after removing the trailing newline added by vim) and 60 bytes of compiler-flags, totalling 246 bytes.
I think there still is potential to remove some more characters. Other tools
not used here include
(which are kind of hard in C, because it lacks an eval, but some variations of
the concept still apply) and magic formulas. If the testcases are very limited,
some people resort to hardcoding the wanted results and just golf a minimal way
to differentiate between what output is wanted. This might be surprising, but
in many cases (this included) this will end up being shorter (though I consider
it cheating and try to avoid it). We also didn't do a lot of
bit banging. For example using
== reverses the check but saves a byte. But I think it is a
usefull intro for people who are just learning C and want to dive deeper into
the language by golfing.