Le Compte est bon en Python

Algorithme de résolution

Un premier algorithme de recherche de solution peut être écrit en réduisant récursivement le nombre de plaquettes, remplaçant chaque paire de plaquette par le résultat d’une opération admissible.

Cet algorithme peut s’écrire comme suit.

1. On définit une liste L contenant comme seul élément la liste des plaquettes.
2. Pour chaque jeu de valeurs P pris dans la liste L, pour chaque indice j de plaquette dans P, pour chaque opération binaire f, pour chaque indice i de plaquette dans P tel que i < j, on calcule le nouveau terme t = f(P_i, P_j). Si ce terme t réalise l’objectif, on adjoint son arbre syntaxique à la liste des résultats, sinon on crée un nouveau jeu de valeurs Q avec les plaquettes de P en remplaçant les plaquettes d’indice i et j par le terme t et on adjoint cette liste à la liste L.

Le nombre d’arbres syntaxiques ainsi produits vaut donc au maximum 6 + 4(2 parmi 6) (1 + 4(2 parmi 5) (1 + 4(2 parmi 4) (1 + 4(2 parmi 3) (1 + 4)))) = 6 + 60 × (1 + 40 × (1 + 24 × (1 + 60))) = 3 516 066.

On remarquera que l’algorithme ci-dessus ne donne pas tous les arbres syntaxiques possibles, puisque les opérations récursives s’arrêtent dès lors que l’objectif est atteint. On ne cherche donc pas à compliquer un arbre syntaxique déjà suffisant.

Programmation en Python

Pour écrire un programme Python traduisant cet algorithme, je définis d’abord un terme comme la donnée d’une valeur, d’une expression (l’arbre syntaxique, sous forme d’une chaine de caractères) et d’un niveau de priorité associé à l’opération à la racine, utile pour déterminer la nécessité d’encadrer l’expression par des parenthèses.

class Terme:
    def __init__(self, val, expr="", niv=0):
        self.val=val # valeur
        self.expr=expr if expr else str(val) # expression
        self.niv=niv # niveau de priorité pour l’opération à la racine
    def group(self):
        return Terme(self.val, "("+self.expr+")", self.niv)

Chaque opération est définie par un symbole, une fonction de calcul, un niveau de priorité, et éventuellement un test pour la pertinence de l’opération. En particulier, on n’effectue une multiplication que si les deux facteurs sont strictement supérieurs à 1, et une soustraction que sur deux valeurs différentes.

