Ghost in the cell

La semaine dernière, j’étais plutôt pris par un … un contest codingame !

Malheureusement, j’ai un peu la flemme de faire le post-mortem avec Asciidoc pour ne pas avoir les images générées par PlantUML.

Donc je vais plutôt en faire une version raccourcie ici.

Qu’est-ce qu’il faut faire ?

Sur un terrain constitué d’un graphe de noeuds produisant des robots, il faut avoir plus de robots à la fin de la partie que l’adversaire.

Mais comment ?

A chaque tour, vous pouvez demander à chacun de vos noeuds d’envoyer autant de cyborgs que vous le voulez vers la destination de votre choix.

Oui, mais comment ?

Là, ça devient compliqué.

J’ai implémenté au début un système qui envoyait les cyborgs vers le noeud ennemi le plus proche (en en envoyant plus que ce qu’a l’ennemi au moment où j’arrive). Mais ça ne marchait pas trop bien. Même si ça m’a emmené jusqu’en bronze.

J’ai ensuite amélioré d’innombrables fois ce système en tentant les choses suivants

  • Envoyer les bombes vers les noeuds ennemis
  • Faire des upgrades des noeuds que je détiens (malin, parce que tout un tas d’ennemis envoient 2 cyborgs à chaque tour, en comptant sur les statistiques) … Ca m’a emmené en argent.
  • Implémenter un peu de solidarité en essayant d’équilibrer le nombre de cyborgs entre les noeuds. Ca a plutôt bien marché … mais je n’ai pas franchi l’argent
  • Et le dernier : trier les noeuds au début de chaque tour par distance au centre des noeuds de mon équipe. Et utiliser ce tri pour chacune des opérations précédentes. Et ça m’a emmené en or.

Résultat ?

683ème.

Pas forcément un mauvais score.

Mais nettement moins bon que mon collègue Nicolas, qui termine 41ème en Legend ! Et que je félicite.

Mais il y a des trucs qui n’ont pas marché ?

Tellement !

La plus grosse déception a été pour moi la tentative d’utiliser l’algorithme dynamique de résolution du problème du sac à dos, qui ne donnait pas vraiment de différence de score de mon algorithme naïf et brutal.

A côté de ça, j’aurais peut-être dû aussi tenter des algorithmes plus … intelligents.

Et des leçons à en tirer ?

Je connaissais bien Bomberman, donc j’ai pu utiliser un peu d’expertise pour sentir les bons algorithmes dans Hypersonic.

Par contre, là, les graphes, je n’y connais rien. Enfin, si, en terme d’algorithmique, de navigation, je m’y connais … un peu. Par contre, ce genre de jeux, vraiment, je n’y connais rien, et je suis nul. Et je sais pourquoi : on est là dans le même genre de problème que pour le go : c’est un jeu distribué sans valeur autre que positionnelle. En effet, un noeud vaut plus par le nombre de cyborgs qu’il produit que par toute autre valeur ou information.

Et du coup, c’est très difficile à appréhender pour l’esprit humain qui est fondamentalement focalisé sur un objectif, et pas sur une situation globale.

Et ça, c’est une super leçon : il est difficile pour moi de concevoir un algorithme intelligent si je ne connais pas vraiment bien l’espace du problème.

Oh, bien sûr, j’ai atteint une position au moins aussi bonne qu’à hypersonic. Mais quelque part, et même si j’étais hier extrêmement content d’atteindre l’or, j’ai quand même une petite pointe de déception de ne pas avoir fait un meilleur score (qui aurait pu être Legend, mais c’est ma prétention habituelle).

Génération de mots de passe

Bon, aujourd’hui, je voulais vous parler initialement de Npackd, ou de minidlna, mais finalement, je vais vous parler de XKCD.
Et plus particulièrement de ce dessin :

 

Password_strength

 

Ce qui est intéressant avec internet, et plus spécifiquement avec XKCD et d’autres comics du genre, c’est que les mecs ont tellement de sens pratique que leurs délires peuvent devenir réalité.
Ainsi, LifeHacker m’apprend aujourd’hui que ce que l’auteur a rêvé existe maintenant sous forme d’une application web. Sympa. Mais j’aimerais encore mieux avoir un générateur de mot de passe dans Keepass. La grande question, c’est évidement « est-ce possible ? ».
Eh bien pas si facilement : les générateurs de Keepass sont limités et, par nature, choisissent des lettres aléatoires, et non des mots aléatoires. Bon, cela dit, faut encore que je regarde en détail la doc de Keepass, parce qu’il y a peut-être une option. D’un autre coté, les sites limitent souvent les mots de passe à dix caractères (ou vingt), ce qui est ennuyeux. Bon, je fouille, et je vous dis quoi, d’accord ?

