Как решить эту проблему, не прибегая к брут-форсингу и / или не имея большого времени на вычисления?

Question

Я пытаюсь решить следующую проблему:

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?

Я стою перебор букв со следующим кодом Python, но это сходится часами, так как их 33 ^ 10 возможнокомбинации для тестирования.Я использую n = 33, так как это максимальная стоимость имени, но на самом деле n можно уменьшить до 15 или даже 10, но без сужения оно будет сходиться.

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, "")

Брутфорсинг будет работать вконец, но он настолько загружен процессором, что это, безусловно, не лучшее решение.

У кого-нибудь есть лучшее решение для решения этой проблемы?Либо за счет сокращения времени вычислений, либо с помощью хорошего математического подхода.

Спасибо всем.

Answer 1

Это то, что называется системой линейных уравнений. Вы можете решить это вручную, если хотите, но вы также можете использовать линейный решатель. Например с симпой

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)

Линейные уравнения могут быть решены очень быстро. Сложность O (n ³ ), где n - количество переменных. Так что для такой маленькой проблемы, как эта, она почти мгновенная.

Answer 2

L + O + A + N - 17 = 0
S + A + M - 18 = 0
2 * A  + 2 * N - 20 = 0

и т. Д.

Попробуйте создать такую ​​матрицу, как:

 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

Теперь вы можете решить ее, например, методом Гаусса.Это займет O (n ^ 3) временную сложность.