Concours de programmation : retour d'expérience de 4 IFs, émissaires en Irlande !

Benoît Chabod, Mathis Hammel et Sophie Legras vous font vivre leur expérience lors d'un concours de programmation ACM sponsorisé entre autres par Google.

Félicitations à eux pour leur place de 1er et 2eme !

 

 

 

C’est la semaine dernière que nous - Benoît Chabod, Mathis Hammel et Sophie Legras, trois étudiants du département informatique de l’INSA Lyon - nous sommes rendus à Cork pour le concours d’algorithmique universitaire irlandais, l’IrlCPC (Irish Collegiate Programming Contest) organisé par la prestigieuse association ACM. Pour remettre cette journée du 25 mars 2017 dans son contexte, nous avons tous les trois effectué un échange Erasmus à Trinity College Dublin et sommes donc partis pour participer à la compétition en représentant cette école.

 

Après quelques heures de train au départ de Dublin, nous descendons à Cork, et nous découvrons l’enceinte magnifique de l’école UCC, où le concours allait se dérouler. Nous sommes alors accueillis par l’équipe organisatrice et nous nous rendons dans la salle pour le round d’entraînement, le but étant de se familiariser avec l’environnement, et de vérifier que le matériel fonctionne bien. Nous séparons alors notre petit groupe d’insaliens pour rejoindre nos équipes respectives : Mathis et Benoît retrouvent Arne, un étudiant d’origine allemande avec qui ils ont déjà pu se rendre à d’autres compétitions de programmation (équipe Wunderbaguette), et Sophie rejoint Oisin et David, deux élèves irlandais (équipe Team18).

La compétition, comme toutes celles organisées par l’ACM, possède un format original. Un seul ordinateur pour l’équipe, et aucune ressource internet autorisée. Plusieurs problèmes sont posés, et c’est parti pour quelques heures intensives de réflexion et de code ! L’entraînement  a duré moins d’une heure et nous avons ensuite pu aller déjeuner. Une belle occasion pour discuter avec les employés de Google, entreprise qui sponsorise l'événement.

 

Puis à 13h, c’est le départ pour la véritable épreuve. Six problèmes, quatre heures et des équipes toutes plus motivées les unes que les autres. Nous prenons alors connaissance des problèmes.

 

 

Chronologie du concours vue par Mathis de l’équipe Wunderbaguette :

 

12h58 (T-0:02) : Ouverture des portes de la salle, on se met en place. Le dossier contenant les exercices est devant nous et l’ordinateur est allumé, mais on ne touche à rien : c’est la règle.

13h00 (T+0:00) : Le concours devrait commencer mais aucune annonce n’est faite. Certainement un petit problème technique qui sera vite résolu, on attend.

13h05 (T+0:05) : Toujours pas d’annonce, mais certaines équipes commencent à ouvrir leurs documents et commencent à coder. On demande aux organisateurs et apparemment le concours est en route depuis 13h… 5 minutes de retard c’est assez peu, mais il ne faudra pas se laisser avoir par la montre. On prend connaissance des 6 exercices, je commence à mettre en place les fichiers et les commandes d’exécution pendant que Benoît et Arne regardent les deux premiers problèmes.

13h07 (T+0:07) : Arne finit de lire le premier énoncé. La question est très simple : on fournit une carte de mines du jeu de démineur, par exemple :

o x o x o

o o o x x

o o o o o

et il faut calculer le nombre de mines qui entoure chaque case :

1 x 3 x 3

1 1 3 x x

0 0 1 2 2

Une implémentation rapide nous rapporte 9/10 points, il est donc fortement probable que notre programme soit trop lent à traiter le dernier test qui est le plus grand. On reviendra plus tard sur cet exercice, Benoît a commencé l’exercice 2 sur papier et on ne veut pas perdre trop de temps pour un seul point.

 

13h15 (T+0:15) : Le problème 2 est une traduction de nombres du format décimal au format romain. Les nombres à traduire sont compris entre 1 et 3999. On essaie une solution qui nous semble simple, sans trop savoir si certains cas particuliers peuvent poser problème. Le principe de notre algo est de traduire les milliers, puis les centaines, les dizaines et les unités, et de concaténer les 4 résultats. Par exemple, pour traduire 2017 :

2 milliers -> MM

0 centaines -> rien

1 dizaine -> X

7 unités -> VII

Le résultat est MMXVII, ce qui est correct.