Le jeu ultime : faire des maths …

Je vais pas faire mon Fred Cavazza (avec sa rubrique coup de coeur du web), mais je suis tombé hier sur un site qui m'a fait perdre un peu de temps, et m'a beaucoup plu (à défaut de m'amuser).
Ce site, c'est Khan Academy, découvert grâce à Quantified Self.
Sur ce site, on fait de petits exercices de maths, on est récompensé par des badges divers et variés, et on avance dans les différentes disciplines mathématiques.
Les badges et leur affichage en haut de page m'ont un peu fait penser à StackOverflow, même si le propos, ici, est tout autre : faire en sorte que les gens apprennent des maths.
Et c'est vraiment bien fichu, comme le montre la page de mon profil … ah, super dommage, elle n'est pas accessible. Bon, un petit bug report, et voilà. Maintenant, il n'y a plus qu'à attendre une version francisée, et les enfants vont pouvoir se lâcher comme des fous.

Vite fait

Bon, je crois que je vais me calmer un peu sur les problèmes d’Euler, parce que le problème 29 a vraiment été trivial à résoudre (et voilà que me revient le vocabulaire typique des prépas).

 

 

Pour le coup, je peux vraiment dire merci aux extensions mathématiques que Groovy amené à Java, et en particulier à la méthode pow, qui me retourne un BigDecimal que je retransforme aussi sec en BigInteger, parce que je sais ce que je veux 🙂
Cela dit, me voilà maintenant niveau 1, ce qui ne change rien à ma vie 🙂 mais me vaut les félicitations d’un ordinateur, quelque part dans le monde :

 

Bravo, Riduidel! Now that you have solved 25 problems you have achieved what 79.94% of members have failed to do and have advanced to level 1. Good luck as you continue.

Fibonacci, c’est trop facile

Les problèmes de fibonacci, c’est un peu comme les permutations : en Groovy, avec les BigInteger, les collections, et les bibliothèques dont on dispose, c’est un peu de la tarte à coder ! Du coup, le problème 25 ne me prend pas plus de 10 minutes à résoudre ! Enfin, 10 minutes de conception, et 1.57 s. d’exécution !

 

 

 

Et du coup, il ne me reste plus qu’un problème à résoudre avant de passer « niveau 1 » !

Vive les permutations !

Ca faisait quand même un moment que je mangeais du nombre premier (pas toujours avec succès, d’ailleurs, comme pour le problème 12 qui me résiste encore). Et là, le problème 24 me fait voyager au pays des permutations d’un ensemble.
Je me souviens de mes cours de maths de prépa, où on a démontré que toute permutation d’un ensemble peut se décomposer en un ensemble de transpositions. Et du coup, j’avais commencé à écrire un truc qui le faisait à la main … Jusqu’à ce que je me rende compte que Groovy incluait une fonctionnalité de calcul de toutes les permutations d’un ensemble ! Ce qui a largement simplifié mon code 😉

 

 

Du coup, le code ne fait quasiment plus rien, mis à part appeler la bonne méthode avec les bons arguments et afficher joliment le résultat. Bon, ma méthode a quand même l’inconvénient notable de consommer environ 500 Mo de RAM pendant 1 minute … Ce qui m’intrigue un peu, je dois dire, même si je bâtis une collection de quelques millions de chaînes de caractères … Boarf, mettons ça sur le dos du Groovy 😉

Eratosthène à la rescousse

Vous connaissez pas Eratosthéne ? Bon, je connaissais son crible de nom. Mais là, pour la première fois, je l’ai utilisé dans du code Grooy pour optimiser trés violemment une recherche de nombre premiers. Ce qui m’aide énormément pour ce fichu problème 10.

 

 

Là, en fait, les feintes, c’est
  1. Demander à Eratosthéne de supprimer les nombres non premiers de mon tableau (ce qui va plus vite que de voir pour chaque nombre quels sont ses diviseurs)
  2. Utiliser un BigInteger pour la somme qui sera plus grande que Integer.MAX_VALUE.

Yes !

Le problème 14 et ses séquences de Collatz me résistait depuis un moment. Heureusement, j’ai enfin trouvé la solution :

 

 

Il y a encore une fois des magouilles de transformations en BigInteger, et une durée d’exécution effarante de 3944 s. (le tout avec, en bonus, un Xmx passé en option pour pouvoir contenir tous ces nombres). Mais là, pour le coup, je suis juste content d’avoir une solution, même trop lentement ! D’ailleurs, pour le coup, je me demande si il ne valait pas mieux passer par une solution en Java.