ICFPC-2008: first impressions

Introduction

There is such an annual programming competition, the ICFP Contest - that is, the International Conference on Functional Programming Contest. The competition is quite famous in the Russian-speaking environment, popularized by the Adept's reports , so I will briefly outline its main principles.

The competition is held once a year, the team game, tasks are issued on the competition website, solutions are sent there too. The game goes on for three days, you can live them non-stop, you can sleep and eat like all normal people. :) There is also the so-called lightning round, that is, a separate prize place among the decisions sent in the first day of the game.

Assignments to the advantageous direction differ from the classic olympiad tasks. In 2006 and 2007, these were wonderful quests from programming, with writing your own compilers of esoteric languages ​​for esoteric virtual machines; before, and this year, programming the logic of the behavior of an object in a virtual world.
')

This year

This year the task was formulated clearly and fully from the very beginning. You need to write a program that manages a Mars Rover via a TCP-shny socket (rover, I’m going to call it a rover by habit). The protocol of communication with the rover is described. Rover has a perfect grip with the planet, can accelerate, roll, gradually slowing down due to friction, and slow down. Able to turn right and left, and the steering wheel has five discrete values ​​of rotation - straight, right, left, all right, and all left. There is a certain delay, latency, in the execution of commands, not more than 20ms. The angular velocity does not change irregularly, but smoothly, linear and angular accelerations, as well as the coefficient of friction, are unknown at the time of the start of the series of rounds, and vary for different maps.

There are boulders on Mars, from which the rover bounces off, loses speed and changes direction, there are craters into which the rover falls to death, and there are Martians, with physics like a rover, only a little smaller in size, who dream to sacrifice the rover to the Gods of Barsum ( This is a reference to the cycle of fantastic stories about Mars by the writer Edgar Burroughs ). What they actually do if they catch up with the rover. The rover is planted at an arbitrary point on the map surface, the task is to get to the base, to the coordinates (0,0). Rover sees only that which falls into his area of ​​view, which is an ellipse, in one of which focuses is a rover.

Information about what the rover sees comes in the form of telemetry packets about once every 100 milliseconds.

Rover is planted five times in a row on the same map, at different, random points. The positions of the Martians and the Rover change in each round, the craters, boulders and physical constants remain the same as in the beginning. For any outcome of the round, whether it is a successful drive to the base, a fall into the crater, or just a timeout — the maximum time it takes for each card to complete — points are added that accumulate over all five rounds. The less points the better. The faster you get to the base, the better. Of the unsuccessful outcomes, the timeout was the most profitable, it was ruined in honor of the gods Barsum, the most shameful and unsuccessful was to fall into the crater. Accordingly, the comparison of the participants was to be conducted in this way, all the rovers in turn drive five rounds on the same card, several of the most successful applicants pass to the next card, the rest are discarded.

That's probably all.

The organizers provided an image of the system on which the presented solutions will be launched, in the form of a liveCD with knoppix, as well as a server compiled for this system and a set of sample maps for it. The server, being launched under X, showed at the same time a window in which he was drawing what was happening with the rover.

In the organization of the teams there were two differences from previous years. Firstly, this year no prior application for participation was required, all decisions made before the deadline were made. Secondly, they imposed a limit on the size of the team, the team should have no more than five people.

On this abstract description of the introductory, I finish, and turn to personal feelings and thoughts.

General pro organization

Opinions about what happened at ICFPC this year vary greatly. For example, the overwhelming majority of people who took part in competitions of previous years, almost immediately after the publication of the assignment, spoke very negatively about him. Like, it used to be better. I dreamed of a similar task for a long time, so I didn’t become boring. And history shows that such tasks are also quite typical for ICFPC. In general, it seems to me that speaking out like this is the same as repeating “a book was better than a film,” not understanding the fundamental incomparability of these two types of narrative presentation.

But I wanted to say about the organization. So, I have seen positive reviews. But the work of the organizers seemed to me unsatisfactory. The LiveCD, on which it was supposed to start the server with X-gui, initially did not start X, and it was necessary to add configuration instructions to the official FAQ. The server itself was added by the organizers right along the way, many bug fixes were made, although according to official data, the competition was being prepared since January - one could have time to write a normal implementation. For example, our team launched its own simple version of the test server in the very first day.

