Solving Puzzle in Python

Earlier walk-through anwswer:

We know a*A + b*B + c*C + d*D = x for all x between 0 and 40, and a, b, c, d are confined to -1, 0, 1. Clearly A + B + C + D = 40. The next case is x = 39, so clearly the smallest move is to remove an element (it is the only possible move that could result in successfully balancing against 39):

A + B + C = 39, so D = 1, by neccessity.

next:

A + B + C - D = 38

next:

A + B + D = 37, so C = 3

then:

A + B = 36

then:

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31, so A = 9

Therefore B = 27

So the weights are 1, 3, 9, 27

Really this can be deduced immediately from the fact that they must all be multiples of 3.

Interesting Update:

So here is some python code to find a minimum set of weights for any dropped weight that will span the space:

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]

To further illustrate this explaination, one can consider the problem as the minimum number of weights to span the number space [0, 40]. It is evident that the number of things you can do with each weight is trinary /ternary (add weight, remove weight, put weight on other side). So if we write our (unknown) weights (A, B, C, D) in descending order, our moves can be summarised as:

    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.

I have put ternary counting from 0 to 9 alongside, to illustrate that we are effectively in a trinary number system (base 3). Our solution can always be written as:

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

For the minimum N that this holds true. The minimum solution will ALWAYS be of this form.

Furthermore, we can easily solve the problem for large weights and find the minimum number of pieces to span the space:

A man drops a known weight W, it breaks into pieces. His new weights allow him to weigh any weight up to W. How many weights are there, and what are they?

#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]

Try using permutations for a large weight and unknown number of pieces!!

Here is a brute-force itertools solution:

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)

For an explanation of how it works, check out the answer Avaris gave, this is an implementation of the same algorithm.