Wednesday 24 October 2007

The aftermath

We are wrapping up our efforts on the ICFP Programming Contest 2007. Most contest-related matters have been finished by now.

If you want to read more about the ICFP Programming contest, you should have a look at our report about it.

You can order a t-shirt with the after picture on the back, and one picture from the arrival sequence on the front from cafepress, or create your own t-shirt using these materials (4.3MB).

If you want to see the presentation we gave about the contest at ICFP 2007, have a look at our video (with an explanation about how to solve the contest problem starting at 18:00, and Endo appearing at around 1:12:00).

The question we got after the contest was:
How much time did you spend creating it?
We have different answers to this question, but probably the one that comes closest to the truth is: as much as we enjoyed creating it.

Wednesday 10 October 2007

Endo lives!

At the International Conference on Functional Programming (ICFP) in Freiburg last week, we announced the results of the ICFP Programming Contest 2007.

Just as last year, the first prize was won by Team Smartass from Google research.



The second prize was one by the United Coding Team from the University of Cape Town, South Africa.



The judges' prize was won by Celestial Dire Badger (Jed Davis).



The highest survival chance produced during the contest (by Team Smartass) was over 90%, so Endo survived! Endo actually came with us to Freiburg to say `thank you' to the people present.



Later in the week he was spotted by several ICFP attendants in the city of Freiburg, running around and enjoying himself.

Friday 17 August 2007

Tickling grass

As you all already know, Endo's chance of survival is also affected by other organisms and objects in his environment. One of the organisms that has recently attracted our attention is grass. It turns out that with just a few modifications to Endo's DNA you can make grass grow in completely different places! We have not discovered, however, how to make it grow at the right locations. Take a look at what we tried:
IIPIFFCPICCFPICICFPPICICIPICIIICCCIICIIICCCIIICCCP
IICIPIIICCPIIPIICIIPIPIIICCPIICIIPIICIPIIICCPIICIP
PPCCCFFCCCCCCCCCCCCCCCCCCICIPPCPFCCCFFCCFCCCCCCCCC
CCFFFICIPPCCPCFCFCFFCCCCCFCFFCCCCCCCICIICIIPIFFCPI
CCFPICICFPPICICIPICCIIICICIIICIICCIIICCCPIICIPIIIC
CPIIPIICIIPIPIIICCPIICIIPIICIIPIPIIICCPIICIIPIICIP
IIICCPIICIPPPCCCCFFCCCCCCCCCCCCCCCCCICIPPCPCCFFFCC
FCFFFCCFFFFFFCFFICIPPCCPCFFCFFCCCCFCCCCCFCCCFFFICI
PPCICPCFFFCFFFFFCCCCCCFCCCCCCICIIC
This prefix enables grass repositioning and redefines the function bioMul (see initial conditions help page) as follows:
bioMul x y = bioAdd x y
It seems that the bioMul function influences where grass is going to grow. We are still searching for the right definition of bioMul, and we are confident that when we find it, grass will grow at the right locations. Do you want to help us figure out how to fix bioMul? If you do, you might find it helpful to understand first how bioAdd is encoded in DNA.

Friday 10 August 2007

Finding palindromes

--------------------------------------------------------------------------------
This blog post receives thousands of hits per month. I do not want to change the blog post from 2007, since it is part of a larger context.

Visit Finding palindromes for a more extensive description of the algorithm and the underlying concepts and ideas.

Visit http://www.jeuring.net/homepage/palindromes/ to obtain the software for finding palindromes.
--------------------------------------------------------------------------------
A palindrome is a number, verse, word or a phrase that is the same whether you read it backwards or forwards, for example the word `refer'.

When I started as a PhD student in Computer Science in 1988, my professor gave the following problem assignment to me. Construct an algorithm that, when given a string, finds the longest palindrome substring occurring in the string. For example, given the string "yabadabadoo", the algorithm should return the substring "abadaba". The algorithm should not only return the longest palindrome substring, it should also return it fast. The requirement was that the algorithm should only use a number of steps linear in the length of the argument string. This was a difficult problem, which gave me severe headaches in the months to follow. I spent four months on the problem, and solved it. The one comment I got from my professor was "The best thing about this problem and its solution is that they have absolutely no practical relevance."

He was wrong.

Since 1988 I have found that palindromes play an important role in the world around us. Palindromes appear in music, in genomes, in art, architecture and design, mathematics, physics, chemistry, etc.