Moreover, the server itself was laid out not immediately after the start of the contest. And its statically linked version for other Linux distributions and for MacOS X is altogether late in a day or so. The Windows version did not appear, which for at least one member of our team became fatal - his car did not pull the virtual user, like mine, and he dropped out of the competition, because he couldn’t really test his own code.

As a result, many teams spent the first day “playing Linux administrators” instead of playing programmers.

On the other hand, we must pay tribute to the organizers, they provided good feedback channels through IRC, mailing lists, bug tracker and wikis, and really solved the problems on the go. I just want to say that more thorough preparation would avoid most of these problems.

Actually the game

It should be noted that the restriction of five people for our team, who had gathered for the game almost six months before its start, was an unpleasant surprise. The rules said that "you can participate in a larger composition, but simply do not count on prizes." Not that the prize for the first place in a thousand dollars for a team of a dozen people meant something to us, and we decided that we would play in the composition in which we met, because pleasure is more important. However, someone was disappointed with the assignment, someone, as I already wrote, could not participate for technical reasons, someone just did not show activity, someone suddenly found himself busy with his own affairs - and hurray, there are exactly five of us left that eliminated moral and ethical problem from the horizon. :)

The main language of development in our team was chosen python. Not that there were many python gurus among us, but everyone wanted to use (after all, the main thing is to enjoy the game :)) a dynamic language suitable for rapid development, and the choice was between Ruby and Python. But hack is too esoteric in order to work with him, without having developed enough good skills, and no one had any particular objections to python. We expected to optimize the bottlenecks using Pyrex, but later it was not useful.

First day

The first night (well, this is in my GMT + 6 time) we spent on the war with the LiveCD and the implementation of the interaction protocol. In this place, the python showed all the beauty of dynamic typing - when the templates that describe the protocol parser, at the same time, specify the fields of the object classes and events, this is a song! :) Which, however, we rewrote in a more conventional style somewhere around the end of the second day of the game.

Approximately 10 hours after the start, the first version of Cerebellum (“cerebellum”) was implemented - a low-level rover controller that took a command like moveTo (x, y) and already translated it into the turn and acceleration commands in the protocol. At about the same time, Vlad, the person who actually wrote Cerebellum, and the implementation of the protocol, was also a client visualizer of what was happening on the client side, written using GLUT, the python api for OpenGL. This helped a lot later, as we were able to display any intermediate data on the map in the same place and to be guided in what was going on. I will say more - without such a visualizer, debugging logic would be incomparably more complex.

Lyrical digression. I really liked the organic, with which self-organized tasks and teamwork. Duplication of work was not enough, each was engaged in a separate aspect of the problem, and at the same time the task was solved. If I lacked something in our code, I knew who to turn to with this problem and knew that I would get the right solution in reasonable time. And all this happened somehow by itself, without any conscious organizing on our part.

So, I spent a few hours licking what Vlad sketched, combing decent bugs and achieving stable application performance.

Then, the development of maps of static objects was completed successfully - the objects were stored as a complete list, for fast iteration when drawing, and in a binary tree, to get only the current set of objects.

As a result, we had a rover, which unfolded at the start and sawed straight to the base - and all this is purely at the level of the cerebellum, "on reflexes." The guys at that time were engaged in a statistics collection module - data on real latency, and calculation of acceleration and friction coefficients based on data on latency and telemetry. Therefore, I sat down and threw the decision to choose the path, which actually remained later to our mainstream - a simple solution, like sneakers.

Another lyrical digression. I adhere to the point of view that everything ingenious is simple. In programming, I don’t believe in universal uber solutions based on complex mathematical theories (it’s obviously about application programming, and not about problems like data encryption or calculating latency and friction coefficients). I believe in simple ideas and simple hacks in places where simple ideas fail. My solution was simple, and further improved by simple hacks.

Rover on my navigation algorithm successfully coped with simple maps, but already on a spiral (for those who are in the subject;)) it demolished the roof and it coped a maximum of 1 out of 5. The first simple hack improved this figure to 3 out of 5.

Even our rover, in my algorithm, ignored the Martians, as a fact - and by the way, according to rumor-reviews, many teams did this. Martians move quickly, but along gentle trajectories, do not maneuver well and usually cannot catch the rover even at arm's length. That is, getting into the Martian is an event very unlikely and purely random. I had an idea to use some tactical maneuver, when the Martian is very close, but her hands have not reached realization.

Second day