On implémente rapidement cet algorithme, en faisant attention à ne pas se tromper dans chacune des 35 traductions qui sont faites à la main. On soumet le script sur la plateforme, et… 0 points, apparemment on ne passe même pas les cas d’exemple. C’est rassurant, on peut débugger facilement en utilisant les deux tests d’exemple fournis. Après une rapide revue du code, on remarque que notre programme affiche les résultats ligne par ligne, et il faut en fait les afficher sur la même ligne séparés par des espaces. Nous corrigeons, et sommes récompensés par 10 points !

 

13h30 (T+0:30) : Le problème 4 semble au premier abord plus simple que le 3, donc on se lance sur celui-ci. Notre solution fait 8 lignes et nous rapporte 6 points. Nous trouvons une optimisation en performances, mais celle-ci est assez complexe et nous la gardons pour plus tard. Benoît reconnaît exactement l’algo à utiliser pour le dernier problème (distance de Levenshtein). Seul problème : je suis le seul à avoir déjà implémenté cet algorithme et c’était il y a un an et demi… Je me mets donc dans un coin de la salle avec mon carnet pour essayer de retrouver les formules.

 

13h50 (T+0:50) : L’exercice 5 est quasiment fini par mes deux coéquipiers, et je pense avoir une bonne idée pour Levenshtein en me basant sur ce dont je me souviens de l’algorithme : du dynamic programming en 2D, avec des flèches dans tous les sens et des valeurs associées. Ma solution a du sens, et je pense qu’en changeant un peu les valeurs et les conditions on peut obtenir une solution valide. J’utilise l’un des cas d’exemple fournis pour valider sur papier, et obtiens bien la valeur attendue. Pendant ce temps, Arne et Benoît ont presque fini de coder une solution pour l’exercice 5, qui est un tri topologique de graphe acyclique dirigé. Les cours de graphes de 3IF datent un peu, on se rappelle en rigolant nos notes au partiel : j’avais eu 12, Benoît avait eu 8. On espère que la performance sera meilleure qu’au DS, mais pas de chance : notre solution ne nous rapporte que la moitié des points… Les profs avaient donc eu raison de nous mettre des notes pareilles !

 

14h05 (T+1:05) : Je me lance sur le code de la solution de Levenshtein, et contrairement à ce que j’attendais, la solution de base me donne un 7/10 ! Par contre, aucune idée des corrections à apporter pour atteindre la note maximale. On abandonne donc ce problème et passons à autre chose.

 

14h15 (T+1:15) : Nous entamons l’exercice 3, seul exercice que nous n’avions pas tenté de résoudre jusque là. C’est un exercice qui parle de la conjecture de Goldbach, et il faut pouvoir calculer le nombre de manières d’écrire les nombres pairs comme des sommes de 2 nombres premiers (Par exemple 10 peut s’écrire avec les deux paires de premiers 5+5 et 3+7). Le calcul prend environ 30 secondes en local, on ne pourra pas valider les cas limites mais on tente quand même. On récupère quelques points mais comme prévu pas 10/10. Nous avions pensé à une optimisation qui consisterait à précalculer toutes les réponses possibles (250 000 valeurs) et notre programme aurait juste à recracher ce qui est calculé d’avance. Le précalcul dure 30s, et le code source résultant fait 1MB, mais la plateforme l’accepte sans souci et nous accorde les 10 points.

 

14h30 (T+1:30) : Nous faisons le bilan :

Exercice 1 : 9 points, facile d’avoir 10

Exercice 2 : 10 points

Exercice 3 : 10 points

Exercice 4 : 6 points, optimisation temporelle assez simple mais plus longue à coder

Exercice 5 : 5 points, relire le code et trouver des cas qui ne marchent pas

Exercice 6 : 7 points, flou total

Pendant que Benoît et Arne reprennent l’exercice 5 sur les graphes, je me lance sur la réalisation (sur papier, car nous n’avions qu’une machine) du code d’une structure de données qui accélèrera le programme simple du problème 4 (un Trie pour faire une recherche très rapide dans des débuts de mots). Tout se passe bien, mes coéquipiers me laissent la place alors que je termine, et nous récupérons les 10 points de l’exercice 4 au bout d’une quinzaine de minutes.

 

14h50 (T+1:50) : Toujours pas d’idée viable pour corriger la solution du 5. On sent qu’il ne faut pas perdre pied à ce moment car notre élan commence à ralentir. Je discute avec Arne d’une nouvelle solution qui nous ferait repartir du début mais qui clarifierait grandement le code et pourrait nous permettre de trouver l’erreur. C’est alors que Benoît, qui avait continué de modifier le code, nous annonce avoir interverti deux indices et validé les 10 points de la solution. Peu fiers mais très satisfaits de notre solution, nous retournons sur l’exercice 1 qui semblait être notre seul espoir d’avoir quelques points de plus.

 

