0

我被这个问题陈述所困扰，我的代码确实有效，但我使用itertools.permutations了它，这使得它非常慢。此外，我不知道如何使它适用于所有或任何输入。我想我必须使用回溯，但我没有在这里使用如何使用它。

欢迎任何有价值的建议或建议或代码。是的，这是一项任务，我不是要完整的代码。谢谢！

这是问题陈述：

用不同的数字（0, 1, 2, .., 9）代替下面的不同字母，这样对应的加法正确，得到的MONEY值尽量大。价值是什么？

SHOW + ME + THE = 钱

有 3 个解满足方程：10376、10267、10265。因此，正确的一个是（最大的）10376。如果有多个映射评估为相同的最大值，则将它们全部输出。

那作业：

用 Python 写一个程序，总能找到这类问题的正确解决方案。

import time
import itertools


def timeit(fn):
    def wrapper():
        start = time.clock()
        ret = fn()
        elapsed = time.clock() - start
        print("%s took %2.fs" % (fn.__name__, elapsed))
        return ret
    return wrapper


@timeit
def solve1():
    for s in range(1, 10):
        for e in range(0, 10):
            for n in range(0, 10):
                for d in range(0, 10):
                    for m in range(1, 10):
                        for o in range(0, 10):
                            for r in range(0, 10):
                                for y in range(0, 10):
                                    if distinct(s, e, n, d, m, o, r, y):
                                        send = 1000 * s + 100 * e + 10 * n + d
                                        more = 1000 * m + 100 * o + 10 * r + e
                                        money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
                                        if send + more == money:
                                            return send, more, money


def distinct(*args):
    return len(set(args)) == len(args)


@timeit
def solve2():
    #letters = input("Enter your string: ")
    #letters1 = list(letters)
    letters = ('s', 'h', 'o', 'w', 'm', 'e', 't')
    digits = range(10)
    for perm in itertools.permutations(digits, len(letters)):
        sol = dict(zip(letters, perm))
        if sol['s'] == 0 or sol['m'] == 0:
            continue
        send = 1000 * sol['s'] + 100 * sol['e'] + 10 * sol['n'] + sol['d']
        more = 1000 * sol['m'] + 100 * sol['o'] + 10 * sol['r'] + sol['e']
        money = 10000 * sol['m'] + 1000 * sol['o'] + 100 * sol['n'] + 10 * sol['e'] + sol['y']
        if send + more == money:
            return send, more, money


print(solve1())
print(solve2())
4

2 回答 2

1

我以您的solve2方法为起点，为方程式实现了一个简单的解析器'word [+ word]*n = word'。该函数get_value在将 word 中的所有字母替换为其相关数字后计算得到的整数值。其余的只是像您一样进行排列，并将左侧单词的总和与右​​侧单词进行比较。

这是代码：

import itertools


def get_value(word, substitution):
    s = 0
    factor = 1
    for letter in reversed(word):
        s += factor * substitution[letter]
        factor *= 10
    return s


def solve2(equation):
    # split equation in left and right
    left, right = equation.lower().replace(' ', '').split('=')
    # split words in left part
    left = left.split('+')
    # create list of used letters
    letters = set(right)
    for word in left:
        for letter in word:
            letters.add(letter)
    letters = list(letters)

    digits = range(10)
    for perm in itertools.permutations(digits, len(letters)):
        sol = dict(zip(letters, perm))

        if sum(get_value(word, sol) for word in left) == get_value(right, sol):
            print(' + '.join(str(get_value(word, sol)) for word in left) + " = {} (mapping: {})".format(get_value(right, sol), sol))

if __name__ == '__main__':
    solve2('SEND + MORE = MONEY')

如果您只对正确单词的最大值感兴趣，您可以更改排列，使其从正确单词的最高数字开始（例如 MONEY 的 98765）并逐个向下直到找到第一个匹配项。

回溯

好的，这里的想法是一个一个地建立替换，并检查每个步骤之间是否可以满足等式。

For example:
1. set S = 9
2. check if equation can be fulfilled:
    2.1. if yes: set a value for the next letter and go to 2
    2.2. if no: select next value for S

在这种情况下，检查方程是否可以满足并不是那么容易。

我会尝试以下方法：

min: range(10) 中到目前为止尚未用于替换的最小值

max: range(10) 中迄今为止尚未用于替换的最大值

用最小值/最大值替换左侧迄今为止尚未替换的每个字母，并将总和与替换为最大值/最小值后的右侧数字进行比较。

Example:
equation = 'SEND + MORE = MONEY'
1. substitute M = 2
2. check:
   max = 9, min = 0
   compare max on left side with min on right side: 9999 + 2999 = 20000
   compare min on left side with max on right side: 0000 + 2000 = 29999
   if max_left < min_right or min_left > max_right:
       the current chosen substitutions (M = 2 in this example) can not lead to a valid solution.

你明白吗？

于 2016-03-13T22:48:10.993 回答
1 
    def isCryptSolution(crypt, solution):
        newsol = list(zip(*reversed(solution)))
        newstring1 = ''
        total = 0
        for word in range(len(crypt)-1):
            subtotal, sol_total = 0, 0
            newstring = ''
            for char in crypt[word]:
                idx = newsol[0].index(char)
                newstring = newstring + newsol[1][idx]
                subtotal = int(newstring)
                # if newstring[0] == '0':
                #     return False
            total = total + subtotal
        for char1 in crypt[-1]:
            nidx = newsol[0].index(char1)
            newstring1 = newstring1 + newsol[1][nidx]
            sol_total = int(newstring1)
        if total == sol_total and newstring[0] != '0':
            return True
        elif total == 0 and newstring[0] == '0' and len(newstring) == 1:
            return True
        else:
            return False

crypt = ["SEND", "MORE", "MONEY"]
solution = [['O', '0'],
            ['M', '1'],
            ['Y', '2'],
            ['E', '5'],
            ['N', '6'],
            ['D', '7'],
            ['R', '8'],
            ['S', '9']]

isCryptSolution(crypt, solution)
于 2018-03-27T16:16:07.140 回答