用Python解决谜题

Question

我有一个难题，我想用Python解决它。

Puzzle:

A merchant has a 40 kg weight which he used in his shop. Once, it fell from his hands and was broken into 4 pieces. But surprisingly, now he can weigh any weight between 1 kg to 40 kg with the combination of these 4 pieces.

So question is, what are weights of those 4 pieces?

现在我想用Python解决这个问题。

我从拼图中得到的唯一限制是4个拼图的总和是40。这样我就可以过滤4个值的总和为40的所有集合。

import itertools as it

weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]

length of comb = 297

现在我需要检查comb中的每一组值，并尝试所有操作的组合。

例如，如果(a,b,c,d)是comb中的第一组值，则需要检查a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........等。

我试了很多次，但仍停留在这个阶段。

问题：

1）我想我需要一个列表，列出所有可能的[a,b,c,d] and [+,-]组合。

2）有没有人有更好的主意，告诉我如何从这里开始？

另外，我想完全不需要任何外部库的帮助，只需要使用python的标准库。

编辑：抱歉，信息迟了。它的答案是（1,3,9,27），这是我几年前发现的。我已经核实了答案。

编辑：目前，fraxel的答案与time = 0.16 ms完美结合。更好更快的方法总是受欢迎的。

问候

方舟

Answer 1

下面是一个强力itertools解决方案：

import itertools as it

def merchant_puzzle(weight, pieces):
    full = range(1, weight+1)
    all_nums = set(full)
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight]
    funcs = (lambda x: 0, lambda x: x, lambda x: -x)
    for c in comb:
        sums = set()
        for fmap in it.product(funcs, repeat=pieces):
            s = sum(f(x) for x, f in zip(c, fmap))
            if s > 0:
                sums.add(s)
                if sums == all_nums:
                    return c

>>> merchant_puzzle(40, 4)
(1, 3, 9, 27)

要了解其工作原理，请查看the answer Avaris gave，这是同一算法的实现。

Answer 2

你很接近，非常接近：）。

既然这是你想解决的难题，我就给你指点。对于本部分：

Eg if (a,b,c,d) is the first set of values in comb, i need to check a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........ and so on.

考虑一下：每个重量可以放在一个秤上，也可以放在另一个秤上，或者两者都不放。所以对于a的情况，这可以表示为[a, -a, 0]。其他三个也一样。现在您需要所有可能的配对，每个权重有这3种可能（提示：itertools.product）。那么，一个可能的配对度量（比如说：(a, -b, c, 0)）仅仅是这些的总和（a-b+c+0）。

剩下的就是检查你是否能“测量”所有需要的重量。set可能在这里派上用场。

注：如评论中所述，一般情况下，这些分开的权重可能不需要是不同的（对于这个问题来说是不同的）。你可以重新考虑itertools.combinations。

Answer 3

你很接近，非常接近：）。

既然这是你想解决的难题，我就给你指点。对于本部分：

Eg if (a,b,c,d) is the first set of values in comb, i need to check a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........ and so on.

考虑一下：每个重量可以放在一个秤上，也可以放在另一个秤上，或者两者都不放。所以对于a的情况，这可以表示为[a, -a, 0]。其他三个也一样。现在你需要所有可能的配对，每个权重有3种可能（提示：itertools.product）。那么，一个可能的配对度量（比如说：(a, -b, c, 0)）仅仅是这些的总和（a-b+c+0）。

剩下的就是检查你是否能“测量”所有需要的重量。set可能在这里派上用场。

注：如评论中所述，一般情况下，这些分开的权重可能不需要是不同的（对于这个问题来说是不同的）。你可以重新考虑itertools.combinations。

Answer 4

早些时候穿过一个电源：

我们知道a*A + b*B + c*C + d*D = x对于0到40之间的所有x，并且a, b, c, d仅限于-1, 0, 1。很明显。下一种情况是x = 39，所以很明显最小的移动是删除一个元素（这是唯一可能导致与39成功平衡的移动）：

A + B + C = 39，所以D = 1，根据需要。

下一步：

A + B + C - D = 38

下一步：

A + B + D = 37，所以C = 3

然后：

A + B = 36

然后：

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31，所以A = 9

因此B = 27

所以权重是1, 3, 9, 27

事实上，这可以从它们都必须是3的倍数这一事实立即推断出来。

有趣的更新：

因此，下面是一些python代码，用于为任何将跨越该空间的掉下来的权重找到最小权重集：

def find_weights(W):
    weights = []
    i = 0
    while sum(weights) < W:
        weights.append(3 ** i)
        i += 1
    weights.pop()
    weights.append(W - sum(weights))
    return weights

print find_weights(40)
#output:
[1, 3, 9, 27]

为了进一步说明这个解释，我们可以把这个问题看作是跨越数字空间[0, 40]的最小权重数。很明显，你可以用每个重量做的事情是三元/三元的（增加重量，去掉重量，把重量放在另一边）。因此，如果我们按降序写下（未知的）权重(A, B, C, D)，我们的动作可以总结为：

    ABCD:   Ternary:
40: ++++     0000
39: +++0     0001
38: +++-     0002
37: ++0+     0010
36: ++00     0011
35: ++0-     0012
34: ++-+     0020
33: ++-0     0021
32: ++--     0022
31: +0++     0100
etc.

我把从0到9的三元数列放在一起，以说明我们是有效的三元数系统（基3）。我们的解决方案通常可以写成：

3**0 + 3**1 +3**2 +...+ 3**N >= Weight

对于最小的N，这是正确的。最小解总是这种形式。

此外，我们可以轻松地解决大重量的问题，并找到跨越空间的最小件数：

一个男人把一个已知的重量W掉下来，它就碎了。他的新重量允许他称任何重量到W。有多少重量，它们是什么？

#what if the dropped weight was a million Kg:
print find_weights(1000000)
#output:
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839]

试着用一个大重量和未知数量的碎片排列！！