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

Version imprimable

21/07/2010, 20h07
eyquem

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

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 ?

J’ai écrit ça pour le moment:
Code:

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

21/07/2010, 21h05
Zavonen

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
21/07/2010, 21h14
rambc

Citation:

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...
21/07/2010, 21h27
rambc

Citation:

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.

Citation:

Envoyé par Zavonen

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

On ne s'occupe pas des espaces tout simplement.

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:

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

21/07/2010, 21h55
eyquem

Citation:

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

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:

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:

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:

Citation:

[(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.

Concernant le casse-tête auto-référentiel, je suis parvenu au code suivant:

Code:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
from time import strftime
 
L = ['0','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
L[9] = 'a'
L[10] = 'a'
L[16] = 'd'
print 'L[1:] =',L[1:]
print 'len(L[1:]) =',len(L[1:]),'\n'
 
nn = -1
for L[1] in 'acde':
    for L[2] in 'acde':
        for L[3] in'abcde':
            for L[4] in 'abcde':
                for L[5] in 'acde':
                    for L[6] in 'bd':
                        for L[8] in 'ace':
                            for L[11] in 'abcde':
                                for L[12] in 'abcde':
                                    for L[13] in 'abcde':
                                        for L[14] in 'abcde':
                                            for L[18] in 'abcde':
                                                for L[19] in 'abcde':
                                                    for L[20] in 'abcde':
                                                        nn += 1
                                                        if nn%100000==0:
                                                            print '\n'+str(nn).rjust(18) + '   ' + ''.join(L[1:6])+\
                                                                  ' '+''.join(L[6:11])+' '+''.join(L[11:16])+\
                                                                  ' '+''.join(L[16:])+strftime('   %d/%m/%Y %H:%M:%S')
                                                        elif nn%10000==0:
                                                            print str(nn).rjust(18) + '   ' + ''.join(L[1:6])+\
                                                                  ' '+''.join(L[6:11])+' '+''.join(L[11:16])+\
                                                                  ' '+''.join(L[16:])
 
 
                                                        if L[8]=='a':
                                                            L[7]='c'
                                                        if L[8]=='c':
                                                            L[7]='d'
                                                        L[15] = L[12]
                                                        L[17] = ('b','d')[L[6]=='b']
 
                                                        w1 = ('b' in L[3:5]) and (L[1]==' abcde'[L.index('b')])
                                                        gt = ''.join( str(i)+str(i+1) for i in xrange(1,20) if L[i]==L[i+1] )
                                                        w2 = gt in ('67','89','910','1011') and L[2]=='acde'[('67','89','910','1011').index(gt)]
                                                        ne3 = L.count('e')
                                                        w3 = ne3 in (0,1,2,3,4) and L[3]=='abcde'[ne3]
                                                        ne4 = L.count('a')
                                                        w4 = (ne4 in (4,5,6,7,8)) and (L[4]=='----abcde'[ne4])
                                                        w5 = (L[5]==L[1]=='a') or (L[5]==L[3]=='c)') or (L[5]==L[4]=='d') or (L[5]==L[5]=='e')
                                                        nv8 = sum(1 for x in xrange(1,21) if L[x] in ('a','e') )
                                                        w8 = (nv8 in (4,6,8)) and (L[8]=='----a-c-e'[nv8])
                                                        nb11 = (''.join(L[1:11])).count('b')
                                                        w11 = (nb11 in (0,1,2,3,4)) and (L[11]=='abcde'[nb11])
                                                        nc12 = sum(1 for i in xrange(1,21) if L[i] in 'bcd')
                                                        w12 = (nc12%2==1 and L[12]=='b') or (nc12%2==0 and L[12]=='a') or (nc12 in (1,4,9,16) and L[12]=='c') or (nc12 in (2,5,7,11,13,17,19) and L[12]=='d') or (nc12%5==0 and L[12]=='e')
                                                        odda = [ i for i in xrange(1,21,2) if L[i]=='a']
                                                        w13 = (len(odda)==1) and (odda in (9,11,13,15,17)) and (L[13]=='--------a-b-c-d-e'[odda[0]])
                                                        nd14 = sum(1 for x in xrange(1,21) if L[i]=='d')
                                                        tota = sum( 1 for i in xrange(1,21) if L[i] =='a' )
                                                        totb = sum( 1 for i in xrange(1,21) if L[i] =='b' )
                                                        totc = sum( 1 for i in xrange(1,21) if L[i] =='c' )
                                                        totd = sum( 1 for i in xrange(1,21) if L[i] =='d' )
                                                        tote = sum( 1 for i in xrange(1,21) if L[i] =='e' )
                                                        w14 = (nd14 in (6,7,8,9,10)) and (L[14]=='-----abcde')
                                                        w18 = ( tota==totb and L[18]=='a') or (tota==totc and L[18]=='b') or (tota==totd and L[18]=='c') or (tota==tote and L[18]=='d') or (tota not in (totb,totc,totd,tote) and L[18]=='e')
 
                                                        if all((w1,w2,w3,w4,w5,w8,w11,w12,w13,w14,w18)):
                                                            print 'j ai trouve L:\n',L
 
 
print strftime('\n%d/%m/%Y %H:%M:%S\n')                                                     
 
 
 
 
 
 
 
if 0:
 
    #1
    w1 = ('b' in L[3:5]) and (L[1]==' abcde'[L.index('b')])
    # 'b' pour les 1,2,5 sont impossibles
 
 
    #2
    # 'b' est impossible pour 2: cf 7 et 8
    gt = ''.join( str(i)+str(i+1) for i in xrange(1,20) if L[i]==L[i+1] )
    w2 = gt in ('67','89','910','1011') and L[2]=='acde'[('67','89','910','1011').index(gt)]
 
 
    #3
    ne3 = L.count('e')
    w3 = ne3 in (0,1,2,3,4) and L[3]=='abcde'[ne3]
 
    #4
    ne4 = L.count('a')
    w4 = (ne4 in (4,5,6,7,8)) and (L[4]=='----abcde'[ne4])
 
    #5
    w5 = (L[5]==L[1]=='a') or (L[5]==L[3]=='c)') or (L[5]==L[4]=='d') or (L[5]==L[5]=='e')
    # 'b' est impossible pour 5
 
    #6 #17
    # L[6] ne peut prendre que l'une de valeurs 'b' ou 'd'
    # et L[17] doit etre alors l'autre
    L[17] = ('b','d')[L[6]=='b']
 
 
    #7
    if L[8]=='a':
        L[7]='c'
    if L[8]=='c':
        L[7]='d'
 
    #8
    #r8 ne peut pas etre b ou d du fait de la question 7
    nv8 = sum(1 for x in xrange(1,21) if L[x] in ('a','e') )
    w8 = (nv8 in (4,6,8)) and (L[8]=='----a-c-e'[nv8])
 
    if L[7] in 'abe':
        L[8] = 'e'
 
    #9
    #i9 = '----------abcde'.index(L[9])
    #w9 = L[i9]==L[9]
    L[9] = 'a'
 
    #10
    L[10] = 'a'
    L[16] = 'd'
 
    #11
    print L
    nb11 = (''.join(L[1:11])).count('b')
    w11 = (nb11 in (0,1,2,3,4)) and (L[11]=='abcde'[nb11])
 
    #12
    nc12 = sum(1 for i in xrange(1,21) if L[i] in 'bcd')
    print nc12
    w12 = (nc12%2==1 and L[12]=='b') or (nc12%2==0 and L[12]=='a') or (nc12 in (1,4,9,16) and L[12]=='c') or (nc12 in (2,5,7,11,13,17,19) and L[12]=='d') or (nc12%5==0 and L[12]=='e')
 
    #13
    odda = [ i for i in xrange(1,21,2) if L[i]=='a']
    w13 = (len(odda)==1) and (odda in (9,11,13,15,17)) and (L[13]=='--------a-b-c-d-e'[odda[0]])
 
    #14
    nd14 = sum(1 for x in xrange(1,21) if L[i]=='d')
    w14 = (nd14 in (6,7,8,9,10)) and (L[14]=='-----abcde')
 
    #15
    L[15] = L[12]
 
    #16
    # cf plus haut
 
    #17
    # cf plus haut
 
    #18
    tota = sum( 1 for i in xrange(1,21) if L[i] =='a' )
    totb = sum( 1 for i in xrange(1,21) if L[i] =='b' )
    totc = sum( 1 for i in xrange(1,21) if L[i] =='c' )
    totd = sum( 1 for i in xrange(1,21) if L[i] =='d' )
    tote = sum( 1 for i in xrange(1,21) if L[i] =='e' )
    w18 = ( tota==totb and L[18]=='a') or (tota==totc and L[18]=='b') or (tota==totd and L[18]=='c') or (tota==tote and L[18]=='d') or (tota not in (totb,totc,totd,tote) and L[18]=='e')
 
    #19
    # no matters
 
    #20
    # quelconque

Il faudrait:

- vérifier que mon algorithme est bon

- vérifier que je ne me suis pas trompé dans l’écriture des instructions sensées traduire les questions

- exécuter ce code; ma machine est trop lente, ça va prendre 3 jours.

22/07/2010, 11h35
rambc

Bonjour.

Citation:

Envoyé par Zavonen

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 ce genre de casse-tête, deux lettres différentes correspondent toujours à deux chiffres différents.

PS : ces casse-têtes s'appellent des cryptarithmes en français. Le terme anglais "alphametic" semble réservé aux cryptarithmes qui ont une signification.

Mon programme s’approche de la barre de 60 millions de combinaisons examinées, en 9 heures d’exécution.

Il a examiné toutes les combinaisons avec les L[i] i>2 variées et L[1],L[2] == ’a’,’a’ en 7h3mn
Comme il doit examiner toutes les combinaisons avec L[1] dans 'acde’ et L[2] dans 'acde’ , il n’a fait en 7h3mn que le 1/16 de ce qu’il doit faire.
L’exécution complète devrait donc prendre 4 jours 17 heures.

Je vais l’arrêter pour lancer un code amélioré de façon à éviter de rentrer dans des itérations ne respectant pas les nombres min ou max de certaines réponses, indiquées dans les questions 3 (sur nombre de E), 4 (sur nombre de A), 8 9sur nombre de A+E), 14 (sur nombre de D) :

Code:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from time import strftime
 
L = ['0','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-','-']
L[9] = 'a'
L[10] = 'a'
L[16] = 'd'
print 'L[1:] =',L[1:]
print 'len(L[1:]) =',len(L[1:]),'\n'
 
 
def test(x):
    if x>=5  and  L[0:x+1].count('e')>4: return False
    if x>=10 and  L[0:x+1].count('a')>8: return False
    if x>=10 and (L[0:x+1].count('a')+L[0:x+1].count('e')>8): return False
    if x>=11 and  L[0:x+1].count('d')>10: return False
    if x>=11 and (L[0:x+1].count('b')+L[0:x+1].count('c')>10): return False
    return True
 
 
nn = -1
for L[1] in 'acde':
    for L[2] in 'acde':
        for L[3] in'abcde':
            for L[4] in 'abcde':
                for L[5] in 'acde':
                    #if L[0:6].count('e')<5:
                    if test(5):
                        for L[6] in 'bd':
                            # pas besoin de if test(6) car L[6] n'est jamais 'e'
                            for L[8] in 'ace':
                                if L[8]=='a': L[7]='c'
                                if L[8]=='c': L[7]='d'
                                # L[9]  = 'a'
                                # L[10] = 'a'
                                #if L[0:10].count('a')<9 and (L[0:10].count('a')+L[0:10].count('e')<9):
                                if test(10): # contient if test(8)
                                    for L[11] in 'abcde':
                                        if test(11):
                                        #if L[0:12].count('d')<11 and (L[0:12].count('b')+L[0:12].count('c')<11):
                                            for L[12] in 'abcde':
                                                if test(12):
                                                    for L[13] in 'abcde':
                                                        if test(13):
                                                            for L[14] in 'abcde':
                                                                L[15] = L[12]
                                                                # il faut que nd > 0
                                                                # L[16] = 'd'
                                                                if L[0:17].count('d')>1:
                                                                    L[17] = ('b','d')[L[6]=='b']
                                                                    if ( test(17) and L[0:18].count('a')>0 and L[0:18].count('d')>2 ):
                                                                        for L[18] in 'abcde':
                                                                            if test(18):
                                                                                for L[19] in 'abcde':
 
                                                                                    for L[20] in 'abcde':
 
                                                                                        nn += 1
                                                                                        if nn%100000==0:
                                                                                            print '\n'+str(nn).rjust(18) + '   ' + ''.join(L[1:6])+\
                                                                                                  ' '+''.join(L[6:11])+' '+''.join(L[11:16])+\
                                                                                                  ' '+''.join(L[16:])+strftime('   %d/%m/%Y %H:%M:%S')
                                                                                        elif nn%10000==0:
                                                                                            print str(nn).rjust(18) + '   ' + ''.join(L[1:6])+\
                                                                                                  ' '+''.join(L[6:11])+' '+''.join(L[11:16])+\
                                                                                                  ' '+''.join(L[16:])
 
                                                                                            ya  = L[0:19].count('a')
                                                                                            ye  = L[0:19].count('e')
                                                                                            yae = L[0:19].count('a')+L[0:19].count('e')
                                                                                            yd  = L[0:19].count('d')
                                                                                            ybc = L[0:19].count('b')+L[0:19].count('c')
                                                                                            print ya,ye,yae,yd,ybc,'  8 4 8 10 10'
 
                                                                                        w1 = ('b' in L[3:5]) and (L[1]==' abcde'[L.index('b')])
                                                                                        gt = ''.join( str(i)+str(i+1) for i in xrange(1,20) if L[i]==L[i+1] )
                                                                                        w2 = gt in ('67','89','910','1011') and L[2]=='acde'[('67','89','910','1011').index(gt)]
                                                                                        ne3 = L.count('e')
                                                                                        w3 = ne3 in (0,1,2,3,4) and L[3]=='abcde'[ne3]
                                                                                        ne4 = L.count('a')
                                                                                        w4 = (ne4 in (4,5,6,7,8)) and (L[4]=='----abcde'[ne4])
                                                                                        w5 = (L[5]==L[1]=='a') or (L[5]==L[3]=='c)') or (L[5]==L[4]=='d') or (L[5]==L[5]=='e')
                                                                                        nv8 = sum(1 for x in xrange(1,21) if L[x] in ('a','e') )
                                                                                        w8 = (nv8 in (4,6,8)) and (L[8]=='----a-c-e'[nv8])
                                                                                        nb11 = (''.join(L[1:11])).count('b')
                                                                                        w11 = (nb11 in (0,1,2,3,4)) and (L[11]=='abcde'[nb11])
                                                                                        nc12 = sum(1 for i in xrange(1,21) if L[i] in 'bcd')
                                                                                        w12 = (nc12%2==1 and L[12]=='b') or (nc12%2==0 and L[12]=='a') or (nc12 in (1,4,9,16) and L[12]=='c') or (nc12 in (2,5,7,11,13,17,19) and L[12]=='d') or (nc12%5==0 and L[12]=='e')
                                                                                        odda = [ i for i in xrange(1,21,2) if L[i]=='a']
                                                                                        w13 = (len(odda)==1) and (odda in (9,11,13,15,17)) and (L[13]=='--------a-b-c-d-e'[odda[0]])
                                                                                        nd14 = sum(1 for x in xrange(1,21) if L[i]=='d')
                                                                                        tota = sum( 1 for i in xrange(1,21) if L[i] =='a' )
                                                                                        totb = sum( 1 for i in xrange(1,21) if L[i] =='b' )
                                                                                        totc = sum( 1 for i in xrange(1,21) if L[i] =='c' )
                                                                                        totd = sum( 1 for i in xrange(1,21) if L[i] =='d' )
                                                                                        tote = sum( 1 for i in xrange(1,21) if L[i] =='e' )
                                                                                        w14 = (nd14 in (6,7,8,9,10)) and (L[14]=='-----abcde')
                                                                                        w18 = ( tota==totb and L[18]=='a') or (tota==totc and L[18]=='b') or (tota==totd and L[18]=='c') or (tota==tote and L[18]=='d') or (tota not in (totb,totc,totd,tote) and L[18]=='e')
 
                                                                                        if all((w1,w2,w3,w4,w5,w8,w11,w12,w13,w14,w18)):
                                                                                            print 'j ai trouve L:\n',L
 
 
print strftime('\n%d/%m/%Y %H:%M:%S\n')

Mais je n’ai pas réexaminé le code en détail pour essayer de vérifier si l’algorithme est bon.
Qu’est ce que vous en pensez ?

22/07/2010, 15h33
Zavonen

Citation:

Pour ce genre de casse-tête, deux lettres différentes correspondent toujours à deux chiffres différents.

Extrait du Wiki:

Citation:

Chaque lettre représente un seul chiffre et le chiffre le plus significatif est différent de zéro.

Je ne vois pas d'où tu sors ton affirmation,M peut représenter le seul chiffre 1 et N aussi. En fait on a une application d'un ensemble de lettres vers l'ensemble des 10 chiffres dont il est dit nulle part qu'elle doit être injective. A-tu vu des équations à deux inconnues en maths x et y où l'on suppose a priori que x est distinct de y ?
Cela dit, j'ai résolu avec plaisir et pour mon amusement SEND+MORE=MONEY mais à vrai dire je ne vois aucun rapport avec le problème posé par eyquem. Ce problème est difficile et je ne pense pas qu'une méthode exhaustive puisse en venir à bout (question de puissance de calcul). C'est un problème complexe à la fois amusant et intéressant pour lequel les méthodes de programmation 'logique' doivent prévaloir.
Désolé eyquem, mais je ne sais pas si ton code est bon et s'il a des chances de parvenir au résultat.
22/07/2010, 16h11
eyquem

Citation:

j'ai résolu avec plaisir et pour mon amusement SEND+MORE=MONEY mais à vrai dire je ne vois aucun rapport avec le problème posé par eyquem.

Pas par moi, mais par le post de developpez.com que j’ai donné.

Ce n’est pas absolument tout à fait sans rapport. Dans l’énoncé du casse-tête auto-réf , les questions 3 , 4, 8, 14 permettent de déduire des min et max pour les nombres totaux de E, de A, de E+A. de D dans les réponses. Il faut donc arriver à affecter des réponses de telles façons que des sommes donnent tel ou tel résultat. C’est un peu similaire à trouver des chiffres affectés à la place de lettres pour former des nombres dont la somme va être égale à un troisième mot transformé en lettres.

Mais je suis d’accord, ce n’est qu’un rapport assez vague. Et de toutes façons, il y a d’autres questions qui n’ont, elles, rien à voir avec des sommations, ce qui fait du casse-tête auto-réf un problème notablement différent des cryptarithmes.

Pas la peine de se casser la tête à essayer de creuser un rapport aussi ténu.

C’est dommage que le casse-tête semble n'intéresser personne.

1) On peut extraire des problèmes logiques indépendants de l’ensemble:

par exemple questions 7 et 8 ==> les réponses de 7 et 8 ne peuvent pas être quelconques, la réponse de dépend de celle de 8 et les seules réponses possibles pour 8 sont A et C.

De même, j’ai abouti aux conclusions que L[9] et L[10] valent toutes les deux A.

Quant à la question 1, elle entraine l’impossibilité d’avoir une réponse B aux questiona 1, 2 et 5.

Ces petites réflexions logiques isolées devraient intéresser des matheux.

2) J’ai voulu voir en combien de temps j’arriverai à formaliser et écrire un programme qui tourne pour la résolution de ce problème à la brute.
Mais en obtenant certaines simplifications en usant des conclusions logiques qu’on peut tirer sans trop se casser la tête des énoncés des questions.
Cela a été assez rapide.

