Solving Puzzle in Python
Question: I got one puzzle and I want to solve it using 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?

Now I wanted to solve this in Python.

The only constraint i got from the puzzle is that sum of 4 pieces is 40. With
that I could filter all the set of 4 values whose sum is 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`

Now I need to check each set of values in `comb` and try all the combination
of operations.

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.

I tried a lot, but i am stuck at this stage, ie how to check all these
combination of calculations to each set of 4 values.

**Question :**

1) I think i need to get a list all possible combination of `[a,b,c,d] and
[+,-]`.

2) does anyone have a better idea and tell me how to go forward from here?

Also, I want to do it completely without help of any external libraries, need
to use only standard libraries of python.

**EDIT** : Sorry for the late info. Its answer is (1,3,9,27), which I found a
few years back. I have checked and verified the answer.

EDIT : At present, `fraxel`'s answer works perfect with `time = 0.16 ms`. A
better and faster approach is always welcome.

Regards

ARK


Answer: **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!!

