Panneau cellulaire et automate publicitaire

Je me baladais tranquillement dans la jungle de Reddit comme l'aventurier solitaire, m'acquittant de ma mission de Redditeur lambda. C'est en bas-votant courageusement les posts de pancartes politiques de r/pics, puis en commentant "rip your inbox" sous une publication d'un individu femelle que je suis tombé sur un contenu tout à fait étranger à mon flux habituel. Tel Indiana Jones qui soulève doucement la statuette inca-maya-soudano-pakistanaise bizarre, j'ai cliqué sur le post pour relever le défi qui me narguait (mais ma maison ne s'est pas écroulée sur ma gueule, la métaphore s'arrête là).

Fun Programming Puzzle
Je conduisais pour rentrer chez moi quand j'ai vu ce panneau publicitaire qui fait la pub d'un puzzle de programmation. On peut le trouver ici: https://www.mx.com/billboard2019/puzzle. Je l'ai résolu en une trentaine de minutes.
Je me suis dit que certains d'entre vous pourraient être intéressés !

https://www.reddit.com/r/LiveOverflow/comments/k8xvma/fun_programming_puzzle/

N'ayant jamais fait de puzzles de programmation, je me suis dit que c'était une bonne idée de tenter, et j'ai beaucoup aimé le réaliser !! Je vous conseille d'essayer de le faire, ce n'est pas trop dur, et si vous êtes bloqués vous pouvez revenir ici pour avoir des indices !

Sans plus d'introduction, le site nous présente deux GIFs:

Les GIFs étant ce qu'ils sont, ils peuvent ne se jouer qu'une fois dans le navigateur. Rafraîchir la page avec CTRL+F5 permet de rejouer le GIF. Ce qui est important de retenir c'est que les lignes s'affichent une par une, de haut en bas.

On a donc des labyrinthes zébrés qui se remplissent, avec des lettres et des chiffres en dessous, et une barre rouge. Youpi ! Notre but est de démêler toute cette logique et de retrouver pour n'importe quel labyrinthe zébré le résultat (7 dans le premier GIF, 53 dans le deuxième GIF).

La première chose que l'on remarque est que le résultat change tout au long du GIF: plus les lignes descendent et plus le résultat augmente, quoique pas à chaque fois. En gardant ça en tête, on va d'abord s'attaquer à nos lettres mystérieuses qui permettent sûrement de reproduire le labyrinthe-zèbre. Le fait d'avoir deux images permet de déterminer facilement ce qu'elles signifient ! Essayez sans tricher de retrouver la signification des lettres.

...

...

...

C'EST BON ?!?

Voici la correction tant attendue:

On peut remarquer que la zone rouge à l'air plutôt importante puisque la plupart des paramètres permettent de la situer. En revanche, je m'attendais à avoir des informations sur la génération des carrés noirs, mais que nenni. Le plus simple pour faire nos expérimentations est de prendre notre langage interprété favori, et de reproduire le début du labyrinthe-zèbre avec les paramètres qu'on a maintenant déterminé. Je vais utiliser Python et la librairie pygame pour se faire.

Commençons par déclarer nos constantes et créons la grille de jeu:

G = 8
X = 2
Y = 3
S = 5

SIZE = 500 # GUI size
grid = [[0 for i in range(G)] for i in range(G)]              

On va faire un tableau à deux dimensions pour représenter la grille de jeu, où chaque case a une valeur de 0 si elle est vide, sinon une valeur de 1. Simple, non ? Maintenant on peut s'occuper d'afficher ça à l'écran.

def draw_grid():
    """Dessin de la grille de jeu"""

    # grille
    for i in range(0, G):
        coord = i * SIZE / G
        pygame.draw.line(screen, BLACK, [coord, 0], [coord, SIZE])
        pygame.draw.line(screen, BLACK, [0, coord], [SIZE, coord])

    # zone rouge
    for i in range(S+1):
        cell = SIZE / G
        pygame.draw.line(screen, RED, [(X-1)*cell, (Y+i-1)*cell], [X*cell, (Y+i-1)*cell], 3)

    pygame.draw.line(screen, RED, [(X-1)*cell, (Y-1)*cell], [(X-1)*cell, (Y-1+S)*cell], 3)
    pygame.draw.line(screen, RED, [X*cell, (Y-1)*cell], [X*cell, (Y-1+S)*cell], 3)
        
def draw_cells():
    """Dessin des cases remplies"""

    for i in range(G):
        for j in range(G):
            if grid[j][i] == 1:
                pygame.draw.rect(screen, GREEN, [SIZE / G * i, SIZE / G * j, SIZE / G, SIZE / G])

On va ainsi dessiner en vert les cases remplies, pour donner un peu de couleur à notre zèbre. Regardons ce que ça donne.

Vous aurez remarqué que j'ai dessiné une première case remplie en haut à gauche: en effet, dans nos deux labyrinthes-zèbres on commence par celle-ci. Mon idée est qu'à partir de cette case, on peut générer les autres cases restantes. Malheureusement, nous n'avons pas de paramètre restant pour nous indiquer comment faire cette génération !