Particularly interesting is the fact that palindromes occur in the male genome: of the about 20,000,000 characters representing the male-specific region of the Y chromosome, 5,700,000 characters form together eight large palindromes (off by a couple of characters). I don't think there is any proven explanation for the presence of palindromes in the male genome, but I suspect it has something to do with repairing genomes. If you know more about it: please let me know.

As you may or may not have noticed when working on repairing Endo's DNA, the cloud is corrupted. It turns out that the cloud's genome also is a palindrome (off by a couple of characters), and that the corruption can be repaired by taking the mirror image of the palindrome. To do so, you have to find the palindrome. In the case of Endo, this is pretty easy: `duolc' follows cloud immediately in the symbol table. Had this information not been in the symbol table, you would have to find this palindrome in the DNA by means of an algorithm for finding palindromes. Actually, the DNA for the cloud is only 6,500 acids long, and using a naive quadratic-time algorithm for finding palindromes is not a real problem if you have a sufficiently fast machine. A quadratic-time algorithm for determining palindromes in human male DNA isn't going to work: it would take a long time to find the palindromes.

This blog message explains how to find palindrome substrings in linear time. I will develop a program in Haskell for finding exact palindromes. The problem of finding approximate palindromes is left as an exercise to the reader :-) Interestingly, the algorithms for finding palindromes developed by computational biologists generally use suffix trees, and both space and time consumption seem to be worse compared with the algorithm I give in this blog message. But descriptions of the algorithm given here have been published in the eighties (by Galil and others, described in RAM-code) and nineties (by me, described in Squiggol, which is probably even harder to decypher than RAM-code) of the previous century, which is a long time ago of course.

This blog message is a literate Haskell file, which can be interpreted with ghci.


The type of a function for finding palindromes


I want to find the longest palindrome substring in a string. The first attempt at a type for a function longestPalindrome is hence:

longestPalindrome :: String -> String

To determine whether or not a string is a palindrome, I have to compare characters at different positions in a list. It would be helpful if I had random access into the string. For that purpose, I'm going to change the input type of the longestPalindrome function to an array. Furthermore, the longestPalindrome algorithm can also be used to find the longest palindrome in a list of integers, or any other type on which I can define an equality function. So here is the second attempt at a type for a function for finding the longest palindrome:

longestPalindrome :: Eq a => Array Int a -> Array Int a

To find the longest Palindrome in an array, I have to calculate the longest palindrome around each position of the array, where a position in an array is either on an element, or before or after an element. For example, the array corresponding to [1,2,3] has 7 positions: before the 1, on the 1, before the 2, ..., until after the 3. So I want to express the function longestPalindrome in terms of a function longestPalindromes of type

longestPalindromes :: Eq a => Array Int a -> [Int]

where the result list is the list of the lengths of the longest palindrome around each position in the argument array. For example,

?longestPalindromes (arrayList (0,2) [1,2,2])
[0,1,0,1,2,1,0]

I will omit the definition of longestPalindrome in terms of longestpalindromes, and define function longestPalindromes below.


A naive algorithm for finding palindromes


A naive algorithm for finding palindromes calculates all positions of an input array, and for each of those positions, calculates the length of the longest palindrome around that position.


> module Palindromes where
>
> import Data.Array
>
> longestPalindromesQ :: Eq a => Array Int a -> [Int]
> longestPalindromesQ a =
> let (afirst,alast) = bounds a
> positions = [0 .. 2*(alast-afirst+1)]
> in map (lengthPalindromeAround a) positions


Function lengthPalindromeAround takes an array and a position, and calculates the length of the longest palindrome around that position.


> lengthPalindromeAround :: Eq a => Array Int a
> -> Int
> -> Int
> lengthPalindromeAround a position
> | even position =
> extendPalindromeAround (afirst+pos-1)
> (afirst+pos)
> | odd position =
> extendPalindromeAround (afirst+pos-1)
> (afirst+pos+1)
> where pos = div position 2
> (afirst,alast) = bounds a
> extendPalindromeAround start end =
> if start < 0
> || end > alast-afirst
> || a!start /= a!end
> then end-start-1
> else extendPalindromeAround (start-1)
> (end+1)


For each position, this function may take an amount of steps linear in the length of the array, so this is a quadratic-time algorithm.


A linear-time algorithm for finding palindromes


I now describe a linear-time algorithm for finding palindromes. Although the program is only about 15 lines long, it is rather intricate. I guess that you need to experiment a bit with to find out how and why it works.

The algorithm processes the input array from left to right. It maintains the length of the current longest tail palindrome, and a list of lengths of longest palindromes around positions before the center of the current longest tail palindrome, in reverse order. Function longestPalindromes is expressed in terms of function extendTail.


> longestPalindromes :: Eq a => Array Int a -> [Int]
> longestPalindromes a =
> let (afirst,alast) = bounds a
> in extendTail a afirst 0 []


Function extendTail takes an array as argument, the current position in the array, the length of the current longest tail, and a list of lengths of longest palindromes around positions before the center of the current longest tail palindrome, in reverse order. There are four cases to be considered in function extendTail. If the current position is after the end of the array, we only have to add the final palindromes in the array to the list of longest palindromes, for which we use the function finalCentres. If the current longest tail palindrome extends to the start of the array, we extend the list of lengths of longest palindromes by means of function extendCentres. If the element at the current position in the array equals the element before the longest tail palindrome we extend the longest tail palindrome. If these elements are not equal, we extend the list of length of longest palindromes.


> extendTail a n currentTail centres
> | n > alast =
> -- reached the end of the array
> finalCentres currentTail centres
> (currentTail:centres)
> | n-currentTail == afirst =
> -- the current longest tail palindrome
> -- extends to the start of the array
> extendCentres a n (currentTail:centres)
> centres currentTail
> | a!n == a!(n-currentTail-1) =
> -- the current longest tail palindrome
> -- can be extended
> extendTail a (n+1) (currentTail+2) centres
> | otherwise =
> -- the current longest tail palindrome
> -- cannot be extended
> extendCentres a n (currentTail:centres)
> centres currentTail
> where (afirst,alast) = bounds a


Function extendCentres adds palindromes to the list of lengths of longest palindromes. It takes the array as argument, the current position in the array, the list of palindromes to be extended, and the list of palindromes around centres before the centre of the current longest palindrome tail. It uses the mirror property of palindromes to calculate longest palindromes around centres after the centre of the current longest palindrome tail. If the last centre is on the last element, we call extendTail with a longest tail palindrome of length 1, and the position moved tot he right. If the previous element in the centre list reaches exactly to the end of the last tail palindrome, use the mirror property of palindromes to find the longest tail palindrome. In the other cases, we've found the longest palindrome around a centre, and add that to the list of length of longest palindromes. We proceed by moving the centres one position, and calling extendCentres again.


> extendCentres a n centres tcentres centreDistance
> | centreDistance == 0 =
> -- the last centre is on the last element:
> -- try to extend the tail of length 1
> extendTail a (n+1) 1 centres
> | centreDistance-1 == head tcentres =
> -- the previous element in the centre list
> -- reaches exactly to the end of the last
> -- tail palindrome use the mirror property
> -- of palindromes to find the longest tail
> -- palindrome
> extendTail a n (head tcentres) centres
> | otherwise =
> -- move the centres one step
> -- add the length of the longest palindrome
> -- to the centres
> extendCentres a n (min (head tcentres)
> (centreDistance-1):centres)
> (tail tcentres) (centreDistance-1)


Function finalCentres calculates the lengths of the longest palindromes around the centres that come after the centre of the longest tail palindrome of the array. These palindromes are obtained by using the mirror property of palindromes.


> finalCentres 0 tcentres centres = centres
> finalCentres (n+1) tcentres centres =
> finalCentres n
> (tail tcentres)
> (min (head tcentres) n:centres)


At each step in this algorithm, either the longest tail palindrome is extended, and the current position in the array is moved, or the list of lengths of longest palindromes is extended. Since both the array, and the list of lengths of longest palindromes are linear in the length of the array, this is a linear-time algorithm.

Saturday 4 August 2007

The Major Imp Episodes

Although the Fuun typically want little to do with them, they do suffer from an inferiority complex when it comes to Imps. This is most evident in the large amount of extremely popular spy stories in which the Fuun novice invariably wins against a hard-boiled, sinister Imp character, who either dies (after a heroic attempt by the hero to save his life) or is converted to Fuun philosophy and thereafter serves the functional cause. A few short excerpts of such a story were recovered from Endo's DNA. It is still unclear whether these stories could actually play a role in saving Endo. For your amusement, we have included the very first episode below:

Only just before sleep-groggy roosters reared their scrawny heads, there was a hesitant knock on the steel door of the austere office of semi-colonel Void. "ENTER", rang out from the room, as though spoken in a medium-sized cathedral. Novice Imp entered the cramped room with some trepidation, knowing full well that many a (not so intelligent) agent had become deallocated after nary a slip of the tongue. Lieutenant Ptr, for example, had referred in His presence to "some unwanted side-effects" of a particular investigation. Ptr had promised that it wouldn't happen again, and Void had made sure that indeed it wouldn't.

Somewhat weak at the knees, Imp made for the middle of the room, where he stood at attention. "RELAX", spoke Void, in his usual teletype voice that belied the contents. "I have heard that among our recruits, you are the one adhering closest our revered commandos. We have a sensitive and dangerous mission scheduled and you have been chosen to volunteer..." (call-cc)

Monday 30 July 2007

How did it go?

The ICFP Contest 2007 ended last Monday. We have seen writeups of several teams that participated in the ICFP Contest. Many of those are interesting and sometimes funny reading. We particularly enjoyed

http://stereotype441.livejournal.com/45150.html

Marco Galotta collected a list of writeups, and posted them on his blog

http://marco-za.blogspot.com/2007/07/icfp-how-we-reached-top-15.html

We don't want to give our writeup now, we'll do that for ICFP in Freiburg, but we do want to briefly share our experiences.

We had a very hectic and pleasant time. I cannot remember I've had such an intense time at work before.

Headquarters was never empty during the 72 hours of the contest. We had a laptop showing several screens via a beamer: last 20 submissions, standings, the icfp mail account, several irc channels devoted to the contest, etc. Not much happened in the middle of the contest, but both the start and end were very hectic. The end was a thriller, I can assure you. But more about that at the ICFP conference in Freiburg.

Everything went fine. We haven't discovered an error in the task description yet. Initially we were worried about the slow start by many teams, but as time passed we were increasingly impressed by the creativity and cleverness of many teams. We have excellent winners. Our machines were unreachable twice for a short period, but that hasn't been a problem. Web statistics show that we processed millions of hits in these three days. All in all we are quite satisfied by how things went.

From now on we will prepare our presentation at Freiburg. By then we will know whether or not Endo survived. In the presentation we will discuss the problem, possible solutions, techniques we used to create the problem, solutions we have seen from the participants, the winners, etc. We will hand out a writeup about the contest in Freiburg.

Monday 23 July 2007

Thank you

Thank you all so much for participating.

It has been heart-warming to see all participants trying so hard to save the poor Endo. It was a hard struggle, but we are very optimistic Endo will survive. We have sent the best submitted prefix to Arrow, but haven't heard anything since. We hope that this is due to the fact that Arrow is using all its remaining energy to apply the DNA prefix to Endo, and not because something has gone wrong. For now, we can do nothing but wait for a sign of life. Repairing DNA takes time, but we expect that we will know whether or not it has been successful by the time of the ICFP Conference in Freiburg.

Friday 20 July 2007

Emorphency!

Ok, here's the story, as unbelievable as it sounds. It looks like the message was a call for help, sent by the ship that also appears in the sequence of pictures. The ship seems to be called Arrow and to be a sentient being, or at least intelligent. Apparently the story as told by the picture sequence has actually happened, with the final picture (decrypted by us today as expected) happening three months ago, about when the message was sent to us.



It is the story of Endo, a specimen of the extraterrestial Fuun. Endo was garbage-collected while sleeping in his(?) ship Arrow and unfortunately drifting into a heap of junk. Garbage collectors are apparently common in space and run by a species called the Imps. They like to drop junk on underdeveloped worlds (sorry, this is what Arrow told us). So the ship, together with lots of other stuff, was dropped on Earth. Arrow was damaged in the process, and before it could warn Endo that the atmospheric conditions of Earth are not very suitable for a Fuun, Endo left the ship – only to be hit by a cargo container! Endo is now in serious trouble. According to Arrow, the only chance to save Endo is to adapt him to the conditions that are prevalent on Earth by changing its DNA.

The hitch is that Arrow, being damaged itself, is running low on energy and cannot come up with a good modification itself. It can still perform the actual transformation process, but only if it gains knowledge of a suitable transformation soon. Arrow tells us it only has slightly more than 72 hours left before it will shut down!

During the last days, we have been able to decipher large parts of the original message, found out that it is about DNA and describes how Fuun DNA works. We therefore have some understanding now about the process involved. Unfortunately – and we feel really guilty about it – we have given all of this a low priority due to the upcoming contest, and the one thing we didn't find out until after we actually made contact with Arrow, was that this really is a cry for help, and how urgent it is! If only we had found out earlier, we would have had much more time to save Endo!

Because of that, and also because it is really the only thing we can think of to still give Endo a chance, we will change our plans. We will abandon the original topic we had in mind for the ICFP contest (writing generic programs in order to design boilerplates). Instead, we make it the task of the contest to Morph Endo!

(Of course, we still are not 100% sure if the message is actually authentic, but from what we've seen, there seems to be a lot of structure in the DNA we discovered, and a lot of information provided by Arrow, and we doubt someone would put so much effort into a joke.)

Wednesday 18 July 2007

Contact

We seem to have made contact with the author of the message. At least that's what we believe. Communication is still, well, difficult at best.

With the contest starting in a few days and the preparations more or less in place, we can now put a bit more effort into solving this mystery, and I am very curious where it will lead to.

Monday 16 July 2007

The message

You might remember the 'SPAM' message we received more than 3 months ago (see my message on April 26). For a long time, the only thing we managed to do with it is decrypt pictures, which already takes us a lot of time. We run the decryption process on one machine, and get about one picture per week. It seems there's only one picture left to decrypt, and that should be ready by Friday. The pictures appear to tell a story, but we cannot make much sense of it.

However, it was clear from the beginning that the pictures are only a small part of the message, and the rest remained a big mystery to us ... until last week, when Alexey suddenly had a brilliant idea that turned out to be a major breakthrough. Since then, we have not only deciphered a large part of the message, but we also have an idea about who sent it. It is all very strange, and we still do not know whether it all is a joke (maybe from an ex-student?) or whether it could be real. I'll keep you informed about our progress.

Friday 13 July 2007

Wednesday 4 July 2007

The team

Let me introduce the team. I cannot disclose their contributions in detail, for obvious reasons.

Atze Dijkstra and Doaitse Swierstra. Contributed to the brainstorming sessions in 2005 and 2006.

Eelco Dolstra. I think if someone in the team qualifies for the label hacker, it will be Eelco. Eelco has participated in several contests. He has developed, amongst others, the central component for this years' contest. He is not a religious Haskell hacker (as many of us others are), and that has definitely been a Good Thing.

Chris Eidhof, Maaike Gerritsen, Jeroen Leeuwestein, Eelco Lempsink, Martijn van Steenbergen, Mark Stobbe. Student testers. Contributed to many aspects of the problem after they finished their test run.

Jurriaan Hage. Jurriaan has a broad background, and has contributed to several components of the task. Unfortunately, none of these can be disclosed.

Bastiaan Heeren. Enthusiastic member from the start. Has become the central organiser in the team, and is continuously adding and testing new ideas, implementing tools, pushing students to implement ideas, answering questions, etc. He knows most of what is going on, what still needs to be done, who is doing what, etc.

Stefan Holdermans and Arie Middelkoop. Young, starting, PhD students, who also have to write their first papers, so they cannot spend as much time as some of us others on the contest. I cannot disclose Arie's contributions; Stefan mainly worked on the task description. His perfectionism is exactly what we need for the task!

Johan Jeuring. Johan is the chairman of the organisation committee. He takes care of the `external relations'. Furthermore, he contributed to the problem and the task description. But he spends most of his time on organisational matters.

