En binaire et en puissances de 2

Je vois deux types de caractères, je pense binaire.
Transformer les lignes en nombre, ça permet des comparaisons d'entiers plutôt que de chaînes : ça me plaît.

Alors voilà une partie 1 assez rapide, faut surtout (surtout) bien mesurer ses indices de listes, ses ranges, etc.

D'abord les données, on va retourner une liste de nombres horizontaux et la même chose en vertical, les . sont des 0 et les # des 1.

def patterns():
 _h, _v = [], []
 for line in stdin.read().strip().splitlines() + [""]:
 if line:
 line = line.translate(str.maketrans(".#", "01"))
 _h.append(int(line, 2))
 _v.append(list(line))
 continue
 _v = [int("".join(col), 2) for col in zip(*_v)]
 yield _h, _v
 _h, _v = [], []
data = list(patterns())

Ensuite j'ai deux fonctions de calcul de symétries, différentes pour les deux exercices, ça se factorisait assez mal chez moi.

def symetry(search):
 for axe in range(len(search) - 1, 0, -1):
 size = min(axe, len(search) - axe)
 for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1]):
 if a != b:
 break
 else:
 yield axe
ex1 = sum(
 sum(list(symetry(h))) * 100 + sum(list(symetry(v)))
 for h, v in data
)

L'exercice 2 est un peu plus complexe, puisque je n'ai plus vraiment accès aux données d'origine, je n'ai plus que mes nombres :

POWEROF2 = {2**i for i in range(20)}
def almost_symetry(search):
 for axe in range(len(search) - 1, 0, -1):
 size = min(axe, len(search) - axe)
 diffs = [
 (a, b)
 for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1])
 if a != b
 ]
 # looking for exactly one different line
 if len(diffs) != 1:
 continue
 # And one difference between the two lines
 a, b = diffs[0]
 diff = abs(a - b) * 2
 if diff in POWEROF2 and (a & diff) == (b & diff):
 yield axe
ex2 = sum(
 sum(list(almost_symetry(h))) * 100 + sum(list(almost_symetry(v)))
 for h, v in data
)

La réflexion est simple : si deux lignes diffèrent d'un seul élément, alors leur représentation binaire diffère d'un seul bit, donc leur différence est une puissance de 2. Les puzzles ne dépassent pas 17x17, donc avec mon ensemble qui va jusque 2²⁰ je suis suffisamment large.

Par contre c'est une condition nécessaire, mais pas suffisante. Presque, en tout cas avec les données de test on ne trouve pas l'erreur.
Ben oui, si deux lignes diffèrent sur deux cases côte à côte, une à 1 d'un côté et l'autre de l'autre, la différence fait 2ⁿ⁺¹ - 2ⁿ = 2^n, qui est puissance de 2.
En regardant bien, pour une différence de 2ⁿ on a forcément le bit n différent, mais si le bit n+1 est identique alors les deux nombres sont identiques (sinon on peut même en avoir plein : 32-16-8=8 !).

Bref, encore une fois je veux faire vite, je teste une idée sans même la valider dans ma tête, c'est faux et je me demande pourquoi.

Mais voilà, finalement on a un truc assez simple, trivialement rapide (0,3s on tombe jamais vraiment en dessous de ça en démarrant un interpréteur python), donc pas trop chercher à optimiser, on ne saurait pas vraiment si on y gagne ou pas.

Par contre côté lisibilité c'est mort, il faut réfléchir à tout ce que ces indices, ces parcours à l'envers ou pas, etc, signifient vraiment, pour comprendre quoi que ce soit.

• Yth.