L’énigme d’Hermionne, Harry Potter tome 1

L’énigme

Lors du premier tome de Harry Potter les trois héros doivent résoudre une énigme - qui ne nécessite aucune magie - afin d’accéder à la salle où est cachée la pierre philosophale. Ce problème, dont l’auteur serait le professeur Rogue (Professor Snape pour les anglophones), consiste à trouver deux potions parmi les sept qui se trouvent devant eux : celles permettent d’avancer et de reculer. Ils sont aidés de quelques indices :

  1. Il y a trois fioles de poison, deux fioles de vin d’ortie, une fiole permettant d’avancer et une fiole permettant de reculer.
  2. Immédiatement à gauche de chacune des deux fioles de vin se trouve une fiole de poison.
  3. Les fioles 1 et 7 ont des contenus différents~; ni l’une ni l’autre n’est la fiole qui permet d’avancer.
  4. Ni la fiole la plus grande (fiole 6) ni la plus petite (fiole 3) ne contient du poison.
  5. Les contenus des fioles 2 et 6 sont identiques.

Les solutions

Les deux solutions proposées sont équivalentes, elles consistent à parcourir toutes les solutions et à accepter la première qui valide toutes les règles. L’ensemble des possibilités n’est pas très élevé et l’algorithme le plus simple suffit. La première fonction solution n’utilise que des fonctions pour trouver la solution, la seconde implémente le même algorithme avec des classes : solution. Et la solution est :

<<<

from ensae_teaching_cs.special.hermionne_classes import solution
print(solution())

>>>

    poison, vin, avancer, poison, poison, vin, reculer

Le parcours des solutions de la fonction solution fait intervenir deux boucles qui implémentent un compteur. Chacune des 7 cases peut contenir 4 potions différenes (poison, vin, avancer, reculer) codé 0, 1, 2, 3. Il y a 4^7 solutions. Pourquoi ne pas les parcourir de 1 à 4^7 ? La n ième solution correspond à :

  • case 1 : n \mod 4
  • case 2 : partie entière de (n \mod 16) / 4
  • case 3 : partie entière de (n \mod 64) / 16
  • case i : partie entière de (n \mod 4^i) / 4^{i-1}

Cela donne :

for i in range(4**7):
    l = [(i % (4**k)) // (4**(k-1)) for k in range(1,8)]

Soit :

    [0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0]
    [2, 0, 0, 0, 0, 0, 0]
    [3, 0, 0, 0, 0, 0, 0]
    [0, 1, 0, 0, 0, 0, 0]
    [1, 1, 0, 0, 0, 0, 0]
    [2, 1, 0, 0, 0, 0, 0]
    [3, 1, 0, 0, 0, 0, 0]
    [0, 2, 0, 0, 0, 0, 0]
    ...

Cela revient à écrire un nombre entier en base 4. Comme 4 est une puissance de deux, on peut utiliser des opérateurs binaires >> qui déplacent les bits d’un nombre vers la droite (division par deux à chaque décalage et & qui est l’opérateur ET.

for i in range(4**7):
    l = [(i >> (2*k) & 4 for k in range(0,7)]

Pour chaque des solutions, utilise une fonction qui vérifie les cinq règles du programme :

from collections import Counter
def solution_correcte(case):
    if case[1] != case[5]: return False
    if case[5] == 0: return False
    if case[2] == 0: return False
    if case[0] == case[6] : return False
    if case[0] == 2: return False
    if case[6] == 2: return False
    c = Counter(case)
    if c[0] != 3: return False
    if c[1] != 2: return False
    if c[2] != 1: return False
    if c[3] != 1: return False
    for k in range(1, 7):
        if case[k] == 1 and case[k-1] != 0:
            return False
    return True

La boucle qui parcourt les solutions est modifiée

solutions = []
for i in range(4**7):
    l = [(i >> (2*k)  & 4 for k in range(0,7)]
    if solution_correcte(l):
        solutions.append(l)
print(solutions)

Le programme perd beaucoup de temps à parcourir toutes les solutions. Une idée simple pour aller plus vite est de réduire l’ensemble des solutions à parcourir en s’appuyant sur une règle. Par exemple celle qui affirme que les potions cases 2 et 6 sont identiques.

solutions = []
for i in range(4**6):
    l = [(i % (4**k)) // (4**(k-1)) for k in range(1,7)]
    l.insert(5, l[1])
    if solution_correcte(l):
        solutions.append(l)
print(solutions)

On parcourt 4 fois moins de solutions.