un casse-tête auto-référentiel: sic

**eyquem** · 21/07/2010, 19h07

http://www.developpez.net/forums/d95...e/#post5351275

Ça me rappelle un type de problème “facilement“ (?)résoluble en Python:
quels chiffres faire correspondre aux lettres dans une expression du genre

VITE + BIEN = PAS ENSEMBLE

pour que les nombres obtenus respectent l’égalité.
Je ne me rappelle plus où j’ai vu ça et comment c’était résolu.

Je me lance dans l’examen du problème dans le lien. Je vais essayer de formaliser ça en Python.
Mais je n’ai pas l’intention d’y passer 3 jours.

Ça intéresse quelqu’un ?

**eyquem** · 21/07/2010, 19h43

J’ai écrit ça pour le moment:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
L = [0,'d','a','c','d','d','e','b','c','a','a','b','d','e','c','a','d','a','b','c','d']
print len(L[1:])
 
 
#1
if L.index('b') in (1,2,3,4,5):
    L[1] = ' abcde'[L.index('b')]
 
#2
gt = ''.join( str(i)+str(i+1) for i in xrange(1,20) if L[i]==L[i+1] )
if gt in ('67','78','89','910','1011'):
    L[2] = ('67','78','89','910','1011').index(gt)
 
 
#3
ne3 = L.count('e')
if ne3 in (0,1,2,3,4):
    L[3] = ne3
 
#4
ne = L.count('a')
if ne in (4,5,6,7,8):
    L[4] = ne4

La liste L est une valeur quelconque provisoire.

Le premier élément occupe l’indice 0 pour que les indices correspondent aux numéros de questions.

Mon idée est, qu’une fois formalisées en Python toutes les questions-réponses, de faire du brute-force en faisant varier L.

Tout en ajoutant des instructions pour éviter d’examiner des pistes qui n’ont aucun sens.

Je sais bien que le problème est sensé être résoluble par seule réflexion, mais je n’ai pas envie de réfléchir.... et je suis parti au petit bonheur la chance sans réfléchir

**Zavonen** · 21/07/2010, 20h05

VITE + BIEN = PAS ENSEMBLE

La substitution d'un chiffre à une lettre donne à gauche la somme de deux nombres, mais que penser du membre de droite et de la signification de l'espace ???
Je ne comprends pas

**rambc** · 21/07/2010, 20h27

Envoyé par Zavonen

La substitution d'un chiffre à une lettre donne à gauche la somme de deux nombres, mais que penser du membre de droite ... ???

L'exemple proposé par eyquem ne trouvera pas de solution car 9999 + 99999 = 199998 où la somme a au maximum six chiffres. Par contre, SEND + MORE = MONEY fonctionne car 9567 + 1085 = 10652.

Envoyé par Zavonen

...et de la signification de l'espace ???

On ne s'occupe pas des espaces tout simplement.

**Zavonen** · 21/07/2010, 20h52

Voici un code 'force brute' permettant de générer toutes les valeurs possibles d'un mot en assignant une valeur chiffrée à toute lettre de ce mot:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def listcar(S):
    """retourne la liste des caractères de S sans doublons"""
    return list(set(list(S)))
 
def value (S,D):
    """S est une chaîne, D un dictionnaire assignant une valeur chiffre à tout caractère de D, retourne la valeur de S"""
    if len(S)==1:
        return D[S[0]]
    else:
        long=len(S)-1
        n=value(S[1:],D)
        return n+D[S[0]]*10**long
 
def dico(L,V):
    """Retourne le dictionnaire associant chaque élément de L aux chiffres de V dans le même ordre"""
    D={}
    n=len(L)
    for i in range(0,n):
        D[L[i]]=V[i]
    return D
 
 
def brute1(n):
    """Brute force :retourne un itérateur: Toutes les listes de n chiffres possibles"""
    if n==1:
        return ([x] for x in xrange(0,10))
    else:
        I=brute1(n-1)
        return (x+[y] for x in I for y in xrange(0,10))
 
def brute2(L):
    """Brute force: Retourne tous les dictionnaires réalisant des mappages des éléments de L"""
    n=len(L)
    BF1=brute1(n)
    return (dico(L,V) for V in BF1)
 
def brute3(S):
    """Brute force: retourne toutes les valeurs possibles de L pour tous les mappages possibles de ses lettres sur des chiffres"""
    L=listcar(S)
    BF2=brute2(L)
    return (value(S,D) for D in BF2)
 
 
 
