The ICFP Programming Contest 2006

The ICFP Programming Contest is an annual international programming contest, hosted each year by a different programming language research group. It works like this: On a well-known date, the hosts release a problem, usually in the form of a specification, on the Internet. The participants (working alone or in groups) then have exactly three days to solve the problem and to submit their solutions. The solutions are then compared by the hosts (usually mechanically and very objectively) and at some point the results are announced.

The 2006 contest came to an end today and, as in the past five years, I’ve participated as a member of the glorious team “Funktion im Kopf der Mensch”. Last year we were not very motivated by the problem, so we kind of gave up. The four years before, though, we always finished in the top 10 percent.

This year’s problem was not directly specified by the task description. Rather, a virtual machine was specified, and a program to be run on that machine provided. The machine is very simple, so it took us only about an hour to get it running. The result of running the program (called the “codex”) on the machine is another, bigger program, obviously uncompressed by the codex.

The second program is a very simple, UNIX-like “operating system” (or rather an imitation of an operating system), called “UMIX”. The first thing you do is log in as “guest” and see what’s around. There are several home directories, but you don’t have the passwords for those users. However, the guest account contains a BASIC interpreter and part of a program for hacking passwords (similar to the well-known “crack”). Finishing and running that program gives you the passwords for a few users. The stuff in those user’s home directories gives you further clues, so sooner or later you have all the passwords.

The real problems, though, are specified in the user’s home directories. Most of them are in the form of a programming language, for which there is an interpreter, and specifications for one or more programs to implement in that language. For each subproblem you solve, the machine spits out a “publication”, which is a string that gives you points if you submit it on the contest website (though it’s too late for that now, obviously). Usually, the shorter your solution, the more points you get.

The first problem I worked on was the “O’Cult” programming language. O’Cult is a term rewriting system, but instead of having sane rules for how terms are rewritten, O’Cult has one particularly nasty twist: If the rule to be applied can be applied an equal number of times in the main term’s subterms, it is not applied at all, which makes it very easy to reach a deadlock-state, where, although in theory further rewriting could happen, it is not done. My solution was to introduce two new terms, “Down” and “Up”, and guarantee that the whole term always contains exactly one Down or Up. The rules can then be written so as to always include a Down or Up in the left-hand-side, thereby ensuring that no rule’s left-hand-side matches more than once. This problem was pretty easy once I figured out what needed to be done, which wasn’t too difficult either. Here are my O’Cult programs for multiplying two numbers and bringing an “XML”-Term into normal form.

My “big” problem was the “2D” language. It’s basically an ASCII-art language with very basic operations. Here’s how my programs for multiplying two number and reversing a list look like in 2D. I drew those by hand in an editor.

The third 2D-subproblem was implementing a one-dimensional raytracer. Drawing it myself seemed out of the question for me, so I implemented (in Common Lisp) a compiler for a higher-level (functional) language which emits 2D code. My mistake here was not sorting out the theory before I started, because I underestimated the difficulty of the compiler’s task. As a result I had to spend about twice the amount of time that I saved in the implementation of the language with writing the raytracer in a way that the compiler could compile without producing incorrect code. Nevertheless, I got it working, albeit with a bit of cheating. The raytracer is supposed to calculate a fix-point, i.e., apply a step repeatedly until the result doesn’t change anymore. I was much too lazy to implement that as well, so I just figured out how often I would have to apply my raytracer step to pass the verification program. The answer is 9. Here, then, is my 2D raytracer, automatically generated and then manually optimized!

As always, my teammates were at least as successful as I was, so we were at fifth place (out of 346) 8 hours before the end of the contest, when the hosts turned off the online score-keeping to make the last hours of the competition even more thrilling.

Overall, this was quite an exciting contest, although I have to say that I really missed the teamwork that usually comes with it. When you have four people and six problems to solve, the teamwork chiefly consists of figuring out who wants to give which problem a try. My favorite ICFP contest is still the 2004 one. Nothing’s more fun than watching your little virtual ants search for food on a hexagonal grid! ;-)

