Un algorithme pour trouver Charlie le plus rapidement possible

Antoine Oury - 20.02.2015

Zone 51 - Insolite - Où est Charlie ? Waldo - algorithme découverte - Randy Olson Computer Science


La question a taraudé des milliers d'enfants depuis 1987, et quelques adultes : Où est Charlie ? Le personnage rayé de blanc et de rouge a fatigué pas mal d'yeux, mais un étudiant américain assure avoir trouvé un moyen infaillible pour débusquer la silhouette filiforme dans la foule, en moins de 10 secondes.

 

 

Le chemin optimal pour trouver Charlie, selon Randal Olson

 

 

Le week-end de Randal Olson, étudiant en sciences informatiques, s'annonçait ralenti par d'importantes chutes de neige : ni une, ni deux, il a décidé de se pencher sur un vieux projet. En novembre 2013, le journaliste Ben Blatt révélait dans Slate une méthode qu'il jugeait infaillible pour trouver Charlie, le plus rapidement possible. En gros, Blatt procédait par bande, en scrutant les doubles pages de gauche à droite, et en ignorant volontairement les bords et le milieu des dessins, où Charlie ne se trouve jamais.

 

Olson avait une tout autre théorie, et estimait que la solution de Slate était loin d'être optimale : il salue néanmoins la recension des 68 endroits où se trouvait Charlie dans les 7 livres signés par Martin Handford, réalisée par le journal. À partir de ces données, Olson a réalisé une estimation par noyau, permettant d'analyser une densité de probabilité. Celle de trouver Charlie à tel ou tel endroit de la page.

 

Il ne restait « plus qu'à » déterminer le moyen le plus simple et rapide de parcourir les 68 points où Charlie pouvait se trouver sur la double page : « Simple, non ? Pas du tout. Ces 68 points peuvent être reliés selon environ 2.48 x 1096 manières différentes, soit plus que le nombre d'atomes dans l'univers », souligne avec esprit Olson. 

 

L'étudiant aura donc préféré un algorithme génétique, qui recherche, à la place d'une solution exacte, une solution optimale. En suivant grossièrement le chemin proposé par l'algorithme, Olson assure que Charlie est trouvé en moins de 10 minutes. Mais l'étudiant souligne également que « [c]omme beaucoup de choses dans l'existence, le plaisir de trouver Charlie relève de la manière de faire, et pas de l'accomplissement ».