En fait, j’aimerais bien pouvoir comparer la façon dont on obtient un tel programme en Python, comparativement à un autre langage.
Je suis arrivé à un premier code assez rapidement: grâce à Python.
Maintenant je fignole: possible aisément grâce à Python.
Sinon avec d’autres langages.... j’aimerais bien voir quelqu’un faire ça en C++.... ou en PHP, ou en Java...

------------------------------------

Mon premier programme avait commencé à examiner les combinaisons débutant par AAAEC au bout de la 7 970 000 ième combinison, après 1h15 d’exécution.

Mon second programme est arrivé au même stade après 325 000 combinaisons et 32 mn d’exécution.

Reste à savoir si mes instructions sont correctes.
22/07/2010, 16h35
kango

bonjour,

tout d'abord eyquem, je te déteste :mouarf:. J'étais tranquille chez moi et je me retrouve avec une énigme à la con que je ne peux pas ne pas résoudre arrgggg !!!

je viens de la résoudre avec papier crayon (ça m'a pris quelques heures quand même...:oops:). j'ai récupéré ton code mais je ne suis pas d'accord avec toi sur les hypothèses initiales.

je voulais brute-forcer au départ mais 95000 milliards de combinaisons, ça fait bobo. j'ai donc chercher à limiter autant que possibles les combinaisons possibles et de fil en aiguille je me suis retrouvé à le résoudre entièrement à la main.

j'ai même récupéré ton code (qui m'a mouliné 70 millions de combinaisons avant que j'arrête de le faire tourner) et j'ai modifié légèrement les conditions initiales. mais sans résultat probant pour le moment, il y a quelques tests qui ne me semblent pas ok.

j'essaierai de mettre une mise à jour.