Python : Cryptogramme Cryptarithm Solver

Résolu/Fermé

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020 - Modifié le 12 avril 2020 à 16:16
Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020 - 14 avril 2020 à 10:06

Bonjour,

J'essaie de créer un petit programme pour résoudre des Cryptarythmmes, mais je suis bloqué ...

Contrainte :
- Les nombres doivent tous être compris entre 0 et 9, mais on peut les utiliser plusieurs fois... Par exemple A peut être égal à 1, B = 2, ... Mais C peut aussi être égal à 1... etc

J'aimerai :
- Améliorer le processus pour que justement la contrainte chiffre de 0 à 9 soit possible pour plusieurs lettres.
- Intégrer une résolution globale pour que A (par exemple) soit le même chiffre dans l'ensemble des équations.

Est-ce quelqu'un pourrait m'aider s'il vous plaît ?
Je débute dans Python, alors n'hésitez pas à illustrer vos propos avec les lignes de codes.

Par avance merci à tout ceux qui m'aideront.

Voici ce que j'ai déjà fait :

from time import time

def solve(text):
    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("+")] for s in text.split("=")]
    signs = [1]*len(lhs) + [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("*")] for s in text.split("=")]
    signs = [1]*len(lhs) * [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("-")] for s in text.split("=")]
    signs = [-1]*len(lhs) - [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("/")] for s in text.split("=")]
    signs = [-1]*len(lhs) / [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

testCases=["abcd*ef/ad=ea*dgf/he+ecah",
           "ihbgh*ga/hbl=gf*gjad/di+eeck",
           "eihle*dhc/gi=lc*aijbk/fk+dkigk",
           "bacj*fjg/eid=df*hcli/ai+daeia",
           "lkjek*fb/ddd=c*jikgb/egb+elblc",
           "ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
           "abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
           "ef+ga-dhc+fjg-fb=gfl",
           "ad+hbl-gi-eid-ddd=dbl",
           "dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
           "he+di+fk+ai+egb=gcl",
           "ecah-eeck+dkigk+daeia-elblc=bbfg",
           ]
for test in testCases:
    print(test)
    start=time()
    solution=solve(test)
    print(time()-start, "seconds")
    if solution is None:
        print("No solution exists")
    else:
        result="".join(str(solution.get(c, c)) for c in test)
        for key, value in solution.items():
            print(key, '=', value)
        print(result)
    print(flush=True)

A voir également:

Python : Cryptogramme Cryptarithm Solver
Citizen code python avis - Accueil - Outils
Python generator - Télécharger - Sécurité
Trouver la position d'un élément dans une liste python ✓ - Forum Python
Mot secret python pix ✓ - Forum Python

8 réponses

Réponse 1 / 8

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 Ambassadeur 1 576
Modifié le 12 avril 2020 à 17:04

bonjour, dans que contexte fais-tu cela?
as-tu écrit ce programme?
es-tu certain du contenu des lignes 159 et 160?
peux-tu partager ton programme en utilisant les balises de code, de façon a préserver l'indentation?
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code

Réponse 2 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 17:00

Bonjour yg_be,

Je fais cela dans le cadre d'un loisir pour résoudre l'énigme qui est dedans :
"abcd*ef/ad=ea*dgf/he+ecah",
"ihbgh*ga/hbl=gf*gjad/di+eeck",
"eihle*dhc/gi=lc*aijbk/fk+dkigk",
"bacj*fjg/eid=df*hcli/ai+daeia",
"lkjek*fb/ddd=c*jikgb/egb+elblc",
"ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
"abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
"ef+ga-dhc+fjg-fb=gfl",
"ad+hbl-gi-eid-ddd=dbl",
"dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
"he+di+fk+ai+egb=gcl",
"ecah-eeck+dkigk+daeia-elblc=bbfg"

Je n'ai pas vraiment écrit ce code, je l'ai trouvé sur internet pour additionner et je l'ai transformé pour les 4 opérations...

Du coup, je cherche à l'étoffer pour résoudre mon énigme dont voici la photo.

Pour les lignes 159 et 160, cela me permet de voir ou je suis bloqué, mais cela n'aura plus d'utilité à la fin si ce programme fonctionne.

Merci d'avance pour votre aide.

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 1 576
12 avril 2020 à 17:05

peux-tu partager ton programme en utilisant les balises de code, de façon a préserver l'indentation?
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020 > yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025
12 avril 2020 à 17:10

from time import time

def solve(text):
    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("+")] for s in text.split("=")]
    signs = [1]*len(lhs) + [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("*")] for s in text.split("=")]
    signs = [1]*len(lhs) * [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("-")] for s in text.split("=")]
    signs = [-1]*len(lhs) - [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("/")] for s in text.split("=")]
    signs = [-1]*len(lhs) / [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

testCases=["abcd*ef/ad=ea*dgf/he+ecah",
           "ihbgh*ga/hbl=gf*gjad/di+eeck",
           "eihle*dhc/gi=lc*aijbk/fk+dkigk",
           "bacj*fjg/eid=df*hcli/ai+daeia",
           "lkjek*fb/ddd=c*jikgb/egb+elblc",
           "ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
           "abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
           "ef+ga-dhc+fjg-fb=gfl",
           "ad+hbl-gi-eid-ddd=dbl",
           "dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
           "he+di+fk+ai+egb=gcl",
           "ecah-eeck+dkigk+daeia-elblc=bbfg",
           ]
for test in testCases:
    print(test)
    start=time()
    solution=solve(test)
    print(time()-start, "seconds")
    if solution is None:
        print("No solution exists")
    else:
        result="".join(str(solution.get(c, c)) for c in test)
        for key, value in solution.items():
            print(key, '=', value)
        print(result)
    print(flush=True)

Je l'ai remis... Est-ce mieux ainsi ?

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 1 576 > Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 17:15

regarde les lignes 161 et 162: qu'en penses-tu?

Elles ne servent à rien apparemment

Réponse 3 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 17:42

voilà le code en photo

Réponse 4 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 17:49

le voici en plus court :

from time import time

def solve(text):
    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("+")] for s in text.split("=")]
    lhs, rhs = [[term[::-1] for term in s.split("*")] for s in text.split("=")]
    lhs, rhs = [[term[::-1] for term in s.split("-")] for s in text.split("=")]
    lhs, rhs = [[term[::-1] for term in s.split("/")] for s in text.split("=")]
    signs = [1]*len(lhs) + [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
   

   
    return True
    return False

testCases=["abcd*ef/ad=ea*dgf/he+ecah",
           "ihbgh*ga/hbl=gf*gjad/di+eeck",
           "eihle*dhc/gi=lc*aijbk/fk+dkigk",
           "bacj*fjg/eid=df*hcli/ai+daeia",
           "lkjek*fb/ddd=c*jikgb/egb+elblc",
           "ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
           "abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
           "ef+ga-dhc+fjg-fb=gfl",
           "ad+hbl-gi-eid-ddd=dbl",
           "dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
           "he+di+fk+ai+egb=gcl",
           "ecah-eeck+dkigk+daeia-elblc=bbfg",
           ]
for test in testCases:
    print(test)
    start=time()
    solution=solve(test)
    print(time()-start, "seconds")
    if solution is None:
        print("No solution exists")
    else:
        result="".join(str(solution.get(c, c)) for c in test)
        for key, value in solution.items():
            print(key, '=', value)
        print(result)
    print(flush=True)

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
Modifié le 12 avril 2020 à 17:55

Malheureusement cela bug pour la deuxième multiplication :
et surtout j'ai beaucoup moins de résultats d'égalité qu'auparavant...

ihbgh*ga/hbl=gf*gjad/di+eeck
3.552436828613281e-05 seconds
a = 0
l = 1
d = 2
k = 9
g = 3
b = 4
c = 6
* = 8
h = 5
j = 7
i5435830/541=3f83702/2i+ee69

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 1 576
12 avril 2020 à 17:55

cela va mieux, il ne reste qu'une erreur avec les lignes 46 et 47.

cependant, il ne donne pas de résultat utile, même pour un cas simple comme:
"a=b+2"

voilà au plus court possible :

from time import time

def solve(text):
    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("+")] for s in text.split("=")]
    signs = [1]*len(lhs) + [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
   
    return True
    return False

testCases=["a=b+2",
           "abcd*ef/ad=ea*dgf/he+ecah",
           "ihbgh*ga/hbl=gf*gjad/di+eeck",
           "eihle*dhc/gi=lc*aijbk/fk+dkigk",
           "bacj*fjg/eid=df*hcli/ai+daeia",
           "lkjek*fb/ddd=c*jikgb/egb+elblc",
           "ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
           "abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
           "ef+ga-dhc+fjg-fb=gfl",
           "ad+hbl-gi-eid-ddd=dbl",
           "dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
           "he+di+fk+ai+egb=gcl",
           "ecah-eeck+dkigk+daeia-elblc=bbfg",
           ]
for test in testCases:
    print(test)
    start=time()
    solution=solve(test)
    print(time()-start, "seconds")
    if solution is None:
        print("No solution exists")
    else:
        result="".join(str(solution.get(c, c)) for c in test)
        for key, value in solution.items():
            print(key, '=', value)
        print(result)
    print(flush=True)

Mais effectivement, il doit y avoir un problème car cela me donne :

a=b+2
5.817413330078125e-05 seconds
a = 1
b = 9
1=9+2

!!!!!!

le programme que tu as trouvé sur internet fonctionne-t'il mieux?
c'est peut-être quand tu l'as transformé qu'il a arrêté de fonctionner.

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 18:24

malheureusement, c'est possible, même si 99% de ce qui est écrit ici est le code trouvé

Réponse 6 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 18:38

voilà, c'est corrigé et cela fonctionne :

from time import time

def solve(text):
    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("+")] for s in text.split("=")]
    signs = [1]*len(lhs) + [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("*")] for s in text.split("=")]
    signs = [1]*len(lhs) * [-1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("-")] for s in text.split("=")]
    signs = [-1]*len(lhs) - [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return True
    return False

    text = text.replace(" ", "")
    lhs, rhs = [[term[::-1] for term in s.split("/")] for s in text.split("=")]
    signs = [-1]*len(lhs) / [1]*(len(rhs)-1)
    lhs.extend(rhs[:-1])
    dic = {}
    maxlen = max(len(rhs[-1]), max(map(len, lhs)))
    return dic if solve_impl(lhs, signs, rhs[-1], dic, set(range(10)), 0, 0, 0, maxlen) else None

def solve_impl(lhs, signs, rhs, dic, unused, row, col, carry, maxlen):
    if col==maxlen:
        return carry==0
    if row==len(lhs):
        if col>=len(rhs):
            return carry%10==0 and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if rhs[col] in dic:
            return dic[rhs[col]]==carry%10 and (col<len(rhs)-1 or dic[rhs[col]]!=0)\
                and solve_impl(lhs, signs, rhs, dic, unused, 0, col+1, carry//10, maxlen)
        if carry%10 not in unused:
            return False
        dic[rhs[col]]=carry%10
        if solve_impl(lhs, signs, rhs, dic, unused-{carry%10}, 0, col+1, carry//10, maxlen):
            return True
        del dic[rhs[col]]
        return False
    if col>=len(lhs[row]):
        return solve_impl(lhs, signs, rhs, dic, unused, row+1, col, carry, maxlen)
    if lhs[row][col] in dic:
        return (col<len(lhs[row])-1 or dic[lhs[row][col]]!=0) \
            and solve_impl(lhs, signs, rhs, dic, unused, row+1, col,
                           carry+signs[row]*dic[lhs[row][col]], maxlen)
    for digit in unused:
        if digit!=0 or col<len(lhs[row])-1:
            dic[lhs[row][col]]=digit
            if solve_impl(lhs, signs, rhs, dic, unused-{digit}, row+1, col,
                          carry+signs[row]*digit, maxlen):
                return True
            del dic[lhs[row][col]]
    return False

testCases=["a=b+2",
           "SEND+MORE=MONEY",
           "abcd*ef/ad=ea*dgf/he+ecah",
           "ihbgh*ga/hbl=gf*gjad/di+eeck",
           "eihle*dhc/gi=lc*aijbk/fk+dkigk",
           "bacj*fjg/eid=df*hcli/ai+daeia",
           "lkjek*fb/ddd=c*jikgb/egb+elblc",
           "ekjhl-gfl-dbl=gaaeli-gdhbhb-gcl-bbfg",
           "abcd+ihbgh-eihle-bacj-lkjek=ekjhl",
           "ef+ga-dhc+fjg-fb=gfl",
           "ad+hbl-gi-eid-ddd=dbl",
           "dgf*gjad-aijbk-hcli-jikgb=gdhbhb",
           "he+di+fk+ai+egb=gcl",
           "ecah-eeck+dkigk+daeia-elblc=bbfg",
           ]
for test in testCases:
    print(test)
    start=time()
    solution=solve(test)
    print(time()-start, "seconds")
    if solution is None:
        print("No solution exists")
    else:
        result="".join(str(solution.get(c, c)) for c in test)
        for key, value in solution.items():
            print(key, '=', value)
        print(result)
    print(flush=True)

réponses données :

a=b+2
0.0 seconds
a = 3
b = 1
2 = 2
3=1+2

SEND+MORE=MONEY
0.02094292640686035 seconds
D = 7
E = 5
Y = 2
N = 6
R = 8
O = 0
S = 9
M = 1
9567+1085=10652

Réponse 7 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
12 avril 2020 à 18:41

reste à ajouter l'option que les chiffres peuvent être les mêmes pour deux lettres ou plus différentes.

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 1 576
Modifié le 12 avril 2020 à 19:29

je pense qu'il suffit de ne jamais rien retirer de unused.

Cela ne semble pas suffire.... Une seule autre équation est résolue :

he+di+fk+ai+egb=gcl
0.00021886825561523438 seconds
e = 3
i = 9
k = 9
b = 9
h = 9
d = 6
f = 6
a = 6
g = 6
l = 9
c = 6
93+69+69+69+369=669

et une autre ne l'est plus...

laquelle ne l'est plus?

Voici celle qui a disparu : SEND+MORE=MONEY

chez moi, elle fonctionne. as-tu encore plusieurs lignes

def solve_impl

?
commence par corriger cela.

Réponse 8 / 8

Wubitt Messages postés 23 Date d'inscription dimanche 12 avril 2020 Statut Membre Dernière intervention 14 avril 2020
13 avril 2020 à 08:19

Pouvez-vous me montrer la correction ?

yg_be Messages postés 23517 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 avril 2025 1 576
13 avril 2020 à 08:37

je pense que tu progresseras mieux en le faisant toi-même. regarde ce que tu as partagé en #17.

je ne vois pas ce que je dois corriger...
le len ?
le carry ?

as-tu encore plusieurs lignes

def solve_impl

oui, beaucoup

j'aurais besoin d'un indice sur ce que je dois corriger, s'il vous plaît... je ne trouve pas l'erreur.

Discussions similaires

Python introuvable

[Python] différence entre \r et \n

[PyCharm] Pas d'interpréteur python

Programme python

executer un programe python dans la console