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
Python retour à la ligne dans le code - Forum Python

8 réponses

Réponse 1 / 8

yg_be Messages postés 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 Ambassadeur 1 572
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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 1 572
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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 1 572 > 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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 1 572
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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 1 572
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 23505 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 30 mars 2025 1 572
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

Bonjour,

Je suis débutant dans le domaine de la programmation et j'essaye de m’entraîner en utilisant visual studio code. J'ai écrit quelques ligne de programme pour voir si ça marchait après avoir installé l'extension python. J'ai lu qu'il me fallait aussi l'extension code runner pour que mon programme fonctionne, et après l'avoir installé le terminal m'affiche "python est introuvable", alors que ça fonctionnait avant d'installer code runner.

Si quelqu'un pouvait m'aider, ce serait génial !

Merci d'avance

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

Bonjour,

En Python, quelle est la différence entre \r et \n ?
Je parle ici de deux éléments que l'on glisse parfois dans des strings.

Merci par avance

Configuration: Windows Vista / Internet Explorer 8.0

[PyCharm] Pas d'interpréteur python

Bonjour, Quand je lance mon script python, PyCharm me dit que je n'ai pas d'interpréteur python valide. Comment dois-je faire pour un sélectionner un, étant donné qu'il ne me propose aucune alternative :(

Programme python

Bonjour, Je dois faire ce programme en math pour lundi mais je galère quelqu'un peut m'aider ? Merci beaucoup

executer un programe python dans la console

bonjour
je voudrais lancer un programme python depuis la console de sublime text 3. je ne sais pas comment faire.

mon code :
A=4
A=A+2
print(A)

merci d'avance
hpfort