for z in brute3('VTT'):
    print z

**eyquem** · 21/07/2010, 20h55

Citation:
VITE + BIEN = PAS ENSEMBLE

La substitution d'un chiffre à une lettre donne à gauche la somme de deux nombres, mais que penser du membre de droite et de la signification de l'espace ???
Je ne comprends pas

j’ai écrit ça vite
c’est vrai qu’un espace n’a pas de sens
ou alors écrire PAS+ENSEMBLE

C’était pour signaler que l’intérêt est quand les mots ont à voir ensemble.
Dans la page que j’avais lue un jour, il était surprenant de voir qu’on arrivait à trouver des correspondances de chiffres pour des associations de mots qui avaient ensemble un sens.

rambc :

ah yes ! très bien

**Zavonen** · 21/07/2010, 21h25

Voici le programe qui résout SEND+MORE=MONEY
Astuce: on a forcément M=1 (retenue) qui divise par 10 le temps de traitement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def listcar(S):
    """retourne la liste des caractères de S sans doublons"""
    return list(set(list(S)))
 
def value (S,D):
    """S est une chaîne, D un dictionnaire assignant une valeur chiffre à tout caractère de D, retourne la valeur de S"""
    if len(S)==1:
        return D[S[0]]
    else:
        long=len(S)-1
        n=value(S[1:],D)
        return n+D[S[0]]*10**long
 
def dico(L,V):
    """Retourne le dictionnaire associant chaque élément de L aux chiffres de V dans le même ordre"""
    D={}
    n=len(L)
    for i in range(0,n):
        D[L[i]]=V[i]
    return D
 
 
def brute1(n):
    """Brute force :retourne un itérateur: Toutes les listes de n chiffres possibles"""
    if n==1:
        return ([x] for x in xrange(0,10))
    else:
        I=brute1(n-1)
        return (x+[y] for x in I for y in xrange(0,10))
 
def brute2(L):
    """Brute force: Retourne tous les dictionnaires réalisant des mappages des éléments de L"""
    n=len(L)
    BF1=brute1(n)
    return (dico(L,V) for V in BF1)
 
def brute3(S1,S2,S3):
    """Brute force: retourne toutes les valeurs possibles de L pour tous les mappages possibles de ses lettres sur des chiffres"""
    L=listcar(S1+S2+S3)
    BF2=brute2(L)
    BF3=(D for D in BF2 if D['M']==1)
    return ((value(S1,D),value(S2,D),value(S3,D)) for D in BF3)
 
X=brute3('SEND','MORE','MONEY')
for x in X:
    if x[0]+x[1]==x[2]:
        print x

Version compacte:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
def value (S,D):
    return D[S[0]] if len(S)==1 else value(S[1:],D)+D[S[0]]*10**(len(S)-1)
 
def brute1(n):
    return ([x] for x in xrange(0,10)) if n==1 else (x+[y] for x in brute1(n-1) for y in xrange(0,10))
 
def brute3(S1,S2,S3):
    L=list(set(list(S1+S2+S3)))
    return ((value(S1,D),value(S2,D),value(S3,D)) for D in (E for E in (dict(zip(L,V)) for V in brute1(len(L))) if E['M']==1))
 
print [x for x in brute3('SEND','MORE','MONEY') if x[0]+x[1]==x[2]]

Résultat:

[(9000, 1000, 10000), (9010, 1090, 10100), (9001, 1000, 10001), (9011, 1090, 10101), (9002, 1000, 10002), (9012, 1090, 10102), (9003, 1000, 10003), (9013, 1090, 10103), (9004, 1000, 10004), (9014, 1090, 10104), (9005, 1000, 10005), (9015, 1090, 10105), (9006, 1000, 10006), (9016, 1090, 10106), (9007, 1000, 10007), (9017, 1090, 10107), (9008, 1000, 10008), (9018, 1090, 10108), (9009, 1000, 10009), (9019, 1090, 10109), (9110, 1001, 10111), (9120, 1091, 10211), (9111, 1001, 10112), (9121, 1091, 10212), (9112, 1001, 10113), (9122, 1091, 10213), (9113, 1001, 10114), (9123, 1091, 10214), (9114, 1001, 10115), (9124, 1091, 10215), (9115, 1001, 10116), (9125, 1091, 10216), (9116, 1001, 10117), (9126, 1091, 10217), (9117, 1001, 10118), (9127, 1091, 10218), (9118, 1001, 10119), (9128, 1091, 10219), (9129, 1081, 10210), (9220, 1002, 10222), (9230, 1092, 10322), (9221, 1002, 10223), (9231, 1092, 10323), (9222, 1002, 10224), (9232, 1092, 10324), (9223, 1002, 10225), (9233, 1092, 10325), (9224, 1002,
10226), (9234, 1092, 10326), (9225, 1002, 10227), (9235, 1092, 10327), (9226, 1002, 10228), (9236, 1092, 10328), (9227, 1002, 10229), (9237, 1092, 10329), (9238, 1082, 10320), (9239, 1082, 10321), (9330, 1003, 10333), (9340, 1093, 10433), (9331, 1003, 10334), (9341, 1093, 10434), (9332, 1003, 10335), (9342, 1093, 10435), (9333, 1003, 10336), (9343, 1093, 10436), (9334, 1003, 10337), (9344, 1093, 10437), (9335, 1003, 10338), (9345, 1093, 10438), (9336, 1003, 10339), (9346, 1093, 10439), (9347, 1083, 10430), (9348, 1083, 10431), (9349, 1083, 10432), (9440, 1004, 10444), (9450, 1094, 10544), (9441, 1004, 10445), (9451, 1094, 10545), (9442, 1004, 10446), (9452, 1094, 10546), (9443, 1004, 10447), (9453, 1094, 10547), (9444, 1004, 10448), (9454, 1094, 10548), (9445, 1004, 10449), (9455, 1094, 10549), (9456, 1084, 10540), (9457, 1084, 10541), (9458, 1084, 10542), (9459, 1084, 10543), (9550, 1005, 10555), (9560, 1095, 10655), (9551, 1005, 10556), (9561, 1095, 10656), (9552, 1005, 10557), (956
2, 1095, 10657), (9553, 1005, 10558), (9563, 1095, 10658), (9554, 1005, 10559), (9564, 1095, 10659), (9565, 1085, 10650), (9566, 1085, 10651), (9567, 1085, 10652), (9568, 1085, 10653), (9569, 1085, 10654), (9660, 1006, 10666), (9670, 1096, 10766), (9661, 1006, 10667), (9671, 1096, 10767), (9662, 1006, 10668), (9672, 1096, 10768), (9663, 1006, 10669), (9673, 1096, 10769), (9674, 1086, 10760), (9675, 1086, 10761), (9676, 1086, 10762), (9677, 1086, 10763), (9678, 1086, 10764), (9679, 1086, 10765), (9770, 1007, 10777), (9780, 1097, 10877), (9771, 1007, 10778), (9781, 1097, 10878), (9772, 1007, 10779), (9782, 1097, 10879), (9783, 1087, 10870), (9784, 1087, 10871), (9785, 1087, 10872), (9786, 1087, 10873), (9787, 1087, 10874), (9788, 1087, 10875), (9789, 1087, 10876), (9880, 1008, 10888), (9890, 1098, 10988), (9881, 1008, 10889), (9891, 1098, 10989), (9892, 1088, 10980), (9893, 1088, 10981), (9894, 1088, 10982), (9895, 1088, 10983), (9896, 1088, 10984), (9897, 1088, 10985), (9898, 1088, 1098
6), (9899, 1088, 10987), (9990, 1009, 10999), (9900, 1199, 11099), (9901, 1189, 11090), (9902, 1189, 11091), (9903, 1189, 11092), (9904, 1189, 11093), (9905, 1189, 11094), (9906, 1189, 11095), (9907, 1189, 11096), (9908, 1189, 11097), (9909, 1189, 11098)]

NB A la différence du code de "dive into python" ce code recherche toutes les solutions et pas seulement celles pour lesquelles les valeurs assignées à des lettres différentes sont des chiffres différents. Pour cet exemple le premier calcul fait une itération sur 43320 éléments dans le premier cas et 100000000 dans le second.

**rambc** · 21/07/2010, 20h14

Envoyé par eyquem

Ça me rappelle un type de problème “facilement“ (?)résoluble en Python:
quels chiffres faire correspondre aux lettres dans une expression du genre

VITE + BIEN = PAS ENSEMBLE

pour que les nombres obtenus respectent l’égalité.
Je ne me rappelle plus où j’ai vu ça et comment c’était résolu.

Peut-être ici...

un casse-tête auto-référentiel: sic

Python

Vue hybride

Discussions similaires

Partager

Partager