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 - Guide
Geometry dash python ✓ - Forum Python
Lancer script python linux - Forum Ubuntu
Ce programme est écrit en python ✓ - Forum Python
Compris entre python ✓ - Forum Python

8 réponses

Réponse 1 / 8

yg_be Messages postés 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471
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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471
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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024
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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471 > 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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471
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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471
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 22707 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 19 avril 2024 1 471
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

programme qui n'affiche pas le mot secret

Python introuvable

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

Récupérer des données d'un fichier texte

syntaxe pour passer une ligne de code python

Discussions similaires

Newsletters