If you want to try out UMIX yourself or even give a few of the problems a shot, look no further! Download this package, which contains our UM interpreter, the UMIX code and the passwords to all the users.

Advertisements

Lisping Flickr

Flickr provides an API for which there are numerous language bindings. A binding for Lisp was, however, missing, and because I wanted to write an application for automating some tasks in Flickr (more on that later on), I decided some time ago to start by implementing bindings to the Flickr API for Common Lisp, aptly named “Clickr”.

Instead of telling you how great my bindings are I think it’s best if I just demonstrate how they work:

Let’s get my Flickr user first and see what my name is:

CL-USER> (defvar *schani* (user-with-name “schani”))
*SCHANI*
CL-USER> (user-realname *schani*)
“Mark Probst”

How many favorites do I have?

CL-USER> (length (user-favorites *schani*))
1675

Every bit of information that Clickr gets from the API is stored. If you request it again, Clickr will used that stored information instead of making the same API calls again. Also, every Flickr object that Clickr knows about corresponds to exactly one Clickr object. If you get, say, the same photo via two different routes, Clickr will give you the same photo object twice.

Let’s do some more complicated stuff! What’s the number of users whose photos are in my favorites?

CL-USER> (defvar *fav-users* (remove-duplicates (mapcar #’photo-owner (user-favorites *schani*))))
*FAV-USERS*
CL-USER> (length *fav-users*)
805

How many of those have faved at least one of my photos?

CL-USER> (length (remove-if-not #'(lambda (user)
(find-if #'(lambda (photo)
(eq (photo-owner photo) *schani*))
(user-favorites user)))
*fav-users*))
183

This last query makes a huge number of API calls, so try it at your own risk! The second time you do it, though, it’s lightning fast!

Clickr can even provide you with some information not available through the API:

CL-USER> (photo-num-views (first (user-photos *schani*)))
127
CL-USER> (photo-num-faves (first (user-photos *schani*)))
3

I need that information for my little application, and since the Flickr API still doesn’t provide it, Clickr has to fetch the photo page and extract those numbers from the HTML code.

On to my application, which I’ve called “Automatr”! There are lots of groups on Flickr, like top-f or top-v, whose only posting requirements are that your photo fulfills some simple “counting” rule. In the case of top-f the rule is that you can post any image provided that it has at least 25 faves. Being very lazy I wanted a tool that did those posting jobs for me automatically, which is why I wrote Automatr.

Right now Automatr can do five things: Adding and removing tags, adding and removing photos to and from groups and adding photos to sets. Let’s look at the simplest job, adding a tag! Let’s say that I want to add the tag “top-f25” to all my photos which have at least 25 faves. Here’s the Automatr rule for that:

(add-action ‘add-top-f25-tag
‘(add-tag “top-f25”)
‘(>= (count faves) 25))

The first argument is just the name of the rule and can be anything. The second argument is the action and the third argument is the condition under which the action is to be applied. Of course Automatr is smart enough not to try to add the tag a second time, so it’s not necessary to specify that only photos without that same tag be tagged.

Groups are more complicated in that they need to be declared first. Here’s the declaration of the top-f group:

(defgroup ‘top-f
“23561440@N00”
:max-batch 1)

The main argument here is the ID of the group. The easiest way to get to it that I know of is to look it up in the HTML source of the group page. Yeah, it sucks. Clickr should be able to do that automatically if you provide it with the group URL, but I was too lazy to implement that. Anyway, the “max-batch” argument specifies how many photos Automatr is allowed to add to that group in one batch. In this case it’s one, meaning that even if I had a hundred photos eligible for entry, Automatr would post only one, determined at random. Here’s the rule for posting photos to top-f:

(add-action ‘top-f
‘(add-to-group top-f)
‘(>= (count faves) 25))

Pretty straightforward. Here’s a more complicated group declaration:

(defgroup ‘top-v
“56022122@N00”
:max-batch 1
:max-posted 11)

The “max-posted” argument tells Automatr that at any point in time there can be at most 11 photos posted to that group (by the user in question). If Automatr wants to post an additional photo to the group, it has to delete one of the 11 first. The photo to be deleted is, again, chosen at random.

That’s basically it. If you want to play around with Clickr and Automatr yourself, just download it and follow the README file in the package. If you do something with it, I’d love to hear from you!

Zooomr is up again…

Zooomr is up again and at version 2.0 (despite still being beta – go figure!). I had hoped that they would implement some community-building features, similar to Flickr‘s favorites and groups, most importantly. Unfortunately, that didn’t happen. What they did do was expand on the stuff I’m completely uninterested in, like GeoTagging. It still remains practically impossible to find good photos on Zooomr, something which has become very easy on Flickr.

So, I guess if what you want is sight-seeing by map then Zooomr’s the thing for you. If you’re more interesting in photography then Flickr’s still the place to go. I had hoped for a real competitor to get the Flickr crew to implement some new features, but Zooomr won’t be a contender soon. Well, maybe when it’s at 3.0…

Zooomr’s giving away free Pro accounts

and I need one! Well, actually, I don’t need one, but I still want one, so I have to host a Zooomr photo here:

GabiGabiHosted on Zooomr

Call me a corporate whore if you want, I don’t care!

Speaking of Zooomr: It was hyped as a “Flickr-killer”, but turned out to be pretty boring. They built in some nice features nobody needs, like geotagging and audio comments, but left out the features that make Flickr the cool photo sharing site that it is, especially groups and favorites and, to a lesser extent, sets.

All is not lost, though! Zooomr will upgrade to version 2.0 on July 14. As far as I know they haven’t announced any of the new features yet, but given that Thomas Hawk, who certainly knows what’s what, works for Zooomr now, I’m confident that we can expect some community-building features of Zooomr. It’s time Flickr got some serious competition – it can only make things better for everybody concerned!

The End of Faith

Sam Harris‘ book The End of Faith presents a strong argument that for our species to survive we will have to put to rest our irrational convictions (usually called “faith”) about a supposed creator of the universe and his will. Religion divides people, causes hatred and motivates death and destruction which cannot be rationalized without the firm belief that eternal joy awaits the perpetrators.

Without a doubt the most offending religion in our time is Islam and Harris spends a whole chapter arguing, quite successfully I might add, that the reasons for Islamic terrorism are not economical or political but are to be found on the pages of the Koran and the Hadith. As the costs of developing or otherwise acquiring nuclear and biological weapons come down, Harris argues, it is only a question of time until we see them applied by people of blind faith against people who don’t subscribe to their particular set of irrational beliefs.

Harris also points to the consequences of Christian “teachings”, especially in the United States, the effects they have on science and science education, and on legislative issues, such as capital punishment and drug laws.

To save this world, or rather ourselves, Harris concludes that we must leave behind our irrational beliefs and that we must stop respecting other people’s irrational beliefs. After all, if we respect the terrorist’s faith in the Koran and his (not very far flung) interpretation of it, we must conclude that he did the right thing by crashing that airplane into that office building!

All in all, I found this book to be very enlightening and I agree with its main thesis wholeheartedly. I do have two major nit-picks, though, both of which do not affect the book’s central thesis, however.

My first issue are the endnotes. This book has 348 pages, of which 63 pages contain endnotes, written in small type, some of them several pages long. If you don’t want to miss anything you’ll want to look up the endnotes while you’re reading the book, which disrupts the flow and can be rather tiring. Harris should have separated the bibliographical endnotes from the others, making a traditional bibliography out of the former. He could have made footnotes out of the shorter endnotes (ironically, the book contains exactly one footnote) and he should have gotten rid of the longer ones, working them into the main text.

My second nit-pick concerns the last chapter, which is basically a short praise of Buddhism, meditation, introspection and secular “mysticism”. The problem I have with it is not so much that it re-introduces religion or faith (it doesn’t), but that it simply has nothing to contribute to the central thesis of the book. It seems like this is a topic very dear to Harris’ heart, but instead of writing a book on its own about it, he decided to slap a chapter on it onto this one. In my opinion the book would lose nothing if the chapter was removed.

My conclusion: Read it! Don’t bother reading the last chapter, though – you won’t miss anything concerning the book’s message.