The second day we, as it turned out later, just lost. I waited for the guys to realize a better, more responsive, moveTo, which, for example, would make more accurate turns when there are many obstacles around; the guys wrote unknown parameters; Vlad was going to make the system optimal, that is, the fastest and most accurate, passing a set of waypoints. We also added to the piggy bank an algorithm for moving a “drunk rover returning home,” which behaved quite tolerably.

In general, from the useful, that is, useful later, a predictor was written over the course of these days, which calculated the current physical trajectory of the rover in the next two or two seconds. The predictor used something from the statistics module. By the end of the second day, as I said, the guys rewritten Cerebellum and the protocol more responsibly and readily. For the most part, I missed the second day - unsuccessfully for the same weekend there was a mass of non-competition matters.

Third day

On the third day, Vlad added his own module for following the trajectory, but first of all, it did not work as expected, and secondly, it did not provide the necessary API, on which I could put my logic on the waypoint stack. Meanwhile, a map was found on which my algorithm gave horrible, disgusting results: the rover had serious problems understanding the concept of a chain of intersecting craters. I went in search of a new hack.

More precisely, at first I spent a decent amount of time writing the processing logic of a chain of craters and finding an extreme waypoint circling the whole bunch of them, but this code did not work as it should. Already in the last 3-4 hours of the contest, I realized that I wouldn’t debug this code, and found another hack for an algorithm that improved the results to 3 out of 5 on this infernal map. Then the guys had a great idea in their simplicity and genius - keeping the crater in the map, exaggerate its size by a meter. It worked!

Somewhere in half an hour before the end of the competition, we sent our trial version to the selection committee, which we still hoped to improve. In the last half hour, we tried to use the trajectory predictor for emergency braking in the event of a possible collision, but this did not bring us an additional winning round on the test card, but added, due to the braking, one timeout. 10 minutes before the end of the competition in one very rare and almost unused branch of my code, two typos were found, which, although rarely worked, but killed all the actions of the rover for all rounds ahead. Prior to this code, the case did not reach at all on official maps, but it fell on one of those that we generated for tests. In the last minutes we were packing a version with a fix, but did not have time to send the commission before the reception was closed. Now we keep our fingers cross and hope that the situation in which this code will work will not arise. :)

More generally

In general, it is not difficult to write some solution for some more or less imputed obstacle avoidance. I am sure that the real question about the winner will be solved in trifles. The points system is designed so that even one fall into the crater, one, albeit a very unlikely, meeting with a Martian can separate the winners from those who drop out on the map. Among those who have learned to avoid these troubles with a 100% result, the speed of passage of the track will decide everything. This is the maximum allowable speed of the trajectory, and the construction of the shortest, and not just a satisfactory path. It will be very interesting for me to look at the actions and code of the winner.

Oh yes, python more - never. To hell with this dynamic typing, which doesn’t reveal even a typo before runtime. Next year I will write everything on Scala - static typing, compilability, performance like Java, and power and expressiveness like a mad python-haskel cross.

Feedback

Now I collect reports from different teams about how it was.

Judging by the different blog entries, our simple solution may not be so bad. So the guys did not have time to send their decision , despite the active work. I am still grateful to the person from our team who organized the sending of a preliminary version of our code. Others have begun , but it is not clear whether the matter has been accomplished. Another team’s attempt to use Haskell failed, and they added their preliminary lightning solution to Perl-e. There, on the contrary, the author considers trivial hacks in place, as in my code or in their pearl-barley solution, an evil and is going to realize a beautiful generalized solution. Another team that chose a simple solution is also not very sad about this. :)

On the other hand, there is a strong solution from the guys at Scheme. Although the results of the test runs that they published, we seem to be better, but in the last two hours they managed to implement a very important idea, to the realization of which I never got around - a stack of strategies. True, I intended to implement it as a team of different priorities - strategic, tactical and shunting - the rozer cerebellum.
The guys from Kharkov in C ++ managed everything. And a universal intelligent algorithm, and otdebazhitsya, and send a solution in the last minutes.
Someone participated simply for interest .
At the moment, the Adept has not yet published its report.

If you have links to reports that are not mentioned here - please write, I will add them to the list.

In general, everything. According to the information on the official website of the competition , we will not know the results soon - September 22-24. The winners, however, learn about their victory long before, to get the opportunity to prepare for the trip to the awards ceremony.

UPD: created a blog for this topic and moved the post there.

At last

"For dessert" - the adrenaline of the last ten minutes of the contest .