J'essaie de résoudre le problème suivant:

A store sells large individual wooden letters for signs to put on houses. 
The letters are priced individually.
The total cost of letters in LOAN is 17 dollars.
The total cost of letters in SAM is 18 dollars.
The total cost of letters in ANNA is 20 dollars.
The total cost of letters in ROLLO is 21 dollars.
The total cost of letters in DAMAGES is 30 dollars.
The total cost of letters in SALMON is 33 dollars.

How much would the letters in the name GARDNER cost?

Je force le coût brut des lettres avec le code python suivant, mais il faut des heures et des heures pour converger, car il existe 33 ^ 10 combinaisons possibles à tester. J'utilise n = 33 car c'est le coût maximum d'un nom mais en effet, n peut être réduit à 15 voire 10, mais sans être sûr il convergera.

def func(letters):
    print letters
    if letters['L']+letters['O']+letters['A']+letters['N'] != 17:
        return False
    elif letters['S']+letters['A']+letters['M'] != 18:
        return False
    elif 2*letters['A']+2*letters['N'] != 20:
        return False
    elif letters['R']+2*letters['O']+2*letters['L'] != 21:
        return False
    elif letters['D']+2*letters['A']+letters['M']+letters['G']+letters['E']+letters['S'] != 30:
        return False
    elif letters['S']+letters['A']+letters['L']+letters['M']+letters['O']+letters['N'] != 33:
        return False
    return True

def run(letters, n, forbidden_letters):
    for letter in letters.keys():
        if letter not in forbidden_letters:
            for i in range(1, n):
                letters[letter] = i
                if not func(letters):
                    if letter not in forbidden_letters:
                        forbidden_letters+=letter
                    if run(letters, n, forbidden_letters):
                        return letters
                else:
                    return letters

LETTERS = {
    "L":1,
    "O":1,
    "A":1,
    "N":1,
    "S":1,
    "M":1,
    "R":1,
    "D":1,
    "G":1,
    "E":1,
}
n=33
print run(LETTERS, n, "")

Le forçage brutal fonctionnera à la fin, mais il est si étendu en CPU qu'il n'est sûrement pas la meilleure solution.

Quelqu'un at-il une meilleure solution pour résoudre ce problème? Soit en réduisant le temps de calcul, soit par une bonne approche mathématique.

Merci a tous.

2
repié 17 mars 2019 à 19:34

2 réponses

Meilleure réponse

C'est ce qu'on appelle un système d'équations linéaires. Vous pouvez résoudre ce problème à la main si vous le souhaitez, mais vous pouvez également utiliser un solveur linéaire. Par exemple avec sympy

import sympy

l,o,a,n,s,m,r,d,g,e = sympy.symbols('l,o,a,n,s,m,r,d,g,e')

eq1 = l+o+a+n - 17
eq2 = s+a+m -18
eq3 = a+n+n+a -20
eq4 = r+o+l+l+o -21 
eq5 = d+a+m+a+g+e+s -30
eq6 = s+a+l+m+o+n- 33

sol, = sympy.linsolve([eq1,eq2,eq3,eq4,eq5,eq6],(l,o,a,n,s,m,r,d,g,e))
l,o,a,n,s,m,r,d,g,e = sol

print(g+a+r+d+n+e+r)

3

5
Christian Sloper 17 mars 2019 à 17:13
L + O + A + N - 17 = 0
S + A + M - 18 = 0
2 * A  + 2 * N - 20 = 0

Etc.

Essayez de créer une matrice comme:

 L O A N S M R D G E val
[1 1 1 1 0 0 0 0 0 0 -17 | 0] LOAN
[0 0 1 0 1 1 0 0 0 0 -18 | 0] SAM
[0 0 2 2 0 0 0 0 0 0 -20 | 0] ANNA
...
[0 0 1 1 0 0 2 1 1 2 -x | 0] GARDENER

Vous pouvez maintenant le résoudre en utilisant par exemple la méthode de Gauss. Cela prendra de la complexité en temps O (n ^ 3).

2
Maras 17 mars 2019 à 17:09