Luke's ICFP 2001 Contest Page

The Contest

Joe Armstrong, Robert Virding, and I (Luke Gorrie) submitted a lightning entry for the ICFP 2001 programming contest. Our entry consists of 403 lines of Erlang and 34 lines of sh. It was called Erlightning, team The Blue Avengers. (Previous edit of this page said 385 lines of Erlang - I forgot to count the header file).

We downloaded the task, talked about it for a while, and chose to use a list of{Decorations, Text} tuples for our basic datatype. Then Joe wrote a parser, Robert wrote a whitespace eliminator, and I wrote an outputer. We put these bits together and tested them and it seemed to work pretty well. Now we had a simple functioning program to work from.

The Features

Next we added some features to our "simple and naive" base program:
• Robustification
  We worked with the conservative assumption that the judges are rabid sadists, who'll try all sorts of devious inputs and time limits to break entries. By recognising that it's technically correct to send the input back as the output, we did some sh hacking to establish some invariants demanded by the judgement criteria:
  1. Correctness: we have to produce a correct file. Our script expects our Erlang program to write its output to a file and then, only if successful, to create a "flag" file indicating that it succeeded. If the Erlang program terminates without writing the flag file, the script just "cat"s the input back. So if the Erlang program were to crash, the input will be returned. This is no help if the Erlang program "successfully" generates invalid output, however.
  2. Stupidity: sending back output that's bigger than the input gets you kicked out, so our sh script compares the sizes of the input and the output and sends back the smaller or the two.
  3. Timeliness: Our Erlang program initially starts a timer process to halt/abort the program 10 seconds before our time expires. If we halt before writing the "flag file", the script will just send the input back. Ten seconds is a long time, but we don't think our program will use nearly 3 minutes (the stated minimum for the contest) unless it gets stuck somehow, and if something bad happens we need to have enough time left to cat back the input after operating system swapping and what-not. The input can be up to 5 megabytes, and the judges state we can assume stdout to eat at least 1 MB/s, therefore in the worst case (memory paging aside) you need to reserve 5 seconds to send the output.
• Tag ordering
  When generating output, we use a simple and short lookahead to see which tags will have to be closed first so that we can open them last. We "randomly" order tags that the lookahead doesn't find the end of.
• Colour and font nesting
  When changing font size or colour, we have to decide whether to close the previous one and/or open the new one. In general we don't close anything until we have to, but for these two we look at the stack of open tags to see whether the colour change can be achieved by simply popping. If the top element of the stack is a color, and the next color below it is the color we want to transition to, then we just pop the stack - otherwise we push the new color. Same thing for fonts.

The Optimisations

We didn't think of any clever optimisations beyond what's listed on the task description. Here's how I think we did on those:

whitespace compression	We implement this.
redundancy elimintation	This disappears in parsing, since the parse tree contains the "meaning" of the document, not a tag tree.
overlap inversion	Our tag reordering achieves this, but it's limited by the lookahead.
PL shortcut	We don't do this at all, which is the major limitation of our program. There is never a PL tag in our output.
whitespace simplification	We implement this, same code as whitespace compression.
EM elimination	Like redundancy elimination, we get this in parsing.
color nesting	We do this, though it ties in with tag reordering and so it's limited by the lookahead.

The Program

Our entry is downloadable here. It requires a recent version of Erlang to be installed. The contest machine uses version R7B-3, which is the latest release at the time of writing.

The Testing

During the initial hacking our main input files were big.txt (a bit under 9 megabytes, created by repeatedly appending example.txt to itself); test.txt, containing the optimisation examples from the spec; and example.txt, as downloaded from the site. The idea of the big file was that if we could process it in comfortable time and space, we're probably OK performance-wise for whatever the contest judges throw at us.

When the program was working, we made a random input generator that produces arbitrarily large and deeply nested files, and this squeezed a bug or two out. Thousands of random files of random sizes is also a much more interesting thing to try optimising than just example.txt (which it seems a simple algorithm can perfectly optimise, except for the PL opportunities at the end - or so says my attempt at hand-optimising it on the bus).

Only a dozen or two of these random files were actually fed through the equivalence testing CGI, and their sizes were relatively small because of limitations of that tester.

We also had a small Erlang program that did the appropriate HTTP POST to the validation CGI, but after a couple of misleading results due to bad parsing we stopped using it.

I believe that our program runs in linear time and space and should have no trouble with either on the contest machine (not meaning to jinx anything :-)).

Reflections

We had lots of fun and enjoyed the contest immensely.

It's also a comfort that the sh script will mask any programming errors, since if we failed visibly on a type error we could never show our faces in comp.lang.functional again ;-)

Results

We won the Judges' Prize, and we're tickled pink. This was awarded for our program being the best-performing lightning entry.