class Operation:
    def __init__(self, sym, calc, niv, test=None): 
        self.sym=sym      # symbole de l’opération
        self.calc=calc    # fonction de calcul
        self.niv=niv      # niveau de priorité
        self.test=test    # test vérifiant la pertinence de l’opération
    def ev(self, a, b):   # fonction d’évaluation du terme résultat
        if self.test:
            if not self.test(a.val,b.val):
                if self.test(b.val,a.val):
                    a,b=b,a # renversement des opérandes
                else:
                    return None
        # adjonction de parenthèses au besoin
        if a.niv//2 > self.niv//2: 
            a=a.group()
        if 2*(b.niv//2) >= self.niv:
            b=b.group()
        return Terme(self.calc(a.val,b.val), a.expr+self.sym+b.expr, self.niv)

operations = [Operation("+", lambda a,b: a+b, 5),
    Operation("−", lambda a,b: a-b, 4, lambda a,b:a>b),
    Operation("×", lambda a,b:a*b, 3, lambda a,b:a>1 and b>1),
    Operation("/", lambda a,b:a//b, 2, lambda a,b: b>1 and a%b==0)]

L’algorithme proprement dit est réalisé par la fonction suivante.

def resolution(plaquettes, objectif):
    L=[[Terme(k) for k in sorted(plaquettes, reverse=True)]]
    n=0
    solutions=[]
    while(n<len(L)):
        P=L[n]
        for j in range(len(P)):
            for f in operations:
                for i in range(j):
                    t=f.ev(P[i],P[j])
                    if t:
                        if t.val==objectif:
                            solutions.append(t.expr)
                        else:
                            Q=[(t if k==j else P[k])
                                for k in range(len(P)) if k!=i]
                            L.append(Q)
        n+=1
    return solutions

Élimination des répétitions

Ce programme trouve de nombreuses solutions au problème en exemple ci-dessus en moins d’une minute sur un ordinateur récent. Tous les arbres syntaxiques possibles sont présents, mais on constate des répétitions dont voici quelques causes :

1. L’interversion de deux plaquettes portant la même valeur conduit à reproduire des jeux de termes identiques dans la liste L, d’où de nombreux doublons.
2. Un même arbre syntaxique peut être obtenu en changeant l’ordre de construction des sous-arbres, comme dans l’exemple ci-dessus où les opérandes de la multiplication peuvent être construits dans un ordre quelconque. Là encore, le même arbre syntaxique va donc être produit plusieurs fois.
3. L’associativité de l’addition et de la multiplication, ainsi que les règles opératoires liant ces opérations à la soustraction et la division, peuvent mener à la construction d’arbres syntaxiques différents mais représentant des opérations essentiellement semblables. Dans l’exemple ci-dessus, le sous-arbre représentant l’expression 50 − 10 + 8 aurait pu être réorganisé pour représenter 50 + 8 − 10 ou encore 50 − (10 − 8)

La liste des résultats peut être débarrassée des doublons par une procédure classique de transformation en dictionnaire. Les répétitions de résultats peuvent être effacées en éliminant les doublons dans la liste des résultats.

On peut imposer de construire les sous-arbres dans l’ordre de leur opérande la plus à droite. Pour cela, on munit chaque jeu de termes d’un indice explicitant le terme le plus à droite utilisé, et on interdit la construction de termes à partir de termes plus à gauche.

L’associativité est mise à profit pour interdire d’utiliser une somme comme opérande à droite dans une addition, ou d’utiliser un produit comme opérande à droite dans une multiplication.

Chaque somme algébrique peut se ramener à une somme de termes ou à une différence de sommes, et de même tout enchainement de multiplications et divisions se ramène à un produit de facteurs ou un quotient de produits. On interdit alors d’utiliser une différence dans une addition ou une soustraction, et on interdit d’utiliser un quotient dans une multiplication ou une division.

def resolution2(plaquettes, objectif):
    L=[([Terme(k) for k in sorted(plaquettes, reverse=True)],0)]
    n=0
    solutions=[]
    while(n<len(L)):
        P,debut=L[n]
        for j in range(debut,len(P)):
            for f in operations:
                if P[j].niv//2 != f.niv//2 or P[j].niv > f.niv:
                    for i in range(j):
                        if P[i].niv//2 != f.niv//2 or P[i].niv%2:
                            t=f.ev(P[i],P[j])
                            if t:
                                if t.val==objectif:
                                    solutions.append(t.expr)
                                else:
                                    Q=[(t if k==j else P[k])
                                        for k in range(len(P)) if k!=i]
                                    L.append((Q,j-1))
        n+=1
    return list(set(solutions))

Enrichissement de la réponse

Il arrive (rarement) que le problème posé n’ait pas de réponse. L’exemple le plus simple se trouve avec les plaquettes 1, 1, 2, 2, 3, 3 qui permettra au mieux d’obtenir 81. On souhaite donc déterminer la meilleure approximation par défaut et éventuellement par excès, et on ajoute tant qu’à faire le nombre de calculs effectués. La réponse est alors un objet munie de propriétés.

Afin d’éviter de recalculer la longueur de la liste L à chaque tour de boucle, on peut utiliser une variable N qui la représente.

class Resultat:
    def __init__(self, plaquettes, objectif, calculs, solutions, minoration, majoration):
        self.plaquettes=plaquettes
        self.objectif=objectif
        self.calculs=calculs
        self.solutions=solutions
        self.minoration=minoration
        self.majoration=majoration

def resolution3(plaquettes, objectif):
    L=[([Terme(k) for k in sorted(plaquettes, reverse=True)],0)]
    N=1
    n=0
    solutions=[]
    c=0
    minoration = Terme(max(plaquettes))
    majoration = None
    while(n<N):
        P,debut=L[n]
        for j in range(debut,len(P)):
            for f in operations:
                if P[j].niv//2 != f.niv//2 or P[j].niv > f.niv:
                    for i in range(j):
                        if P[i].niv//2 != f.niv//2 or P[i].niv%2:
                            t=f.ev(P[i],P[j])
                            if t:
                                c+=1
                                if t.val==objectif:
                                    solutions.append(t.expr)
                                else:
                                    Q=[(t if k==j else P[k])
                                        for k in range(len(P)) if k!=i]
                                    L.append((Q,j-1))
                                    N+=1
                                    if t.val < objectif:
                                        if minoration.val < t.val:
                                            minoration = t
                                    elif not majoration or majoration.val > t.val:
                                            majoration = t
        n+=1
    return Resultat(plaquettes, objectif, c, list(set(solutions)), minoration, majoration)