On ICFP Contest

So, it’s time to summarize a bit on how our team stood during the latest ICFP Contest.

It went well, we are satisfied with the result. It is my personal record score rank for ICFP Contests.

 The Team

We were ten persons. Three of them were CS students, the rest CS PhD students. Of them, two, including myself, were mathematicians, the rest were CS majors. We had two remote participants, of which one was not able to attend.

 The Task

We got some quite weird specification for some model „cars“ and „fuel“ in an unknown ternary encoding. It was possible to submit both cars and fuel. Other’s cars were available, so one could submit fuel for them. Fuel is to be specified as interconnections of ternary logic circuit, called „factory“. We had to find some unknown 17-digit prefix to be able to actually submit fuel–in form of factories. The amount of cars a team was able to submit was limited to 72. The scoring was done, basing on length of the factory and time of submission. Some points of the score were assigned each time tick, which was something like 10-15 minutes.

The original task description is here.

Preparation

I sent an email to my coworkers and students about the contest some time ago. We arranged a meeting one week before, discussing availability, programming languages each knew and tools to be used. We have setup a mailing list, svn repository (with wish to switch to git next time) and an IRC channel during the week. Also, a bugtracker and a wiki were available.

Our preferences were Haskell or some imperative language like Java or C++, depending on a task to solve. As a glue between them and an auxiliary language we ended using Python. We wrote almost everything in Haskell, there was a later bruteforcer implementation in C, the scripts used bash and Python.

The First Day

 The contest began at 2 pm local time. We gathered in the conference room, where we would stay then for three days. After reading the task description, we spent a lot of time, trying to obtain the prefix for submitting fuel („the key“) and to understand the gates of which the factory consists. The score was 0.

As we have deduced, there is only one type of a gate. (I omit here the description of a special I/O gate, as it is technical and not funny.) A normal gate has two inputs and two outputs, as the task description says. But the server supplies some unknown input to it, producing known output. But no hope for calculating the gate function. So, first we tried to produce an „identity circuit“. There were in fact two different things to understand under identity here. The one is a trivial circuit, having no actual gates, thus piping its input to its output. However, this circuit is not composable with other circuits: it does not retain its property of being identity in this case, as it uses the I/O gate. The trivial circuit helped us to obtain the server input. So, we connected a single gate after that circuit (in a few different manners), played around, and obtained the gate function. Seemingly a success. The score was 0.

The gates have some nasty feature: the gates could be connected not only normally, called „forward wire“ in the task, but also with a delay, called „backward wire“. The case, when a connection is a backward one, occurs when a gate is connected to a gate with a lower position. Also, when it loops back on the same gate! Oh, and gates of course operate with ternary logic.

We wrote some bruteforce code for gates. In Haskell. With no success. Still at score zero. We optimized the bruteforcing code. With some funny monads (no idea, not my code). With no success. We tries to analyse the gates (my doing, no success). Still score zero. We made some thought on the shape of a car and a fuel. Very useful for further days, but no success. We just wanted that stupid score to show something larger than zero!

The problem was: gates are not composable. Meaning: if we connect two gates, the second one distorts the output from the first. We have found no merger and splitter circuits. Why was that important? We need to produce the 17-digit key before ous actual fuel submission. We cannot submit cars until a successful fuel submission for a dummy car. We can easily produce the first digit of the key from the server input, but need to assure that while producing the second digit of the same key we do not destroy the previous one. But this property is not given for gates!

The Second Day

We spent it writing mostly useless bruteforcers (first dumb and then more smart ones) and running them on all CPUs we could find.

The Third Day

Prepend 0 Circuit

In the night one of us had found a „prepend 0“ circuit. It consists of 6 gates, which take their input and send it to the output. But before the input the digit „0“ is output. It consisted of „zero producer“ and the „identity gate“, identity in the actual sense. Each was 3 gates long. Soon we had „prepend 00“, then, after some work we also obtained the actually required „prepend 1“ and „prepend 2“. Having them, we could write a Haskell program, capable of encoding of each ternary string with circuits.

Prepend 00 CircuitThe „prepend 00“ circuit has a funny story. We built it just with concatenating two „prepend 0“ circuits. The actual creator of the prepend circuit was working at home that day. So we never got until after the end of contest, that „prepend 00“ can be made with 3+3+3 gates, not with 6+6. This could have boosted our score quite much. But at that moment we had it equal to zero.

So, we could submit fuel to cars. We have constructed the factory representation of the key and submitted it to the special checking car, provided by the organizers. We got 0.03 points! We were not at zero anymore! Now we could increase out score, by submitting more fuel. We had some thoughts on the generic shape of the fuel, but no encoding of it! So, we roughly knew what to submit, but had to idea how to write it. We needed to represent some lists of matrices as a ternary string in an unkown manner.

