Bonjour Jean-Marc,

Chez moi ton code n'a pas trouvé 6 avec [1, 1, 1, 1, 1, 1].

J'ai voulu écrire la version la plus courte possible et la plus rapide possible.
Le code que je propose ne cherche pas les solutions approchés :

def diabolik(target,list) $h={};_diabolik(target,[0]+list,0,0,0) end

def _diabolik(t,l,j,i,r)
if (l[j]=r) && (l[i]=0) && (l=l-[0]).size > 1 && !$h[l=l.sort] && $h[l]=true
for i in 0..sz=l.size-2; for j in i.next..sz.next
for r in [['+',l[j]+l[i]],['*',l[j]*l[i]],['-',l[j]-l[i]],['/',l[j]%l[i]==0?l[j]/l[i]:0]]
if (t==r[1] && (s='Compte est bon !')) || (sz!=0 && (s=_diabolik(t,l.clone,j,i,r[1])))
return [format("%d=%d%s%d",r[1],l[j],r[0],l[i]),s]
end; end; end; end; end
false
end

puts diabolik(957, [1, 1, 25, 50, 75, 100]), Process.times.utime

@+
Christian Blanvillain.

Merci pour votre réponse Christian,

En effets le code proposé ne peut trouver 6 avec [1,1,1,1,1,1]... problème qui ne se pose pas selon les règles des chiffres et des lettres puisque chaque nombre n'est tiré qu'une seule fois.

Ceci dit, votre code est en effets très rapide, pour un même problème mon code prends jusqu'à 11 secondes pour résoudre un problème qui en prends 0.0346 secondes, et très compact. Dommage qu'il soit compact au point d'obscurcir certains détails de l'implémentation.

Merci pour votre réponse... ce serait intéressant de voir la même vitesse avec un compte approchant, qui est après tout la 2e façon de gagner lorsqu'on joue à "Des chiffres et des lettres"

Jean-Marc

Bonjour Jean-Marc,

Je viens juste de lire votre réponse. Merci.

Avez-vous bien regardé le résultat proposé par votre code pour 957 avec [1, 1, 25, 50, 75, 100] ? S'il ne trouve pas la solution c'est à cause de explore_espace_solution_etendu(selected + [[o,n]], available - [n]) qui supprime *toutes* les occurrences de [n] dans la liste available. Vous devriez aussi changer numbers = [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,25,50,75,100] car les nombres de 1 à 10 peuvent être à doubles (http://cybercl.free.fr/reglem/freglem.html).

Voici une nouvelle version plus compréhensible de mon algorithme. Cette fois-ci je fournis un résultat approché lorsqu'il n'y a pas de solution.


def allegro(target, list) # Initialisation des variables globales.
$hash = {} # Permet d'eliminer les branches de calculs deja effectues.
@solution = [] # Affichage final du detail des operations.
@min = target # La plus petite difference entre les valeurs trouvees et la valeur recherchee.
recu(target, list.sort, []) # Trier la liste des nombres permet d'éliminer plus de branches de recherche avec la hash table.
puts @solution.to_s # Solution la plus proche.
puts Process.times.utime # Chrono.
end


def recu(target, list, calculs) # Nombre recherche, Liste des candidats, Detail des calculs.
if !$hash[list] # La liste des nombres a telle deja ete rencontree ? Si oui, inutile de refaire les calculs.
$hash[list] = true # Memorise la nouvelle liste.
for i in 0..list.size-2; for j in i+1..list.size-1 # Toutes les paires possibles.
for res in [[:+,list[j]+list[i]], [:*,list[j]*list[i]], [:-,list[j]-list[i]], [:/,list[j]%list[i]==0?list[j]/list[i]:0]]
if res[1] != 0 # Pour les 4 operations res[0]: nom de l'operateur, res[1]: valeur effective calculee.
new_list = list.clone << res[1] # Nouvelle liste de nombres avec nouvelle valeur calculee.
new_list.delete_at(j) ; new_list.delete_at(i) # Supprime les operandes utilisees dans le calcul.
if (res[1] - target).abs < @min # Recherche meilleure solution approchee.
@min = (res[1] - target).abs # @min est nul si la solution est trouvee.
@solution = [calculs, [res[1],'=',list[j],res[0],list[i],"\n"]] # Detail du calcul effectuee.
end # Appel recursif si solution pas trouvee et s'il reste plus d'un element dans la liste des nombres.
if (@min == 0) || (new_list.size>1 && recu(target, new_list.sort, [calculs, [res[1],'=',list[j],res[0],list[i],"\n"]]))
return true # Solution trouvee.
end; end; end; end; end; end
return false # Pas trouve.
end


allegro(666, [1, 2, 3, 4, 5, 6 ]) # Pas de solution.
allegro(947, [1, 3, 7, 7, 8, 50]) # Une solution unique existe.


Si la version "allegro" est quasiment aussi rapide que la version "diabolik" c'est parceque les performances de "diabolik" peuvent encore être améliorées d'approximativement 22%. Je vous laisse le plaisir de trouver ce qu'il faut changer !

Amusez-vous bien,
Christian Blanvillain
mail:/blanvill/gmail/com