Sunday, May 12, 2013

Codingame

Ceci est le post le plus vu de mon ancien blog, comme Google Cache l’a sauvé je pense que ça peut être utile de le remettre ici.

J’ai participé au CodinGame le 29 janvier, voici mon compte rendu.

CodinGame est un concours de programmation/algo. Avant le concours, plusieurs entreprises s’inscrivent, et les candidats peuvent postuler dans plusieurs d’entre elles. Le concours a lieu à la même heure pour tout le monde et est constitué de trois problèmes à résoudre. À la fin, un classement est établi en fonction du nombre de testcases passés puis du temps requis pour trouver et coder la solution. Les boites reçoivent les résultats et peuvent demander à vous contacter (pour le moment, tout est anonyme). À vous de les autoriser à vous contacter directement, puis à vous le stage/job sans devoir passer par la case contact avec d’anciens élèves de la promo.

Du coup, le principe est cool. Si vous vous plantez, vous restez anonyme et personne ne le saura jamais. Donc aucune excuse pour ne pas tenter l’aventure. Pour couronner le tout, les gagnants peuvent recevoir des lots (la dernière fois 5 nexus 7, cette fois 10 RaspberryPi complet (i.e. avec les accessoires)). Et cerise sur le gâteau l’équipe derrière l’organisation est super cool. Il y avait eu une annonce sur linuxfr, où un membre de l’équipe avait rapidement répondu aux divers commentaires. La dernière fois je les avais contactés par mail pour avoir des précisions sur un testcase et j’ai eu ma réponse dans l’heure. Finalement, les suggestions proposées lors du dernier CodinGame ont été prises en compte. (publication des sources des gagnants sous GPLv3 pour pouvoir regarder les codes gagnant dès la fin du concours, un chan IRC pour pouvoir troller sur les pauvres Pythonistes qui ramaient sur le concours)

Bref, j’avais participé lors du dernier concours, et trouvé ça super. Donc j’étais motivé pour la prochaine édition (j’étais le candidat 34 sur 1267, donc inscrit dès la parution de l’annonce). Problème, cette édition a lieu le mardi à 20 h et j’ai cours de Russe de 18 à 20. J’épluche le règlement, on dispose de 15min après l’heure de départ pour commencer. 15 min pour rentrer chez moi, c’est impossible en transport.J’ai testé avec un vélo c’est jouable, mais il ne faut pas avoir peur de se faire renverser. Heureusement, sur le campus il y a une salle info. Bon elle est à 10 min de ma salle de cours, mais c’est raisonnable. Je l’utiliserai donc.

Mardi 29 janvier 17h40: Je suis en salle info, je vérifie que tous les outils vitaux sont installés: Emacs check, g++ check. Je prépare mon dossier pour coder, lock ma session et go en cours. À 20 h pour une fois je suis le premier à sortir, je traverse le campus en courant, arrive en salle info. Elle est vide et heureusement personne ne s’est amusé à me déloguer. J’ouvre mes mails clique sur le lien, ouf c’est bon je suis dans les temps.

Premier exo: encoder une chaine de caractère ASCII en unaire. Ça commence bien, je n’ai aucune idée de comment convertir un char en son int ASCII associé. Je regarde sur c++reference une hypothétique fonction toascii, mais bon Google est mon ami. Ok je comprends que caster en int comme un bourrin fait ce que je veux. Aller c’est parti. J’écris une fonction qui transforme un char en la chaine de 01 associée puis une fonction qui converti une chaine de 01 en l’équivalent unaire. Je teste, ça ne marche pas. Je relis l’énoncé, on veut convertir un message en unaire, pas convertir lettre par lettre en unaire. Du coup effectivement la fin d’un caractère peut s’encoder avec le début du caractère suivant. Ça m’apprendra à lire l’énoncé. Je corrige mon code. Je teste sur les exemples fournis, fait quelques tests supplémentaires en local (il faudra que je creuse pour ajouter mes propres tests dans l’IDE) ok c’est bon je soumets ma solution.