We reasoned, that the shortest car string (which we also could not read) was the most primitive car from the scheme we devised. Submitting fuel for one such car was a success. So, we wrote a bunch of (buggy) shell scripts for submitting the fuel for all available car. At ran it repeatedly, as new cars came in permanently. We had a few variants of the fuel above, and ran autosubmitter for all of them. As far as I recall, this action got us some whole points after the first pair of ticks. No, much better! It got us up to 20 points in the evening and 60 score points early morning. The 6th team had like 1000 points at that time. We never knew, what teams 1-5 from top have.

The idea with autosubmission and further server-based bruteforcing was not new: the server was very slow, single request lasted typically for 30-70 seconds.

The Numbers

 The organizers set up a more lightweight version of submission checker. Instead of checking a fuel for a given car, one could submit a car and a fuel to get, whether the fit. This means, however, that we could supply the car ourselves. And that we see parser errors, if the car is malformed.

 At some point, the error message „tank x not connected with tank y“ was shown. The numbers were decimal, with minor modifications other values of x and y were shown. Two very patient members of our team made and verified assumptions on the form of the numbers and obtained the ternary encoding of the numbers, used in cars and fuels.

From it, the list encoding was concluded. Not so much time after that, we had an encoder and decoder for cars and fuels.

The Fourth Day

There were some issues with the encoder emerged next day. Late in the night the encoder’s/decoder’s implementor used some matrix library, which was fast, but not available for all our machines. Some early morning hacking was done then. But we had like 80 score points and it was increasing. We had hope, we might stay in the top 100, if everything goes well. We went on and decoded some cars, tried to find a fitting fuel for it, encoded it, launched a script for committing it. If the solution looked somehow general it was added to the autosubmitter for all cars. Last night the script was modified twice: for using a further car search interface from the organizer and to submit to newer cars first. The latter is explained easily: the priority matters. Using the fuel encoder (Haskell lists of lists of lists to ternary) and factory generator (ternary string to circuit) we generated multiple fuel instances, seemingly suitable for many cars. As many teams were submitting their cars and not all of them were very hard, we harvested multiple cars fitting some of the fuel instances, we were autosubmitting.

In an attempt to a classification, we can separate three car types. The trivial ones, we constructed on the first day theoretically and learned how to solve on the second day. The low-middle ones, consisting of multiple chambers with moderately long pipes (see task description), but with simple conditions. A fuel like [[[2]], [[2]], [[2]]] or [[[2]], [[3]], [[4]]] would fit such cars. Finally, we have the upper-middle ones, the description for them follows and the hard ones, we had no clue and no one without an automatic solver would.

 The upper-middle cars had a nice trick: the constrains, defined by the car, told something like A>=B, but A^k<=B^n. We had instances of integer 2×2 matrices, fulfilling it. Try to find some yourself, it is not that hard. Permutations of this solution for 2, 3 and 4 tanks also were submitted with the script. At this point we were two hours before contest end. We decided against attempts to write an automatic solver in the remaining time and tried to find some further car classes instead. We were analyzing few hard cars, but hat difficulties finding a solution manually. (I think we have found one for a particular car, but it was not generalizable, and time effort for manual solving was too hard.) Finding fuel for further car types of upper-middle difficulty class boosted our score rank.

We were not submitting cars before, even although we could. The point was: before full car decoder was there, we could only build a simple variation of a known car. To make it worse: of a most trivial car type. So such car would give us little points and allow everyone submitting their solutions to obtain points as well. But after we finally knew, how to construct both some fuel and a car, we have carefully constructed some cars and submitted all 72 allowed cars. I think, our cars fit into the middle type by above classification. This gave us another acceleration of the score.

It is hard to decide, what from two above measures (or maybe on of the previous boosts?) made our score points to go over 200. We did not stop working until few minutes until contest. The scripts were running constantly on all new and old cars. We ended the contest with 281.71 points at place 50 from the top.

Tools

We have made following tools: factory plotter, circuit interpreter, ternary to factory encoder, car decoder and encoder, fuel decoder and encoder (i.e. matrix representation to ternary encoder plus ternary to factory encoder) various bruteforce applications, various solution uploader scripts and a car downloader. Everything not being a script, was written in Haskell. We had some brutforcer in C the last day, but all non-that-stupid programs were written in Haskell. We had no time to make a constraint solver or to learn how to integrate an existing one into our toolchain. Our primary Python developer wrote some tools auxiliary tools for manipulating the list of cars.

Thanks

All the people from tower D5 (and not only from there) on the team: thank you guys, you are great!

Leave a Reply

You must be logged in to post a comment.