Andres Löh. One of our two external members. But he did his PhD here, and will become a lecturer very soon, so he cannot really be called external. Has participated in several contests (even won one!). Contributed many things: story, basic constructs, task description, theory development, etc.

Clara Löh. Our other external member. Did most of the artwork.

Alexey Rodriguez. Together with Eelco, I think Alexey is the other candidate for the hacker label. Has been away a couple of months to optimize GHC in GHC-headquarters, but has picked up very quickly again after he returned. His main contributions have to remain a secret for now. They're slightly obscure, but I hope you'll enjoy them anyway.

John van Schie. One of our students, and another hacker, who has implemented the communication components.

Thursday 28 June 2007

Monday 25 June 2007

The process

Ralf Hinze, the general chair of ICFP 2007 asked us already at the end of 2005 if we would like to organise the ICFP Programming Contest 2007. I tried to collect a group of people from the Software Technology group of the Computing Sciences department of Utrecht University that were willing to help. That turned out to be rather easy: the majority of the people I asked were enthusiastic about it. In the first months we had frequent meetings, to discuss the several aspects of organising such a contest. Furthermore, we extended the team with several young colleagues. In particular with people that had participated in a couple of previous contests, which was really helpful.

After two months we stopped meeting to wait for the 2006 contest. We participated in the 2006 contest with four members of the team. As I mentioned in the blog message about the 2006 contest, I think this was a great experience.

