John Fremlin's blog: Cheating at codegolf with System V IPC

Waiting for updates: connected

Codegolf is a about writing the shortest possible program for a task. Shinichiro Hamaji (Japanese) runs an excellent golf competition on golf.shinh.org. You can play in a very wide selection of languages, and the entries are generally extremely high quality. It's a good way to evaluate how well you've mastered a language.

I occasionally look in on it, and once was briefly the winner in Perl, before tybalt89 came along and beat me. I sweated for hours until I equalised his solution:

$/=<>;print y/*///5,"
"for<>

In fact I found the same solution as him. Several other people found it too but yibe achieved the same score another way:

#!perl -aln055
print@F/3if@F

Isn't perl fantastic?

You might imagine that codegolf has nothing to do with real world programming, which should be about readability, robustness and so on. Well, certainly there is no point stripping your real programs of all whitespace and comments, but if you think that's what codegolf is about then you are missing the point. It's like saying that being great at fifty metre rifle prone competitions is no use in a firefight. True it's not the same game, but I'd rather have a fifty metre champion on my side than someone picked randomly off the street. Many of the people playing on golf.shinh.org are absolutely first rate programmers by any metric. They're better programmers than me at any rate.

Codegolf requires you to look in a fresh way at the algorithms you are using. In my opinion, the C competition is especially fun, because you can get away with all sorts of hijinks exploiting the way the code maps to the underlying machine in a predictable way. For example, don't waste time declaring any buffer sizes, just assume there is enough space due to page boundaries. Don't pass arguments to functions, as the right value is in the right register anyway because it was the return value of another function. I think this solution by nn

main(_,s){for(;gets();)strpbrk(s,"DMOPW")+strlen(s)-6||puts();}

for finding anagrams is a good example. What is going on?! Surely puts takes an argument? And clearly it's not truly finding anagrams at all :-) After I got a good score on the perl count diamonds, I thought I would try my hand at the C competition but got nowhere. These guys are at another level.

I was talking to leonid on the IRC channel (one of the wizards at the ruby contests) and he explained that he sometimes repeatedly submits programs that have a low but non-zero probability of producing the correct output until they pass. Ingenious.

Now given that I am not good enough to compete but nonetheless love winning, I decided to cheat. The deadline for totients was coming up. Writing a file somewhere then reading it in with a later submission is apparently stopped, so I thought about the old security exploit trick of filling up memory with many copies of the solution in one submission then printing it out in another. Unfortunately, as far as I know, there is no way to read uninitialised memory under Linux without being root.

This was not going to fly. But what about my old favourite, System V IPC message queues? I used them in my init replacement called jinit because they don't need the filesystem, and in 2001, I wrote a Python interface to them. They allow you to pass datagrams between programs with permission checking. They're not too well known (and rather odd anyway) so maybe shinh hadn't closed off this loophole. . .

After a bit of fiddling I got a solution out that beat the best goruby program (for a total of 46 bytes)

a[];main(){msgrcv(msgget(8,0),a,a,0);puts(a);}

On AMD64, you can drop the trailing 0 arguments (I had to use gcc -m32 to test the 32-bit version locally). The queue was primed by this semi-compressed program (that could be improved in nearly every way) which actually calculates the totients (the function c(a,b) is true iff a and b are not coprime — for some reason I mistakenly estimated that subtraction would be shorter than implementing Euclid's algorithm normally, just change the - to a % for a major speedup; you can also eliminate the a>b check I think).

char msg[10000],*m=msg;
i,j,k;
c(a,b)
{
  if(b<2)return 1;
  return a-b&&(a>b?c(a-b,b):c(b,a));
}
t(a)
{
  j=0;
  for(i=a-1;i;i--)j+=c(a,i);
  m+=sprintf(m,"%d\n",j);
}
char buf[9990];
main()
{
  int q=msgget(8,01777);
  for(k=0;301>k;++k)t(k+10000);
  msgsnd(q,msg,m-msg-5,0);
}

Note that in the finest tradition of horrible hacks you have to change the -5 to -9 in order for it to work on 64 bit (the message length does not include the first word which is the message type).

The next best C program was 97 bytes by the mighty nn. This may not be a fair way to win, but dammit, it feels better than not winning at all.

PS. For shinh to stop this chicanery, disable the sysv ipc mechanism. For example,

echo 0|sudo tee /proc/sys/kernel/msgmax|sudo tee /proc/sys/kernel/msgmni

PPS. If you play codegolf, and I urge you to, don't forget to remove the newline at the end of your file (there is even a caddy to help with this sort of thing).