Concours de l'ICFP

Tous les ans, en marge de l'International Conference on Functional Programming a lieu l'ICFP Contest, un concours de programmation de 72 heures.

L' année dernière, je n'avais pas participé pendant le concours, mais avait fait une partie du sujet. Ce dernier était vraiment amusant : on récupérait une grosse image binaire et les spécifications d'une machine capable d'exécuter l'image binaire. Il fallait donc commencer par programmer une sorte de machine virtuelle, pour exécuter l'image binaire. Une fois ceci fait, l'exécution de l'image binaire permettait d'entrer dans une sorte de mini-système d'exploitation, dans lequel il y avait tout un tas de défis à relever. À chaque défi réussi, on recevait un hash permettant d'attester du succès de l'équipe et de le saisir dans le site Web (ce que je n'avais pas fait, puisque le concours était terminé depuis bien longtemps). Il fallait par exemple bricoler avec un interpréteur BASIC qui numérotait les lignes avec les chiffres romains, ou encore travailler avec un langage de programme en 2D, style ASCII-Art. C'était vraiment passionnant. Le code de la machine virtuelle que j'avais écrit et optimisé avec l'aide de quelques amis est par ici.

Du coup, pour cette année, je me suis dit que j'allais essayé de participer. Le concours a lieu ce WE, de vendredi midi à lundi midi, et le sujet est disponible sur icfpcontest.org. On récupère l'ADN d'un extraterrestre, qu'il faut modifier pour l'adapter à la vie sur terre. Pour cela, il faut transformer cet ADN en ARN, puis en image PNG. L'ADN fourni permet d'aboutir à une image donnée, et tout l'objectif est de modifier l'ADN pour qu'après la génération de l'ARN, puis de l'image, on arrive à une autre image. Les règles pour passer de l'ADN à l'ARN, puis de l'ARN à l'image sont fournies.

Entre hier soir et ce matin, j'ai réussi à faire un convertisseur ADN vers ARN, implémenté en Python. Il passe les tests basiques, mais est vraiment très lent: 1 minute 22 secondes pour 1000 itérations, alors qu'il y a près de 2 millions d'itérations à faire d'après le sujet. Visiblement, les rédacteurs du sujet s'attendaient à cela, puisque dans le chapitre 6, il est clairement indiqué qu'il faut faire très attention aux performances. Ne sachant pas vraiment comment fonctionne Python en interne, j'ai choisi de recoder le tout en C. Mais les performances ne sont guère meilleures : 1 minute et 12 secondes pour 1000 itérations. Pour les curieux, mon code est par là. Le code C est clairement immonde, avec des gros buffers statiques à droite à gauche pour aboutir rapidement à un prototype fonctionnel.

Du coup, même après avoir passé la journée sur ce convertisseur ADN vers ARN, je suis toujours bloqué. Il doit y avoir une astuce, un raccourci qui n'est pas exprimé dans le sujet, mais qu'il faut trouver.

Enfin, en tout cas, comme l'an dernier, le sujet est vraiment très prenant.