Et nous n'avons pas non plus résolu le plus gros problème: comment est calculé le résultat ? Regardez à nouveau le premier GIF en détail. Le résultat augmente avec la troisième ligne, la quatrième ligne, puis la cinquième ligne. Après, il ne change plus de sa valeur, 7. Et il y a aussi cette histoire de zone rouge, qui sert forcément à quelque chose d'important, comme on l'a dit plus haut.

En fait, il semblerait que quand une case de la zone rouge se remplit, le score augmente ! On peut vérifier cette hypothèse grâce au deuxième GIF. Mais alors, quelle opération est appliquée pour calculer ce résultat ?!? Au début, je pensais que les autres cases remplies de la ligne influaient sur le résultat. Un truc du genre:

resultat = 0
POUR chaque ligne:
    SI case remplie dans la zone rouge
        resultat += nombre de cases remplies dans la ligne
    FINSI
FINPOUR

Mais on peut vite se rendre compte que ce genre d'algorithme ne colle pas avec les deux GIFs: il semble que le score soit entièrement déterminé par les cases remplies présentes dans la zone rouge. En particulier, si on regarde la zone rouge du deuxième GIF, on s'aperçoit que plus la case remplie est dans une ligne du bas, et plus le résultat augmente. Allez, on se refait un petit tableau pour y voir plus clair ?

Bon là ça devrait vous sauter au yeux, surtout avec les deux colonnes du milieu ! La zone rouge représente en fait un nombre binaire, avec le bit de poids fort à la fin ! Autrement dit, on compte en puissance de 2: la valeur d'une case est deux élevé à la puissance de la ligne de la zone rouge. Voici un petit récap:

En faisant la somme de toutes les puissances correspondantes aux cases remplies, on obtient bien le 53 escompté !

Sauf qu'on a toujours un problème de taille: comment générer ce motif satanique ?? Si on regarde les deux GIFs, on peut voir surtout au début que les lignes se ressemblent. Mais après ça part un peu dans tous les sens. Si on se fie au GIF, on peut déjà comprendre que chaque ligne permet de créer la suivante, puisqu'elles arrivent les unes après les autres.

MAIS OUI, bon sang, c'est un AUTOMATE CELLULAIRE !! Mais si, vous connaissez sûrement le plus célèbre d'entre eux: le jeu de la vie (cette recherche Google lance un jeu de la vie en haut à droite de la page !).

En fait, on dispose d'une grille où les cases sont appelées des cellules. Dans le cas du jeu de la vie, les règles sont les suivantes:

• Une cellule est déterminée par l'état de ses 8 voisines.
• On distingue une cellule morte (case vide) d'une cellule vivante (case remplie)
• Si à une cellule à trois voisines vivantes, elle sera vivante à l'étape d'après.
• Si une cellule à deux voisines vivantes, elle ne change pas d'état à la prochaine étape.
• Si une cellule à moins de deux ou plus de trois voisines, elle meurt à l'étape suivante.

Alors ça peut paraître assez bizarre comme ensemble de règles, mais le jeu de la vie est Turing-complet, ce qui veut dire que vous pouvez y faire autant de conneries qu'en utilisant un langage de programmation normal. Rien ne vous empêche donc de programmer Fortnite 2 et la triple danse du dab big chungus juste avec des petites cellules du jeu de la vie. Mais on va quand même éviter hein.

A moins que ... 😳

Revenons à nos zèbres ! On a de la chance, notre automate cellulaire est bien moins compliqué que le jeu de la vie: en effet, c'est seulement la ligne précédente qui peut influencer la suivante. En effet nous avons affaire à un automate cellulaire 1D ou autrement dit à un automate cellulaire élémentaire !

On va donc pouvoir s'aider de la page Wikipédia des familles pour comprendre de quoi il en ressort (toujours prendre les pages en anglais, elles sont plus fournies):

https://en.wikipedia.org/wiki/Elementary_cellular_automaton#The_numbering_system

Il y a 8 = 2³ configurations possibles pour une cellule et ses deux voisins immédiats.Pour que l'automate cellulaire fonctionne, il faut savoir l'état d'un cellule pour chaqu'une des possibilités, ce qui donne 256 = 2²³ automates cellulaires élémentaires différents. Stephen Wolfram à proposé un schéma appelé le code Wolfram, qui permet d'associer à chaque règle un nombre de 0 à 255, et qui est devenu un standard.

On peut reprendre les conventions du code de Wolfram pour représenter les différentes règles de notre automate cellulaire. Voyons voir comment ça marche de façon un peu plus concrète. On va créer un ensemble de règles un peu au hasard, qui selon les cellules précédentes va donner l'état de la cellule suivante.

Comme on le remarque, c'est seulement les trois cellules précédentes qui influencent la cellule suivante. Dans notre exemple, si les deux diagonales de notre cellule sont pleines mais que la cellule du dessus est vide, on dit que la cellule est pleine. Autrement dit, en utilisant des 0 ou des 1 pour représenter les cases vides et pleines, on a

101 -> 1

