Re: Jour 25

Oui, je suis assez d'accord avec toi au niveau de la difficulté de cette année.

Pour le jour 25, j'ai trouvé une petite astuce qui consiste à encoder la grille sur un entier de 32 bits.

Par exemple, pour la grille

#####
##.##
.#.##
...##
...#.
.....
.....

je vais encoder le nombre de # par colonnes par des séquences de 4 bits.
sous forme de liste, ça donne [1, 2, 0, 4, 3] (je retire 1 à chaque colonne car il y a forcément un # par colonne).
et sous forme d'entiers 0001_0010_0000_0100_0011

De même, pour une grille partant du bas.

.....
...#.
...#.
..##.
.###.
.###.
#####

J'encode par la liste [2, 4, 5, 7, 2] (j'ajoute 2 à chaque colonne pour la somme avec le complément fasse 7).
ce qui donne en binaire 0010_0100_0101_0111_0010

Du coup, si il y a un overlap entre 2 colonnes, la somme des 4 bits les représentant va dépasser 7 et le bit de poids fort va être 1.

Donc pour tester si deux grilles g1 et g2 matchent ensemble, il faut que
(x + y) & MASK == 0 où x est l'encodage de g1, y est l'encodage de g2 et MASK=0b1000_1000_1000_1000_1000.

9 microsecondes pour ce problème et 4.6 millisecondes pour le temps cumulés de tous les problèmes de cette année.