Concours de l'ICFP

En 2006 puis en 2007, j'avais un peu participé au concours de l'International Conference of Functional Programming (qui n'est pas obligatoirement réalisé avec des langages fonctionnels).

Cette année, le concours avait lieu ce WE, de vendredi 20:00:16 à lundi 20:00:16. Nous avons travaillé dessus à 4, mais seulement de vendredi 20:00:16 à environ 4h du matin, soit en gros huit heures de travail sur les 72h de concours. Forcément, le résultat est à la hauteur de notre modeste participation: l'équipe Toulibre++ termine 307ème sur 317 participants classés. Nous n'avons en effet soumis la résolution que pour 2 problèmes sur 16. D'ailleurs, une personne de notre équipe a résolu 2 autres problèmes après notre séance de travail, mais nous ne les avons pas soumis.

Même si le concours est terminé, une petite description du sujet vous donnera peut-être envie d'y jeter un œil. Avant la publication du sujet, la FAQ du site Web disait que des indices étaient déjà en ligne. Pourtant, en regardant de fond en comble le tout petit site Web du concours, je n'avais rien vu d'intéressant. Un seul détail paraissait étrange: le démarrage du concours à 13:00:16 CDT. Pourquoi pas à 13h pile ?

Ça s'est expliqué quand le sujet a été dévoilé : un shuttle s'est accroché à la station Mir le 29 juin 1995 à 13:00:16. Le sujet serait donc lié à l'espace. Et effectivement, l'objectif était de guider un satellite.

Le sujet se décomposait en 4 problèmes comportant chacun 4 scénarios similaires mais avec des données de départ différentes. Pour chaque problème était fourni un blob binaire, pour lequel il fallait écrire une petite machine virtuelle. Il était en effet écrit avec un jeu d'instruction assez particulier (pas de sauts par exemple, et une écriture en mémoire possible seulement à l'adresse de l'instruction), décrit dans le sujet. Cette machine virtuelle faisait donc tourner le code qui simulait le déplacement du satellite. Il fallait fournir des données en entrée (scénario utilisé, et vitesse du satellite en x et en y), et une exécution du binaire renvoyait des données en sortie (position courante du satellite, score actuel, essence restante, position à atteindre). À partir de ces données de sortie, il fallait recalculer des données d'entrée pour le prochain cycle, les injecter dans la machine virtuelle, puis relancer l'exécution du binaire.

Le développement de la machine virtuelle fût relativement simple, si ce n'est que nous avons perdu du temps sur une erreur du sujet, sur laquelle toutes les équipes ont buté (d'après ce que nous avons pu lire sur le canal IRC du concours). La description du jeu d'instruction comportait une erreur de décalage d'un bit, ce qui évidemment faussait complètement l'exécution. En bons bourrins que nous sommes, nous avons donc développé la chose en C (avec un soupçon de C++), car tout le monde ne connaissait pas le Python dans notre petite équipe. Comme quoi le «fonctionnel» dans le titre n'est pas vraiment important :-)

Une fois la machine virtuelle développée, il fallait s'attaquer aux problèmes en tant que tels. Ils relevaient finalement plus de la physique que de l'informatique pure. Dans le premier problème, le satellite que nous contrôlions était en orbite à une altitude donnée, et il fallait l'amener à une autre altitude. Évidemment, la ligne droite n'est pas la bonne solution car il n'y a pas assez d'essence pour cela. Il faut parcourir une trajectoire elliptique qui ne nécessite que deux impulsions : une impulsion pour sortir de la première orbite, puis une seconde impulsion pour se caler sur la deuxième orbite. Heureusement, ce principe était expliqué dans le sujet, et Wikipédia donnait plus d'informations à ce sujet.

Nous nous sommes amusés à générer un fichier avec toutes les positions du satellite pour tracer avec Gnuplot la trajectoire du satellite ainsi que les orbites de départ et d'arrivée. Ce fût fort utile pour mettre au point le bazar.

Le second problème, que nous n'avons pas abordé, était assez similaire, mais il ajoutait une contrainte sur l'orbite d'arrivée : il fallait arriver au même moment qu'un satellite gravitant sur cette orbite. En bref, il fallait bien calculer le moment de départ de l'orbite initiale.

Tout cela était bien amusant, j'espère pouvoir participer à nouveau l'an prochain, peut-être en prévoyant une participation plus intensive.