Retour sur le concours de code #CodeonTime organisé par Meritis à l’occasion de #Devoxx2022.
Le principe : résoudre 4 exercices de code le plus efficacement possible depuis son ordinateur.
Découvrez le retour d’expérience des meilleurs joueurs et les tips de Gaëtan Eleouet !
À l’occasion de Devoxx 2022, Meritis a lancé un concours de code : Code on Time. Le principe : résoudre 4 exercices de code le plus efficacement possible depuis son ordinateur. Du 25 avril au 4 mai dernier, 346 développeurs de tous les niveaux ont participé. Gaëtan Eleouet, Ingénieur Software-Engineering, Expert Java Meritis, fait le point et partage quelques tips pour vous permettre de relever le prochain défi.
Pour remporter l’épreuve, il fallait non seulement donner une bonne réponse mais aussi tenter de récolter le plus de points pour gagner une Nintendo Switch ! Gaëtan Eleouet présente ci-dessous en quoi consistaient les exercices mais, surtout, partage les retours d’expériences des meilleurs participants de l’épreuve.
1er exercice : trouver l’adresse qui consomme le plus
Il s’agit d’identifier ce maximum à partir de la liste fournie en entrée. Il n’y a pas de pièges, chaque adresse n’est présente qu’une fois. Il est même possible de résoudre l’exercice manuellement (certains l’ont fait) ou via un tableur !
Le tips de Gaëtan
L’adresse qui consomme le plus consomme 1 de plus que le précédent, ce qui permet de garantir l’unicité de la solution !
2e exercice : trouver un code qui correspond à de nombreux critères
Une manière de faire efficace consiste à tester tous les nombres un par un. Il faut faire attention à bien comprendre chaque contrainte et à l’implémenter convenablement.
Le tips de Gaëtan
La plupart des nombres de la liste sont divisibles par 7 pour simplifier le générateur !
3e exercice : trouver dans la liste les 3 nombres dont la somme fait 987 654 321 et en calculer un code
Ici, deux difficultés se présentent :
- Il y a 25 000 nombres dans la liste, ce qui rend la recherche exhaustive particulièrement TRÈS longue.
- Enfin, le code demandé repose sur la multiplication de 3 grands nombres qui font un overflow (dépassement de taille) sur des entiers « classiques ».
La recherche exhaustive peut être parallélisée pour être plus rapide : Rémi Thomas (@iso8859) a ainsi exécuté sur son processeur dans 24 threads en une dizaine de minutes sa solution avec quelques optimisations.
Une façon plus conventionnelle de résoudre l’exercice est de remplacer la triple boucle par une double boucle et recherche dans un dictionnaire pour tester en temps constant la présence du nombre qui complète le triplet.
Le tips de Gaëtan
C’est ce qui est aussi fait par Postgrsql ! Mickaël Galien a accepté de nous partager sa solution en SQL :
— objectif : trouver un triplet n1, n2, n3 tel que n1 + n2 + n3 = 987654321
— contrainte : le produit cartésien n’est pas envisageable car 25000 * 25000 * 25000 = 15625000000000 combinaisons
— données : les nombres ont été préalablement importés dans une table tmp.exercice3
—
— pour limiter, on va chercher les 3 chiffres n1, n2 et n3 en considérant que n1 <= n2 <= n3
with candidat_n1 as (
— n1 (i.e. le plus petit nombre) * 3 ne peut pas dépasser 987654321
— on passe de 25000 à 11723 candidats
select motdepasse
from tmp.exercice3
where 3 * motdepasse < 987654321
),
candidat_n2 as (
— n2 (i.e. le nombre du milieu) * 2 ne peut pas dépasser 987654321
— on passe de 25000 à 17564 candidats
select motdepasse
from tmp.exercice3
where 2 * motdepasse < 987654321
)
select
n1.motdepasse as n1,
n2.motdepasse as n2,
n3.motdepasse as n3,
(n1.motdepasse + n2.motdepasse + n3.motdepasse) as total,
(n1.motdepasse::numeric * n2.motdepasse::numeric * n3.motdepasse::numeric) % 987654321 as reponse
from candidat_n1 n1
inner join candidat_n2 n2 on n1.motdepasse <= n2.motdepasse — n1 <= n2
inner join tmp.exercice3 n3 on n2.motdepasse <= n3.motdepasse and n3.motdepasse = (987654321 – (n1.motdepasse + n2.motdepasse)) — n3 = 987654321 – (n1 + n2)
limit 1 –
Le limit 1 permet de terminer la requête dès qu’un résultat est trouvé et donc de gagner du temps. Voilà comment il a trouvé la solution en une vingtaine de secondes !
4e exercice : l’optimisation
L’idée est d’améliorer sa solution et donc gagner plus de points. Pour avancer dans sa résolution, il faut progresser étape par étape. Un premier départ peut consister à choisir un fichier et à construire le chemin pour aller le récupérer.
On en profite alors pour prendre tous ceux qui sont sur le chemin. Ensuite, on peut améliorer le choix du fichier, la construction du chemin, choisir de prendre ou de ne pas prendre un fichier sur le chemin, etc. Les seules limites sont celles de l’imagination !
Témoignage de Mathis Hammel
Mathis Hammel (@MathisHammel), 2e du concours, résume son algorithme. Le principe est de chercher plein de chemins qui vont chacun prendre 10 fichiers distincts :
- Initialement, on a aucun chemin formé et tous les fichiers sont ‘‘libres’’ (= liés à aucun chemin) ;
- On fait un Dijkstra pour trier tous les nœuds par distance croissante ;
- On itère sur les nœuds par distance croissante en considérant le chemin le plus court ;
- Si le chemin passe par moins de 10 fichiers libres, on le skip (parce que non viable), sinon le chemin accapare tous les fichiers disponibles. On peut aussi voler des fichiers à d’autres chemins qui ont >10 fichiers.
J’ai aussi un mécanisme de reset au bout de la moitié du temps : une fois que 1 800 secondes se sont écoulées, je regarde les 15 chemins qui ont les fichiers les plus « demandés » (= ceux sur lesquels passent le plus de chemins) et je les supprime complètement. Ensuite, je relance l’algo depuis le début. Ça peut se Monte-Carlo parce que j’ai plein de chemins de même longueur donc je peux randomiser le tie-break.
Dans l’immense majorité des cas, ça me donne ~1705 fichiers (donc 170 ou 171 chemins, dans 99 % des cas je dirais), mais de temps en temps je chatte et je trouve un 172. Le 173 me semble pas vraiment faisable parce que mon meilleur 172 se termine à 3 596 secondes donc clairement pas de quoi en caler 10 de plus. J’ai essayé de faire genre 172 dizaines suivi d’un ou deux fichiers solo proches du serveur 0, mais même ça n’est pas suffisant.
- Vous pouvez lire des informations complémentaires sur Dijkstra qui permettent de trouver le plus court chemin.
- Et consultez le principe des algos Monte-Carlo qui amènent de l’aléatoire dans la recherche de solutions.
Retour d’expérience de Pierre Testart, vainqueur du concours
Pierre a su dépasser ses limites et nous détaille lui aussi ci-dessous son algorithme :
J’ai d’abord fait un greedy qui cherche la façon la plus rapide de collecter 10 fichiers (en prenant en priorité les fichiers plus rares), se téléporte au début et recommence jusqu’à épuisement du temps. J’ai remarqué que les runs de 10 fichiers prenaient jusqu’à 28-29 secondes. Je me suis dit que j’allais seulement chercher des solutions avec des runs <= 29 secondes parce que c’était improbable de trouver de meilleures solutions avec des runs plus longs.
Ensuite, je me suis demandé combien il existait de chemins partant du spawn (départ) qui prennent 29 secondes ou moins. De façon surprenante, assez peu : j’ai pu énumérer environ 9 000 chemins « intéressants » en quelques secondes ! J’ai gardé seulement le meilleur préfixe de chemin pour chaque paire (serveur, ensemble de fichiers vus) pour éviter que la génération explose trop.
En supprimant les chemins inutiles (pour lesquels un autre chemin possède au moins les mêmes fichiers sans coûter plus de temps), j’arrive à garder seulement 4 600 chemins intéressants.
J’ai donc pu ramener le problème à 2 étapes :
- Sélectionner un ensemble de chemins parmi ces 4 600 de sorte que la somme de leurs coûts ne dépasse pas 3 600 ;
- Trouver comment collecter le plus de fichiers possibles sur les chemins sélectionnés.
L’étape 2 se résout en temps polynomial : c’est un problème de flot ! Très proche d’un bipartite matching entre fichiers et chemins, sauf que chaque chemin peut être relié à 10 fichiers maximum au lieu d’un seul.
Pour l’étape 1, j’ai essayé plusieurs approches, notamment un algo génétique, mais j’ai obtenu les meilleurs résultats avec un semi greedy un peu randomisé : à chaque étape je prends l’un des chemins qui a le meilleur ratio augmentation du flot / coût, et je supprime les chemins précédemment sélectionnés dont les fichiers sont un sous-ensemble des fichiers du chemin que j’ajoute (ils peuvent être ajoutés à nouveau plus tard).
Un algorithme Greedy (glouton) est un algo qui construit une solution approximative en prenant à chaque étape ce qui améliore directement le plus.
- Pour découvrir les algorithmes de flot et le bipartite matching, reportez-vous sur Wikipédia
Le tips de Gaëtan
Le juge donne des indications lorsqu’une solution effectue des opérations invalides, certains n’ont soumis que des solutions valides et n’ont pas vu cette aide !
Bravo à tous ceux qui ont participé pour le plaisir, le fun et le partage, et merci à tous ceux qui sont venus discuter des problèmes sur les réseaux sociaux et autres : j’ai adoré soulever le rideau et montrer l’envers du décor à ceux que j’ai pu ainsi rencontrer. J’ai hâte d’organiser la prochaine saison de l’événement et de vous retrouver. Bon code à tous et à toutes !
Pas encore de commentaires