Google hashcode 2022

Jeudi soir, j’ai participé avec mon équipe au Google hashcode 2022. Retour sur ce concours un peu particulier qui regroupe plus de 30000 personnes autour du monde, toutes avec le même objectif : trouver la meilleure solution algorithmique à un problème en 4 heures.

Le Google hashcode est un concours organisé par Google chaque année. Elle a lieu au mois de février par équipe (de 2 à 4 participants). Mais qu’est-ce qu’un concours de programmation ?

Le principe est simple : étant donné un problème de la vie de tous les jours, développer un programme qui donne la solution la plus optimisée possible. La solution parfaite n’existe pas, il faut s’en rapprocher au maximum. Ce qui nous attire dans cet exercice est le côté « travail en équipe » et le fait de réfléchir à un problème réel plutôt qu’à un exercice d’algorithmie pure.

Le concours vous fournit des fichiers de données en entrée qui correspondent à différents scénarios puis charge à la solution, documentée de son code source, de soumettre une réponse pour chaque fichier.

Quelques exemples de problèmes :

• Comment scanner efficacement tous les livres de toutes les bibliothèques dans le monde ?
• Comment gérer un trafic routier en pilotant les feux rouges ?
• Comment classer des photos pour générer automatiquement des diaporamas intéressants ?

Je suis accompagné de Joël, Florian et Cyril et nous formons l’équipe CURB Code (ne cherchez pas un sens à ce nom, il n’y en a pas 😅). C’est la 4ᵉ année que nous participons ensemble à ce concours, l’occasion de se retrouver, de passer un bon moment ensemble et de mettre nos neurones à l’épreuve. Nous avions terminé en 2128ᵉ place l’année dernière, insatisfait de notre solution (et respectivement 1956ᵉ en 2020 et 1383ᵉ en 2019).

Nous avons travaillé dans le passé ensemble et nous nous connaissons. Je trouve que nous nous complétons bien, les échanges et réflexions en sont donc plus efficaces.

Cette année, Florian nous avait préparés avec notamment un exercice d’entraînement, des fichiers utilitaires déjà prêts, un repository GitHub pour partager le code pendant la soirée et quelques révisions en Python.

Petit aparté concernant le langage choisi pour faire ce concours : nous avons choisi Python (après avoir testé Java, Ruby et Python les années précédentes) pour sa rapidité d’exécution, le fait que ce soit un langage interprété (pas de perte de temps à la compilation et expérience développeur améliorée) et pour sa facilité d’écriture (nous sommes tombés amoureux des filtres et de la gestion des array/map/dict). La plupart des équipes en finale utilisent du Python/Ruby/C/C++.

L’objectif était clair : « Passer une bonne soirée, mais faire un bon classement ».

Le jour J

Nous nous retrouvons donc vers 18h pour vérifier une dernière fois que tout est prêt, commencer l’apéritif et attendre que le problème soit dévoilé.

Le problème

18h45 – Google révèle le sujet du jour : l’affectation de développeurs à des projets selon leurs compétences…

Je vais essayer de vous résumer le problème en quelques lignes, pour que vous sachiez à quoi vous attendre si vous voulez participer. Si vous êtes intéressé pour lire le problème complet, c’est encore possible sur le site de Google.

Nous avons en premier paramètre une liste de Contributeurs ayant une ou plusieurs compétences dans des domaines différents. Par exemple, Anna a une compétence de niveau 3 en HTML et 2 en Python. Bob est expert Java et a donc un niveau 10. Cela pourrait tout à fait représenter les employés d’une ESN.

En second paramètre, une liste de Projets nous est donnée. Chaque Projet requiert des compétences de niveaux différents, rapporte un nombre de points (score) et se déroule sur un nombre de jours incompressible.

Quatre règles à prendre en compte :