Il faut donc faire ça pour toutes les combinaisons possibles de cases précédentes. Je vais encore choisir des règles au hasard, que l'on va résumer avec un tableau:

Notre ami Wolfram (qui est entre autre le créateur de Wolfram Alpha, et qui à son insu a résolu pas mal de mes exos de maths) nous propose un nom à l'ensemble de règles que l'on vient de créer avec le tableau précédent. On lit le nombre en binaire qui correspond au nouvel état de la cellule: 01101110, remis en décimal, 110. Nous voilà donc avec la règle de code Wolfram 110 !

Écrivons un morceau de code pour modéliser ceci. Pourquoi ne pas utiliser un peu d'arithmétique booléenne pour le fun ??

LEFT = 0b100
MIDDLE = 0b010
RIGHT = 0b001
NOTHING = 0

Ainsi, en faisant LEFT | RIGHT pour indiquer qu'une cellule à ses diagonales remplies, on va avoir une valeur de 100 | 001 = 101. Pile ce qu'on attend. Et pour savoir si la cellule prochaine doit être remplie ou non ?

def next_cell_state(rule, flags):
    """Finds the state of the next cell"""
    return (rule >> flags) & 1

Plutôt élégant et intriguant comme ça, non ? Décortiquons un peu ce code. Supposons qu'on fait un appel next_cell_state(110, LEFT | RIGHT). Que ce passe-t-il ?

Tout d'abord, on décale vers la droite le schéma d'autant de fois que le code utilisé pour les voisins ( LEFT | RIGHT soit 101 ou encore 5 en décimal). Puis on récupère le dernier bit, qui sera la valeur de la nouvelle cellule.

On sait donc ainsi que la nouvelle cellule doit être remplie dans notre cas précis ! Mettons tout ça en application et tentons d'afficher la règle 50, par exemple. Voici comment on peut s'y prendre pour calculer sur une ligne si les cellules doivent être vivantes ou mortes:

line = 0
grid[0][0] = 1
rule = 50

for col in range(G):
    flags = NOTHING

	if col > 0 and grid[line][col - 1] == 1:
		flags |= LEFT
    if col < G - 1 and grid[line][col + 1] == 1:
		flags |= RIGHT
	if grid[line][col] == 1:
		flags |= CURRENT

	grid[line + 1][col] = next_cell_state(rule, flags)

line += 1

Ce qui donne:

Il ne nous reste plus qu'à trouver quel règle utilise notre énigme. Reprenons le tableau d'avant et remplissons-le en regardant les deux GIFs qu'on nous a donné:

Ce qui nous donne un code Wolfram de 01100101, ou 101 en décimal. Testons maintenant celui-ci dans notre merveilleux programme !

Victoire !! C'est exactement le même motif que dans le premier GIF (si, si, vous pouvez vérifier !). On obtient un résultat similaire avec le deuxième GIF. On peut maintenant répondre à l'énigme.

{ g⇒32, x⇒12, y⇒21, s⇒7 } = ?
{ g⇒64, x⇒34, y⇒45, s⇒9 } = ?
{ g⇒128, x⇒81, y⇒100, s⇒14 } = ? 
{ g⇒1024, x⇒32, y⇒920, s⇒42 } = ?

On doit juste avant créer la fonction qui va nous calculer le résultat:

def get_score():
    score = 0
    for i in range(S):
        score += grid[Y + i - 1][X - 1] * 2 ** i

    return score

Il s'agit simplement de mettre à la puissance de deux comme on l'a fait précédemment. Voyons voir ce que ça donne pour g=64 !

Le damier devient tout petit mais l'idée est là ! Et encore if faut voir pour g = 1024:

On ne voit carrément plus rien :D

Je dois avouer que le dernier a pris un peu de temps à se calculer, mon implémentation Python est faite à la va vite et les questions sont de complexité quadratique (à chaque fois on augmente les dimensions x et y de la grille). Une bonne dizaine de minutes plus tard, j'avais la dernière solution, qui de mémoire ressemblait de près ou de loin à

45236456315275467356734564356

(J'ai tapé au pif mais vous avez une idée de l'ordre de grandeur)

En validant ça, vous aurez un petit message de félicitations ! Une deuxième partie d'énigme est aussi disponible, avec cette fois des automates cellulaires basés sur le jeu de la vie. Pour cette deuxième partie aucune connaissance en programmation ne semble être requise, il faut juste placer des petites cellules pour faire des machines du jeu de la vie. Ne connaissant pas bien les règles, je laisse cette dernière tâche en exercice au lecteur ®.

Note: on peut aller BEAUCOUP plus vite à la solution. la GUI est sympa pour visualiser mais n'apporte rien en soi. J'ai aussi préféré m'attarder sur les concepts des automates cellulaires parce que je trouve ça stylé sa mère. Mais pas besoin de connaître le code Wolfram pour comprendre qu'ici une cellule est déterminée par ses trois voisines précédentes. D'une manière plus générale, la plupart des articles que je propose sur ce blog sont des prétextes permettant d'explorer des concepts que je trouve dignes d’intérêt.