Brute force en Python : énumérer les arrangements avec itertools.permutations

Technique de brute force en Python avec itertools.permutations : énumérer les arrangements ordonnés et tester chacun

→ Challenge Correction: Traversée 26 #8 The Monolith

Rappel de l’énoncé

On reçoit la position de départ de l’aiguille (charge) et une liste d’instructions comme "K7". Chaque instruction multiplie la position par son chiffre puis ajoute le rang de sa lettre, sur un cadran de 60 crans. Il faut trouver 4 instructions distinctes qui, appliquées dans un certain ordre, amènent l’aiguille sur la position de référence (26), et renvoyer leurs codes séparés par des tirets, par exemple "A4-B7-E4-K3".

Pièges à éviter

  • La référence n’est pas dans les données : seules charge et instructions sont fournies. La position à atteindre, 26, se déduit du nom de l’événement « Traversée 26 », tout simplement !
  • Le rang de la lettre commence à 1 : A vaut 1, pas 0. Un calcul basé sur le code du caractère (65 pour A) ou sur un indice de tableau (0 pour A) donne un décalage si on ne corrige pas.
  • Le chiffre est du texte : dans "K7", le 7 est un caractère. Il faut le convertir en entier avant de multiplier. Selon les langages, multiplier une chaîne donne une erreur, une répétition de texte ("7" * 3 vaut "777" en Python) ou une conversion implicite.
  • Le cadran est circulaire : sans le modulo 60, la position dépasse vite 59 (49 × 7 + 2 = 345) et ne sera jamais égale à 26. Il faut ramener la position entre 0 et 59.
  • L’ordre des instructions compte : J8 puis T3 ne donne pas le même résultat que T3 puis J8. Tester seulement des groupes de 4 instructions sans leurs différents ordres fait rater des solutions.
  • Les instructions doivent être distinctes : avec des boucles imbriquées écrites à la main, il est facile de réutiliser deux fois la même instruction dans un assemblage.

Code complet

from itertools import permutations

TAILLE_CADRAN = 60
NOMBRE_INSTRUCTIONS = 4
REFERENCE = 26  # position de référence du Monolithe (événement « Traversée 26 »)


# Applique une instruction à une position et renvoie la nouvelle position
def appliquer_instruction(position, instruction):
    # "K7" => lettre "K", multiplicateur 7
    lettre = instruction[0]
    multiplicateur = int(instruction[1:])  # le chiffre est du texte : conversion en entier

    # A vaut 1, B vaut 2, C vaut 3... (et non A vaut 0)
    rang_lettre = ord(lettre) - ord("A") + 1

    # Le modulo ramène l'aiguille sur le cadran : 345 % 60 => 45
    return (position * multiplicateur + rang_lettre) % TAILLE_CADRAN


# Applique les instructions d'un assemblage, dans l'ordre
def appliquer_assemblage(position, assemblage):
    for instruction in assemblage:
        position = appliquer_instruction(position, instruction)
    return position


# Brute force : on teste chaque arrangement possible jusqu'à trouver le bon
def trouver_assemblage(charge, instructions):
    # permutations() énumère tous les arrangements ordonnés de 4 instructions distinctes
    for assemblage in permutations(instructions, NOMBRE_INSTRUCTIONS):
        if appliquer_assemblage(charge, assemblage) == REFERENCE:
            return "-".join(assemblage)  # ("J8", "T3", ...) => "J8-T3-..."
    return None


# Données du challenge
charge = 31
instructions = ['J8', 'T3', 'B3', 'E1', 'Z8', 'M7', 'A1', 'X1', 'D5', 'U6']

print(trouver_assemblage(charge, instructions))  # J8-T3-E1-M7

Découper le problème

On ne sait pas calculer directement quelles instructions choisir : la multiplication et le modulo rendent le résultat difficile à prévoir. En revanche, il y a peu de possibilités, donc on peut toutes les essayer. C’est le principe du brute force (ou recherche exhaustive) : énumérer tous les candidats, tester chacun, garder celui qui fonctionne.

La solution se découpe en trois étapes :

  1. Calculer la nouvelle position après une instruction.
  2. Calculer la position finale après un assemblage de 4 instructions.
  3. Énumérer tous les assemblages possibles et renvoyer le premier qui mène à la référence.

Les valeurs fixes de l’énoncé sont regroupées en constantes en haut du fichier. La référence, absente des données, y est écrite explicitement :

