Python : Cryptogramme Cryptarithm Solver
Résolu
Wubitt
Messages postés
23
Date d'inscription
Statut
Membre
Dernière intervention
-
Wubitt Messages postés 23 Date d'inscription Statut Membre Dernière intervention -
Wubitt Messages postés 23 Date d'inscription Statut Membre Dernière intervention -
A voir également:
- Python : Cryptogramme Cryptarithm Solver
- Citizen code python avis - Accueil - Outils
- Python est introuvable. exúcutez sans argument pour procúder ó l ✓ - Forum Python
- Mot secret python pix ✓ - Forum Python
- Python par la pratique : 101 exercices corrigés pdf - Forum Python
- Exercice python - Forum Python
8 réponses
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
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
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
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.
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.
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
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
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)
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)
voilà au plus court possible :
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
!!!!!!
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
!!!!!!
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
voilà, c'est corrigé et cela fonctionne :
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
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
reste à ajouter l'option que les chiffres peuvent être les mêmes pour deux lettres ou plus différentes.