• Pour réussir un projet, il faut affecter les contributeurs ayant le bon niveau de compétence aux rôles du projet pendant le nombre de jours de travail.
• Il est possible de faire du mentorat : un Contributeur étant de niveau 3 en Python peut participer à un projet requérant du niveau 4 en Python s’il est mentoré par un pair (participant aussi au projet) de niveau 4 ou plus.
• Chaque Contributeur participant au projet gagne un niveau dans la compétence à laquelle il est affecté.
• Après un certain nombre de jours passés (paramètre pour chaque Projet), un Projet ne vaut plus de point.

L’objectif est donc de trouver la meilleure combinaison de Contributeurs pour faire les Projets dans un ordre qui rapporte le plus de points.

Notre réponse

Nous commençons à avoir une stratégie de départ efficace. 3 personnes lisent le sujet pendant qu’une personne attaque le développement pour lire le fichier d’entrée et écrire la solution dans un fichier de sortie. C’est Florian, chaud bouillant qui démarre le développement aujourd’hui.

Après avoir lu le sujet, nous inversons un peu les rôles. Joël commence à réfléchir à un algorithme de résolution pendant que Cyril et moi développons les objets (classes) qui permettront de comprendre plus facilement notre code. Nous développons donc les classes Contributeur et Projet et les ajoutons au code initial de Florian.

Pendant ce temps-là, Florian finit la lecture du sujet et détecte une erreur dans un exemple de l’énoncé. Nous débattons de cette erreur jusqu’à ce qu’un message s’affiche sur le site de Google, corrigeant l’erreur. Quelques minutes de perdues.

Nous avons maintenant un code qui permet de lire les paramètres en entrée, créer les objets adéquats, mais rien pour proposer une solution.

Joël ayant bien avancé sur l’algorithme général, échange avec Florian et les deux commencent à développer cette première version de solution.

De notre côté, nous développons avec Cyril la fonction team_can_do qui, en fonction du Projet et des Contributeurs passés en paramètres, répond une liste de Contributeurs qui pourraient travailler sur le sujet (ou rien si le projet n’est pas réalisable avec cette équipe). Pas évident, mais nous avons une version fonctionnelle après quelques neurones grillés.

20h15 – La première version de notre code est fonctionnelle (après quelques debugs à coup de print 😅) et nous lançons le programme sur les 6 fichiers d’entrée (nommés A, B, C, D, E et F). Généralement, le premier fichier A est très simple et jouable sur un cahier. Cela permet de vérifier que notre algorithme est correct.

Nous jouons notre programme sur les fichiers restants, mais les fichiers C (projets à 65 contributeurs), E (projets demandant des compétences de haut niveau) et F (demandant beaucoup de mentorat) sont beaucoup trop longs. Nous décidons donc de soumettre les résultats des premiers fichiers et inscrivons nos premiers points (classement à ce moment 1912ᵉ place).

20h45 – Nous cherchons maintenant à faire deux choses :

• implémenter les règles non prises en compte à ce stade (comme le gain de niveau et la possibilité de faire du mentorat)
• optimiser notre algorithme pour à la fois écarter des solutions faibles en points et améliorer les performances

En termes de règles, nous implémentons facilement le gain de niveau. Cela nous permet de réaliser des projets plus importants après quelques jours. Nous gagnons quelques points sur tous les fichiers.

Le mentorat est plus compliqué à développer. Nous resterons sur une première version non optimisée qui couvre uniquement 50% des cas, mais cela nous permet aussi de gagner des points.

D’un point de vue optimisation, nous excluons chaque jour les projets ne valant plus de point via cette très belle ligne :

Nous implémentons aussi un simple test au début de la fonction team_can_do qui vérifie si l’équipe disponible est au moins aussi nombreuse que le nombre de rôles attendus dans le Projet (cela semble évident, mais c’est le genre de règle qu’on oublie quand le temps est compté).

Nous stockons aussi les Projets en cours dans un dictionnaire avec comme clé le jour de fin du Projet. Cela permet de savoir très rapidement quel Projet se termine sur le jour J et surtout, de sauter des jours lorsque aucun Contributeur n’est disponible et que plusieurs projets sont en cours.

21h30 – Le ravitaillement arrive (pizzas 🍕 pour renforcer le cliché du développeur). Et nous repartons à l’assaut de ces projets.

