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

Posted 2010-01-12 14:55:00 GMT

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).

Don't say things like `echo 0|sudo tee /proc/sys/kernel/msgmax|sudo tee /proc/sys/kernel/msgmni`. It encourages copy-and-paste adminning, which both allows idiots to do things without learning, and is a potential security risk if an idiot were to copy and paste a command that rm'ed their box. Instead, just say which files to echo 0 into and let the user determine the exact command to use.

Also note you could save a byte by using `sudo echo 0>/proc/sys/kernel/msgmax;sudo echo 0>/proc/sys/kernel/msgmni`

Posted 2010-01-12 16:17:52 GMT by Anonymous

Thanks for the suggestion to save a byte Anonymous, that is always welcome.

However, unfortunately, sudo echo ... > redirect doesn't open redirect as root of course. Doh. That's the point of using tee.

I hope that the people reading this are more than capable of figuring out what to change. There are plenty more vars to fiddle with not just those I mentioned. See sysctl.conf.

Posted 2010-01-12 17:16:41 GMT by John Fremlin

Actually, if we're playing this game properly, I think echo 0 | sudo tee /proc/sys/kernel/msgmax /proc/sys/kernel/msgmni

Or even, cd /proc/sys/kernel/;echo 0|tee msgmax msgmni

Can anybody do better? :-)

Posted 2010-01-13 13:07:59 GMT by John Fremlin

Very interesting indeed, I might look into code golfs in the future.

Posted 2010-01-15 22:03:11 GMT by Henrik H

Interesting cheat. This article about codegolf http://www.perlmonks.org/?node_id=763105 describes a couple of other codegolf cheats. Keeping up with tybalt89 is impressive, as he is one of the all time golfing greats.

I don't agree with your assertion that "doing well at codegolf is a good way to evaluate how well you've mastered a language". I argued the opposite point of view in http://www.perlmonks.org/?node_id=761053 namely that it is possible to win at codegolf while being a relative language ignoramus by finding a good algorithm, and being tenacious and devious.

Posted 2010-01-17 00:02:29 GMT by eyepopslikeamosquito?

Thanks, that's a great article.

You're right that you can get a great golf solution without knowing a language well, but (provided you aren't doing an automatic search for a solution) you will spend a lot of time in the language documentation. This will hopefully indicate to you that you have not mastered it. In normal programming it is easier to stay in your comfort zone.

In fact, even if you know a language/library quite well, you are likely to spend a long time reading the manual trying to scrape an idea out something. For example, I was beaten by youz with http://golf.shinh.org/reveal.rb?Count+diamonds+level+2/youz_1254926721&l in Common Lisp. He used read-delimited-list -- I'd completely forgotten it existed (and such a long name in a code-golf, wow).

The surprising things you learn by playing golf help calibrate your estimate of the number of surprising things you still don't know about a language (i.e. your level of mastery).

Posted 2010-01-20 05:04:19 GMT by John Fremlin

Post a comment