Python : Cryptogramme Cryptarithm Solver

Résolu
Wubitt Messages postés 26 Statut Membre -  
Wubitt Messages postés 26 Statut Membre -
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)

8 réponses

Réponse 1 / 8
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 585
 
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
0
Réponse 2 / 8
Wubitt Messages postés 26 Statut Membre
 
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.
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585
 
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
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
  
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)
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
Je l'ai remis... Est-ce mieux ainsi ?
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585 > Wubitt Messages postés 26 Statut Membre
 
regarde les lignes 161 et 162: qu'en penses-tu?
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
Elles ne servent à rien apparemment
0
Réponse 3 / 8
Wubitt Messages postés 26 Statut Membre
 














0
Wubitt Messages postés 26 Statut Membre
 
voilà le code en photo
0
Réponse 4 / 8
Wubitt Messages postés 26 Statut Membre
 
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)
0
Wubitt Messages postés 26 Statut Membre
 
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
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585
 
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"
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
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

!!!!!!
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585 > Wubitt Messages postés 26 Statut Membre
 
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.
0

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

Posez votre question
Réponse 5 / 8
Wubitt Messages postés 26 Statut Membre
 
malheureusement, c'est possible, même si 99% de ce qui est écrit ici est le code trouvé
0
Réponse 6 / 8
Wubitt Messages postés 26 Statut Membre
 
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
0
Réponse 7 / 8
Wubitt Messages postés 26 Statut Membre
 
reste à ajouter l'option que les chiffres peuvent être les mêmes pour deux lettres ou plus différentes.
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585
 
je pense qu'il suffit de ne jamais rien retirer de unused.
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
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...
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585 > Wubitt Messages postés 26 Statut Membre
 
laquelle ne l'est plus?
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
Voici celle qui a disparu : SEND+MORE=MONEY
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585 > Wubitt Messages postés 26 Statut Membre
 
chez moi, elle fonctionne. as-tu encore plusieurs lignes 
def solve_impl
?
commence par corriger cela.
0
Réponse 8 / 8
Wubitt Messages postés 26 Statut Membre
 
Pouvez-vous me montrer la correction ?
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585
 
je pense que tu progresseras mieux en le faisant toi-même. regarde ce que tu as partagé en #17.
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
je ne vois pas ce que je dois corriger...
le len ?
le carry ?
0
yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention   1 585 > Wubitt Messages postés 26 Statut Membre
 
as-tu encore plusieurs lignes 
def solve_impl
?
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
oui, beaucoup
0
Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 24281 Date d'inscription   Statut Contributeur Dernière intervention  
 
j'aurais besoin d'un indice sur ce que je dois corriger, s'il vous plaît... je ne trouve pas l'erreur.
0

Discussions similaires

Pix python
Soldat7632 -
Phil_1857 -

4 réponses
Python introuvable
DeepMaze -
mamiemando -

3 réponses
le mot secret ne s'affiche pas, comment pourrais-je faire?
v.b.06 -
elevedeprime -

5 réponses
Programme python
PIROYOLO -
PIROYOLO -

4 réponses
afficher un message sur python ""
Tim -
Enzo -

2 réponses