Le classement est maintenant figé, car il ne reste plus qu’une heure de concours ; le temps passe vite. Nous pouvons toujours soumettre nos réponses et notre code, nous voyons le nombre de points, mais sans voir le classement général évoluer.

Avec les optimisations précédentes, nous réussissons à proposer des solutions pour les fichiers C et E, mais le F nous résiste.

21h45 – Florian et Joël reviennent sur notre façon de stocker les Contributeurs (dans une liste). Ils pensent que les stocker dans un dictionnaire (avec comme clé la compétence) serait plus efficace dans les futures recherches. 5 minutes pour échanger sur l’idée, 10 minutes pour la développer et tester. Effectivement, les performances sont améliorées. Heureusement que notre code était « assez bien » structuré, car ce changement de vision aurait pu nous demander beaucoup plus de temps.

Ce type de changement est capital dans ce concours. Le gain de performance permet souvent d’ajouter des règles et de tester plusieurs variables d’ajustement pour obtenir de meilleures solutions.

22h15 – Cyril trouve une astuce pour pouvoir marquer quelques points pour le fichier F (toujours trop long). Il découpe le fichier d’entrée en 2 (supprimant la moitié des projets à faire) et fait tourner notre programme. En quelques minutes, nous obtenons un résultat qui nous fait gagner 450000 points. Une idée de roublard, mais les points sont là.

22h30 – Le chronomètre égrène les quelques secondes restantes et le concours est finalement terminé. La pression retombe et nous faisons des pronostics sur notre place finale. En effet, le classement est révélé environ 1 heure après la fin. Nous pensons être dans les 2000 premières équipes, mais Joël lance un

Je suis sûr qu’on est sous les 1000 !

Joël

22h35 – Dans l’euphorie, je décide de lancer une commande Python qui permet de monitorer l’exécution du programme et de connaître les fonctions les plus gourmandes (en temps et en CPU). La fameuse fonction team_can_do occupe 90% du temps de notre algorithme. Florian et moi repassons sur chaque ligne et trouvons une optimisation très simple : au lieu de gérer les Contributeurs disponibles dans une liste (et donc de faire des if contributor in free_contributors), nous créons une variable is_free sur chaque Contributeur. Notre programme est 5 à 6 fois plus rapide. Nous apprendrons plus tard que cela nous aurait permis de gagner 150000 points (en soumettant le fichier F en entier) et environ 70 places.

Le classement final

23h30 – L’histoire donnera raison à Joël, nous sommes finalement 192ᵉ équipe mondiale 🌍 et 12ᵉ française 🇫🇷 sur plus de 10000 équipes cette année. Retrouvez le classement final ici : Google hashcode Scoreboard 2022.

La finale est encore loin (seules les 40 premières équipes sont sélectionnées) mais nous sommes très fiers du résultat de cette année.

Pour conclure, ce qui nous a réussi n’était pas de trouver la solution optimale, mais de créer un algorithme robuste dès le début puis de gagner quelques points avec des améliorations mineures. Les problèmes du Google hashcode sont toujours créés pour qu’il soit quasiment impossible de brute forcer la solution (tenter toutes les combinaisons). Alors, il faut ruser et faire confiance à son intuition.

Le contexte de ce concours est particulier, que ce soit au niveau du format ou au niveau du temps. Cela nous force à développer et réfléchir différemment de notre quotidien dans des projets de développement classiques. Pas de temps pour la qualité, les conventions de commit ou les tests unitaires 😋

Quelques idées d’amélioration (je suis sûr que Florian est déjà en train d’en tester certaines) :

• implémenter proprement le mentorat
• trier les projets par temps de complétion, score, temps de travail ou poids technique (du plus simple au plus complexe)
• choisir la meilleure équipe (la moins qualifiée ?) pour chaque projet pour laisser libre les meilleurs Contributeurs pour la suite

Si vous avez aussi participé à cette édition, n’hésitez pas à partager votre expérience et laisser un commentaire.

Rendez-vous l’année prochaine 😉