Deuxième exo: Organiser des calculs sur un superordinateur pour maximiser le nombre de calculs fait. Les contraintes étant que chaque calcul doit avoir lieu précisément sur une plage de temps définie. Cette fois je lis, je relis et relis l’énoncé. Pas question de coder un truc qui répond à une autre question. Je regarde les exemples fournis. En particulier, on n’a pas le droit d’avoir un calcul finissant le 7 et un commençant le 7. Et attention un calcul qui commence le 2 et dure 5 jours fini le 6. Vu le nombre de calculs il faut un algo en O(nlg(n)). En gros, on peut trier. La première idée, trier par durée de calcul ne marche pas vu que les périodes de calculs sont fixes. En fait il faut trier par date de fin, puis dans cet ordre si c’est possible de faire le calcul, on le fait sinon on le jette. En effet, au moment de considérer le ième calcul vu que tous ceux qu’on va regarder après terminent plus tard. On est sûr que le ième est bien celui qui nous posera le moins de problèmes par la suite donc il n’y a pas de risque à le prendre dans une meilleure solution. En revanche, j’ai dû me battre avec le compilateur de l’IDE en ligne. Pour lui les paramètres de la fonction de comparaison utilisée lors du tri doivent être constants sinon il ne compile pas. En local aucun problème que ce soit avec g++ ou avec clang++. Et pourtant j’active tous les warnings possibles. Je comprends bien qu’effectivement ils doivent l’être, mais pourquoi mon compilo ne me pose pas de problèmes ?

Troisième exo: Décoder un message en morse en utilisant le dictionnaire fourni. Celui-là était chaud d’après les stats officielles 0,36% de réussite pour cet exo. Effectivement si on ne fait pas attention l’algorithme est trop lent et ne valide pas les gros tests. Et ce qui peut être fourbe les mots du dictionnaire sont différent, mais le code morse associé peut être le même. Il y a en fait deux difficultés, on ne sait pas ou une lettre s’arrête “…” peut être “EE” ou “I” et même une fois ce problème résolu, on ne sait pas où les mots se terminent. Du coup la première étape est de convertir le dictionnaire fourni en dictionnaire morse, puis de cherche le nombre de messages possible en décodant avec ce dictionnaire sans s’occuper du fait que le message est en morse. Ensuite mon algo est assez simple dans l’idée. Je lis le message s(0,n) et si s(0,i) est un mot du dictionnaire j’ajoute le nombre de décodages possible de s(i+1,n). Sauf que je suis malin, pour ne pas exploser la complexité j’ai un tableau qui se souvient du nombre de messages de s(i+1,n). Si ce tableau contient une valeur banzai ! Sinon j’effectue le calcul (ie j’applique ma fonction à s(i+1,n)) est marque le résultat dans mon tableau. Bon aussitôt dit, aussitôt codé, aucun problème sur les 3 premiers exemples, mais aucun résultat sur le dernier. Il va falloir débuger. En affichant le debug que me rend compte que je ne gère pas le cas où plusieurs mots ont le même code morse. Pas de problème, j’ajoute multi devant mon set et adapte mon code. Mais cela ne fonctionne toujours pas. En affichant une trace d’exécution c’est la catastrophe mon algo trouve le premier mot, mais rien pour continuer le message. Là j’ai badé, j’ai lu et relu mon code impossible de comprendre cette erreur. Je commence à faire des modifs un peu au hasard (conseil, dans ce genre de situation faite une sauvegarde de votre code avant pour pouvoir facilement revenir dans un état ou le code est compréhensible). Finalement je comprends mon erreur. Le code morse de C n’est pas “_.-.” mais “-.-.”. Sur mon clavier “-_” sont sur la même touche et il faut un MAJ pour faire le point. Du coup en tapant vite c’est l’erreur de base, et dans un océan de “_…” c’est vraiment très dur à voir.

Voilà, j’ai soumis mes trois problèmes. Le petit moment de stress pendant que mes programmes sont testés. D’après le scoreboard personne n’a encore fait 100%, si mes codes sont bons je prends la première place. Sinon il y a encore pas mal de chance d’être bien classé, mais ça veut dire stresser jusqu’à la fin pour être sûr. C’est long, objectivement le résultat est donné en une minute, mais c’est une longue minute. Je suis assez content de moi, sans cette erreur du _- tout c’est vraiment bien passé. Voilà les résultats sont là: Blabla404 100%. Je vais faire un tour sur le chat IRC, mais j’ai trop peur de spoiler des indications (j’étais tellement fier de moi en voyant ce problème du multiset de l’exo trois) du coup je quitte assez vite. Une bière pour fêter ça, et bientôt ma framboise aura une amie. C’est génial, j’étais en train d’hésiter pour en prendre une autre (pour faire des tests sans impacter la disponibilité de mon site, pour tester des trucs en réseau toussa et je n’aurai même pas besoin de le commander.)

No comments:

Post a Comment