TAILLE_CADRAN = 60
NOMBRE_INSTRUCTIONS = 4
REFERENCE = 26  # position de référence du Monolithe (événement « Traversée 26 »)

Appliquer une instruction

On sépare d’abord l’instruction en deux parties : le premier caractère est la lettre, le reste est le multiplicateur. instruction[1:] prend tout ce qui suit la lettre et int() le convertit en nombre.

Pour le rang de la lettre, la fonction ord() renvoie le code d’un caractère : ord("A") vaut 65, ord("K") vaut 75. En soustrayant ord("A"), on obtient la position dans l’alphabet en partant de 0, d’où le + 1 pour que A vaille 1.

Enfin, l’opérateur % renvoie le reste de la division par 60, ce qui ramène toujours la position entre 0 et 59, quel que soit le nombre de tours effectués.

# Applique une instruction à une position et renvoie la nouvelle position
def appliquer_instruction(position, instruction):
    # "K7" => lettre "K", multiplicateur 7
    lettre = instruction[0]
    multiplicateur = int(instruction[1:])  # le chiffre est du texte : conversion en entier

    # A vaut 1, B vaut 2, C vaut 3... (et non A vaut 0)
    rang_lettre = ord(lettre) - ord("A") + 1

    # Le modulo ramène l'aiguille sur le cadran : 345 % 60 => 45
    return (position * multiplicateur + rang_lettre) % TAILLE_CADRAN

Sur l’exemple de l’énoncé : 12 × 4 + 1 = 49, puis 49 × 7 + 2 = 345 et 345 % 60 = 45.

Appliquer un assemblage

Un assemblage est une suite de 4 instructions. On part de la charge et on applique chaque instruction à la position obtenue à l’étape précédente : la variable position est mise à jour à chaque tour de boucle.

# Applique les instructions d'un assemblage, dans l'ordre
def appliquer_assemblage(position, assemblage):
    for instruction in assemblage:
        position = appliquer_instruction(position, instruction)
    return position

Appliquer le modulo à chaque étape plutôt qu’une seule fois à la fin donne le même résultat, mais garde des nombres petits et correspond à ce que fait l’aiguille sur le cadran.

Énumérer les assemblages avec itertools.permutations

Le module itertools de la bibliothèque standard de Python fournit des outils pour parcourir des combinaisons d’éléments. La fonction permutations(liste, k) produit tous les arrangements de k éléments de la liste : chaque élément n’est utilisé qu’une fois par arrangement, et l’ordre compte. Par exemple :

permutations(["A1", "B2", "C3"], 2)
# ("A1", "B2"), ("A1", "C3"), ("B2", "A1"), ("B2", "C3"), ("C3", "A1"), ("C3", "B2")

C’est exactement ce que demande l’énoncé : 4 instructions distinctes, dans un ordre au choix. Avec 10 instructions, cela représente 10 × 9 × 8 × 7 = 5040 assemblages, ce qui se teste instantanément.

# Brute force : on teste chaque arrangement possible jusqu'à trouver le bon
def trouver_assemblage(charge, instructions):
    # permutations() énumère tous les arrangements ordonnés de 4 instructions distinctes
    for assemblage in permutations(instructions, NOMBRE_INSTRUCTIONS):
        if appliquer_assemblage(charge, assemblage) == REFERENCE:
            return "-".join(assemblage)  # ("J8", "T3", ...) => "J8-T3-..."
    return None

Trois points à retenir :

  • permutations() ne construit pas la liste complète à l’avance : elle produit les arrangements un par un, au fil de la boucle. Le return arrête donc l’énumération dès qu’un assemblage valide est trouvé, puisque n’importe quelle solution est acceptée.
  • Chaque assemblage est un tuple, par exemple ("J8", "T3", "E1", "M7"). La méthode "-".join() assemble ses éléments en une chaîne, avec un tiret entre chacun.
  • La fonction voisine combinations() ne serait pas adaptée : elle ne produit qu’un seul ordre par groupe de 4 instructions et ferait rater des solutions.

Bonus : la solution des vainqueurs de la Battle Dev

from itertools import permutations

CIBLE = 26

for combo in permutations(instructions,4):
    position = charge
    for inst in combo:
        lettre = inst[0]
        chiffre = int(inst[1:])
        position = (position *chiffre+ord(lettre) -ord("A") +1) %60
    
    if position == CIBLE:
        print("-".join(combo))
        break


Qui a codé ce superbe contenu ?

Keep learning

Other content to discover