We resumed brainstorming at the end of summer 2006. We ended up with three or four problem ideas. Each idea was investigated by a small group of people, and in October we selected one of the ideas, based on the practical requirements for a task we have formulated in a previous blog message.

In the following months we implemented several components for the task, and we tried to solve the several problems we envisaged with our problem idea. In January 2007 we were pretty convinced that our problem idea had no fatal flaws, and we started working out the many details that we had left open.

Since then we have been working on the implementation of the several components, testing, and quality control.

Monday 18 June 2007

What's in it for us?

Why would you ever organize an ICFP Programming Contest? I can assure you it is a lot of work. So why did we agree to do it?

  • We are happy to do a service to the community. We benefit from having a community in which we perform our research. The community organises conferences and workshops at which we learn about new ideas, can present our own ideas, and meet colleagues. Furthermore, people from the community review our papers and research proposals. In return, we sometimes have to invest time in projects that support the activities and visibility of the community.
  • Visibility for the community is good for us as well. There is very little programming language research in The Netherlands, and we have the impression that programming language research is sometimes not as respected as we would like it to be. Organising a contest that shows that programming languages and tools matter, might help a bit. Especially if previous organisers come from places like Harvard, CMU, and MIT .
  • We try to draw some attention to the contest in the Netherlands. It is nice to be able to have a story to present to the media. It is quite a challenge to present our work on a level that is understandable for non computer scientists.
  • Organizing the ICFP Programming Contest gives us visibility in the community.
  • We will write and publish a paper about the contest. However, the amount of work for producing this paper is considerably higher than for a normal paper.
  • We are a team of around 10 people (depending on whom you count), most of them from the Software technology group of the Information and Computing Sciences department of Utrecht University, working on a common goal, with a strict deadline. I think such a common goal creates a good atmosphere in the group.
  • We have already learned a lot, and had quite some fun.
  • Eternal fame. The ICFP Programming Contest has a good name. We hope that the contestants will like this years' contest, and remember it.

