Python : Cryptogramme Cryptarithm Solver

Résolu

Wubitt Messages postés 26 Statut Membre -
Wubitt Messages postés 26 Statut Membre - 14 avr. 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)

Afficher la suite

8 réponses

Résumé de la discussion

La discussion porte sur la création d'un petit solveur cryptarithmetic en Python, avec contraintes numériques 0 à 9 réutilisables et cohérence des lettres sur l'ensemble des équations. Plusieurs intervenants examinent des implémentations où résoudre l'addition, la multiplication et d'autres opérations exige une mapping unique des lettres vers des chiffres et un tableau "unused". Le fil aborde des bugs fréquents tels que la duplication de solve_impl, des tests avec des cas simples comme a=b+2, et des améliorations pour éviter des échecs. D'autres échanges insistent sur l'importance de partager le code avec une indentation correcte et proposent des cas de tests variés pour évaluer robustesse et performance.

Réponse 1 / 8
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588

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

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.

yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588

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 23437 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)

Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention

Je l'ai remis... Est-ce mieux ainsi ?
0
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > 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 23437 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
1. Wubitt Messages postés 26 Statut Membre
  
  voilà le code en photo
  
  0

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)

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 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588

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"

Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 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

!!!!!!

yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > 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

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

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
1. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588
  
  je pense qu'il suffit de ne jamais rien retirer de unused.
  
  0
  1. Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 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
  2. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > Wubitt Messages postés 26 Statut Membre
    
    laquelle ne l'est plus?
    
    0
  3. Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention
    
    Voici celle qui a disparu : SEND+MORE=MONEY
    
    0
  4. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > 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
1. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588
  
  je pense que tu progresseras mieux en le faisant toi-même. regarde ce que tu as partagé en #17.
  
  0
2. Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention
  
  je ne vois pas ce que je dois corriger...
  le len ?
  le carry ?
  
  0
3. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > Wubitt Messages postés 26 Statut Membre
  
  as-tu encore plusieurs lignes
  def solve_impl
  ?
  
  0
4. Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention
  
  oui, beaucoup
  
  0
5. Wubitt Messages postés 26 Statut Membre > yg_be Messages postés 23437 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

Python : Cryptogramme Cryptarithm Solver

8 réponses

Discussions similaires

Newsletters