14h55 (T+1:55) : Nous nous lançons à 3 sur un bricolage de la solution du 1 pour améliorer le temps d’exécution. En effet, notre utilisation abusive de certains éléments de python avaient rendu une boucle plus lente qu’elle ne pouvait l’être. En plus, notre fix a rendu le code bien plus joli qu’avant. Notre solution de secours était d’implémenter le programme en C++ mais nos calculs de complexité nous avaient montré que cela ne serait pas nécessaire. On soumet, et 10 points nous sont accordés. Il reste donc un seul exercice qui nous sépare du score parfait, mais nous n’avons aucune idée de la manière de le terminer. Je me souviens à ce moment de l’article Wikipédia sur la distance de Levenshtein (algorithme de l’exercice 6), qui a une colonne et une ligne vides au début du tableau. J’ajoute donc deux lignes à mon script, et à ma grande surprise la plateforme accorde maintenant 9 points !

 

15h05 (T+2:05) : On ne peut pas s’arrêter si proches des 60 points ! Nous pensons que le point qui nous manque est lié à un souci de performance. Après relecture de code, rien d’évident n’apparaît et il semble que la complexité temporelle devrait largement passer. Dans une dernière tentative de valider le point manquant, nous tentons une traduction de python vers C++ pour accélérer le temps d’exécution.

 

15h25 (T+2:25) : L’écriture du code en C++ a été longue, ça faisait longtemps que nous n’avions pas utilisé ce langage. Juste avant de terminer, un organisateur vient nous annoncer que l’un des fichiers du serveur est incorrect, et qu’il faut tenter de resoumettre l’exercice 6. C’est maintenant clair, le dernier point qui manquait ne vient pas de notre programme mais plutôt de la validation. Nous soumettons l’ancien code source qui avait rapporté 9 points, et… c’est dans la poche ! Wunderbaguette valide les 60 points du concours en 2h25 (en réalité toutes nos solutions étaient valides vers 15h). Nous suivons les instructions des organisateurs, et ne sautons pas de joie en hurlant : les consignes étaient de garder notre discrétion, et de sortir dans le calme si nous le souhaitions. Comme nous n’avions rien d’autre à faire pour les 90 minutes qui restaient, nous sommes restés dans la salle.

 

15h30 (T+2:30) : Pause goûter, puis pictionary en anglais avec l’équipe. La restriction : utiliser LibreOffice Draw et faire deviner en un seul trait continu.

 

16h00 (T+3:00) : Je fais signe à l’équipe de Sophie que nous avons fini. Eux apparemment sont toujours en plein dans le concours, idem pour l’équipe de DCU que nous pensions gagnants d’avance. Nous pensons être premiers mais il est possible que des équipes dans d’autres salles aient terminé avant 15h. Pour la dernière heure, nous nous lançons dans la réalisation d’un jeu de réflexe qui mesure le temps de réaction.

 

17h00 (T+4:00) : Fin du concours ! Et je tiens le record du temps de réaction avec un spectaculaire score de 8 millisecondes (j’ai cliqué totalement au hasard et eu beaucoup de chance).

 

La fin de la compétition est assez intense et incertaine, car le scoreboard a été gelé deux heures avant la fin de la compétition. Nous ne sommes alors certains que de deux choses : l’équipe Wunderbaguette a complété tous les exercices en 2h30 et l’équipe Team 18 a réussi à valider le dernier exercice seulement dix minutes avant l’arrêt du concours.  Nous sortons alors prendre une photo avec tous les participants, ne sachant pas réellement à quoi nous attendre.

 

 

Et arrive enfin l’annonce des résultats. La troisième équipe est appelée sur l’estrade : ce sont des élèves de DCU que nous connaissons bien. Et comme nous avons pu discuter avec eux à la fin de l’épreuve, nous savons qu’ils n’ont pas validé la totalité des problèmes. Nous comprenons alors que nous allons monter sur le podium ! Le rythme cardiaque s’accélère.

 

L’équipe Team 18, avec Sophie, termine donc deuxième du concours.

 

 

Et l’équipe Wunderbaguette, avec Benoît et Mathis, prend la première place.

 

 

C’est donc très heureux que nous sommes allés fêter nos résultats dans Cork, et nous en avons profité pour visiter un peu la ville !