Thursday 14 June 2007

Monday 11 June 2007

The ICFP Programming Contest 2006

I started collecting a team of people to organize the ICFP Programming Contest already by the end of 2005. Besides collecting and discussing requirements and advice, we didn't start working on a particular task immediately, also because the 2006 contest could well make it necessary to change our ideas. Of course, we took the chance to participate in the ICFP Programming Contest 2006. Only four of our team could make it, but that happened to be exactly the team size that could still qualify for a prize...

I can recommend participating in such a contest to everyone :-). It was really Big Fun. Family life suffered, but participating was both intellectually challenging and good for the team-spirit. Moreover, it was an excellent opportunity to find out how much you can actually do in three days time. Which is a lot!

What was really nice about the 2006 contest:
  • entering a virtual world which you could explore
  • solving puzzles
  • scoring incrementally; small points for small solutions, big points for major achievements
  • writing programs in languages which tied your hands on your back (I wrote programs in qbasic and a stupid rewriting engine; and helped thinking a bit about the `rotating' machine.)
  • very, very, cleverly done!
What was maybe a bit less nice:
  • had to program the machine in C because of speed requirements
  • could not use Haskell, our programming language of choice, other than for testing
  • small programs
  • only teamwork at the start, from then on mostly individual work (but that was our own, not very conscious, decision).
All in all a very nice experience, from which we learned a lot.

Wednesday 6 June 2007

Whither, fairest, art thou running?

This garbage collector seems to be going somewhere...

Friday 1 June 2007

Previous organizers

Once we had agreed to organize the ICFP Programming Contest 2007 (did we really?), I called the previous organizers to ask for advice. I did not talk to all 9 of them, but only the last three: John Hughes (Chalmers, race tracks, 2003), Benjamin Pierce (UPenn, ants, 2004), and Robby Findler (Chicago, cops & robbers, 2005). At this time the 2006 contest hadn't happened yet. Most of the advice corresponded with our own requirements for the task, but they had some useful observations for us.

About the programming task:
  • The task should be easy to understand.
  • Make sure the task is correct, for example by turning it into a literal programming file, or by deriving it from an actual program.
  • Spend a lot of time modifying the problem, tweaking it, trying it out, etc. Have a few groups of students test it.
  • Don't finish the task a couple of minutes before the contest starts!

Meta observations about the task:
  • It would be nice if the winners to in some way belong to the community, be interested in the community, and definitely show up at ICFP (which is probably a consequence of the first two desirables). This implies that you want to design a task that is not too alien to people in or close to the community, and that it helps to know about programming languages.
  • One of the nice things about the ICFP Programming Contests is that lessons can be drawn from most contests afterwards. For example, the 2005 contest, with the twist, was easier to solve in Haskell than in most other languages. It is maybe hard to prove these statements, but it is nice to be able to say something like this to your students. It might be nice to think of the `lesson' that can be drawn from the contest in advance.

About the process:
  • It is important to have hackers on the team.
  • Try to prevent premature rankings. Maybe set up a mailing list in which contestants can discuss the problem. Otherwise they will do it anyway. Monitor the list, and remove postings that reveal too much.
  • Reserve a long slot at ICFP, and spend a lot of time on the problem, several statistics, interesting details about submissions, etc

We've taken most (but not all) of this advice to heart. The mailing lists, and long slots at ICFP have happened for a couple of years now.

Tuesday 29 May 2007

Interstellar public transport?

That hook was the arm of an interstellar garbage collector! The story is getting weirder with every picture I manage to extract.

Wednesday 23 May 2007

Decrypted!

Andres Löh, another member of the ICFP Programming Contest team, visited us today. Together with Bastiaan he managed to decrypt the two pictures. Here they are.






Strange content for a spam message.

Monday 21 May 2007

Practical requirements for the ICFP Programming contest

In a previous message I discussed the most important goals of the ICFP Programming Contest: the contest should offer the possibility to show off your favorite programming language and/or programming tools, and the contest should be fun.

The programming task should at least test language + programming skills + intelligence. We considered using the programming task for addressing a real problem.

Recent contests had thousands of contestants, working from anywhere in the world, with very different backgrounds. The contestants may use any tools they like, and any information at their disposal. Furthermore, teams may be of arbitrary size. These `contestant-friendly' rules have some important practical consequences for the organizers (that is: us!).
  1. the programming task should not be easily solvable
  2. the programming task should not be solvable by using a lot of computing power
  3. a solution to the programming task should not be lying around (or for sale) somewhere
  4. we have to think about how to deal with the fact that contestants are going to use many programming languages and compilers
  5. the solution space of the programming task should be large: we don't want many teams to submit the same, correct or best, solution
  6. there should be a clear way to determine the winner of the contest: the solution space of the programming task should have a total ordering without a top (or bottom)

Wednesday 16 May 2007

Objects in Space?

Bastiaan sent me another picture. It is somewhat clearer than the last one, but there's obviously still something wrong with the pictures. It doesn't make much sense. Bastiaan also tells me that he has an idea now what might be the problem, namely a bug in the decryption program, and that he's working on corrected versions as well as on extracting more pictures.

Monday 14 May 2007

The first test run

The group of students, mentioned in the Power Outage and Goals messages, just finished their test run of our first version of the ICFP Programming Contest 2007. The good news is that they exhibited the same kind of addiction we felt when working on last years' contest: each of them was supposed to spend 40 hours on the contest (72 hours minus sleeping, eating, and some travelling), about the number of hours we spend when working on the 2006 contest, but some of them spent more than double the amount of time. And they had quite a lot of fun working on the contest. It doesn't happen often to me that, despite me telling a student not to work on a task anymore, he tells me he is going to work on it, in a way which clearly shows that I cannot stop him even if I wanted to. They actually got quite far, but they also missed some aspects. They're clearly very good students, but I expect that they are not of the level of the top teams working on ICFP contests. So we might make the task a bit more challenging at some points. They had some interesting observations about our task description, and the way with which we ranked solutions. All in all this test round has proved very useful:
  • we were forced to finish a first version of the task long before the actual contest. We spent a very hectic weekend before the deadline. Besides being a very productive weekend, it was also very enjoyable.
  • the students got a very good idea of what the contest is about, and how contestants will go about trying to solve it. Probably better than us.
  • we got to see how contestants go about the task, what kind of (sometimes undesirable) problems they encounter, etc.
From now on the students will help in producing the next test version of the task, scheduled for the beginning of July.

Thursday 10 May 2007

Blog syndication

I've been asked to have my blog added to http://planet.haskell.org/. I think getting more exposure for the contest is a Good Thing, but I certainly don't want to give the impression that the ICFP Programming Contest is a Haskell contest. It definitely isn't. If other blog aggregators or syndicators want to add this blog as well, please contact me.

Monday 7 May 2007

Sleeping beauty?

Remember the strange mail message I talked about? We (that is, me and some persons in the offices around me) are trying to figure out what it is in our free time. Actually, I had already given up last week after spending several hours without getting anywhere, but today, I can report our first success. Guess what? More or less by accident, Bastiaan Heeren (also a member of the contest organization committee) found a picture hidden in the flood of seemingly random data. He says it was encrypted, and that he somehow managed to decrypt it. I do not know the details, but I am not sure he did it right, as it looks really strange. But see for yourself!

Tuesday 1 May 2007

Advertising the ICFP Programming Contest

I think the ICFP Programming Contest is an established contest by now. The publicity chair of ICFP thinks that it will sell itself, and he is probably right. However, to be on the safe side, we started advertising the ICFP Programming Contest last week. And lo and behold, our server experienced a hit explosion! In the last week, http://www.icfpcontest.org/ got five times as many hits as usual. Even this blog about the contest gets a considerable amount of hits; more than my homepage, for example. (But I admit: my homepage is probably much more boring than this blog (is going to be).)

I'd like to ask you, reader, for help though. I've published the advertisement on a lot of places, and I guess you have read it somewhere. But do you know of a good place to advertise the contest, which I missed? You are welcome to forward the advertisement yourself, but you can also let me know, and I will do it. Actually, I've seen the advertisement, or variants of it, appear on a couple of places where I did not publish it. One of those, http://programming.reddit.com/, has generated more than 700 hits! So please contact me if you know a good place to advertise the contest.

Here is the list of places where I (or someone I know) advertised the contest: haskell, haskell-cafe, caml-list, plt-scheme, ruby-talk, fp-nl, prog-lang, types-announce, clean-list, erlang-questions, comp.lang.c, c++, dylan, functional, haskell, lisp, ml, prolog, python, ruby, scheme.

Thursday 26 April 2007

Goals of the ICFP Programming Contest

One of the first things we discussed in the organization team of the ICFP Programming Contest 2007 was what we want to achieve with the contest. We never drew up an ordered list, but the general concensus was that being able to

Show off your favourite programming (language) tools and programming capabilities

is one of the most important goals of the contest. A second important aspect is that

The contest should be fun.

These goals largely coincided with the goals of the previous contests. And of course, they are reflected in the prizes.

Btw, something interesting happened today. I was visiting the systems people to arrange computers and screens for some of the new organization team members. The systems guy was telling me that apparently the power outage from a couple of days ago had been caused by a SPAM mail message of a couple of megabytes that was triggering a bug in our server. The message itself seemed to be strange: several hundreds of attachments, all of them in strange encodings not known to our software.

Out of curiosity, I asked to get the message, and I will have a closer look at it later (although the contest doesn't leave me a lot of spare time). Since I suppose this blog will be read by clever language people, I might come back to it here.

Monday 23 April 2007

Power outage

We had a power outage in the ICS department over the weekend. Luckily, nothing important seems to have been damaged. It is a bit disconcerting to see such a thing happening in the midst of the organisation efforts for the ICFP Programming Contest... Especially since we want to start with the first test runs. We deferred the start of our test run by two days. There is still almost three months to go before the contest starts, of course. (Actually: today is exactly 3 months before the contest ends.)

Our systems people are still busy to find out what exactly happened. Only our department seems to have been affected - other floors of our building haven't had any problems.

Saturday 21 April 2007

ICFP Programming Contest 2007

We're working hard on organizing the ICFP Programming Contest 2007 here at Utrecht University (and abroad). For information about the programming contest, see http://www.icfpcontest.org/. I intend to blog about our efforts in organizing this contest in this spot. From an organizer's perspective, I think this is the world's most complicated programming contest. Contestants can use any tools, programming languages, libraries, and internet resources they like, for 72 hours. To quote our systems manager, this is a real `free software fight'.