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.

Il était temps

Ca faisait un moment que je tournais autour de la suite de Fibonacci du problème 2. Et, cette fois, même si ma solution n’est pas optimale (en particulier dans le calcul du nombre d’éléments de ma suite), j’ai enfin bien compris l’énoncé, ce qui m’a permis d’écrire la solution assez vite.

 

 

Bon, encore une fois, il y a un parcours assez rigolo de mon tableau/liste qui est effectué par un findAll. Ca, c’est le genre de chose qui manque vraiment à Java, mais qui est implémenté dans les collections google, ce qui est une excellente idée (et montre également que Java n’a pas besoin des closures).