Python 3 中的密码谜题通用解决方案

Question

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

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

这里是问题陈述：

Substitute different digits (0, 1, 2, .., 9) for different letters below, so that the corresponding addition is correct, and the resulting value of M O N E Y is as large as possible. What is the value?

SHOW + ME + THE = MONEY

满足方程的解有3个：10376、10267、10265，所以正确的解是（最大的）10376。如果有多个映射的最大值相同，则全部输出。

作业：

Write a program in Python, which can always find the correct solution for this kind of problem.

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())

Answer 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')

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

回溯

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

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) 中迄今为止尚未用于替换的最大值

用 min/max 值替换左侧的每个字母，并将总和与替换为 max/min 值后右侧的数字进行比较。

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.

你明白了吗？

Answer 2

    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)

Python 3 中的密码谜题通用解决方案

Cryptarithmetic puzzle generic solution in Python 3

python

algorithm

python-3.x

recursive-backtracking

cryptarithmetic-puzzle