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

• Jacob Mattison: The puzzle is trickier than that; I'm not sure you can easily brute-force it. The trick is that, to measure certain weights, he may need to add pieces of the weight to both sides of the scale. Think about a simpler version: break a 4-kg weight into 2 pieces that can measure any weight up to 4 kg. The answer is a 1 kg piece and a 3 kg piece. To measure 2 kg, you have to put one of the pieces on each side of the scale.
• Jeff Tratner: @JacobM has the best way to go: start with a simpler problem and see if you can't find a pattern that allows you to solve the more complex problem. Also, be aware that, unless you are sure that each weight is unique, combinations won't give you what you want. (to see this, try changing weight to 10 and full to range(1,10). easier to play around with what it does.)
• Abid Rahman K: @ JacobM...yeah.. of course.. ie the question. You can put weights on both sides of scale to get desired weight. ie i mentioned negative sign in question. ie a-b, a-b+c-d ..... minus denotes that weight put in other scale. I think i have to explain it in question. Thanks for notifying.
• jgritty: Read the question andrew, he wants to solve it using Python, and who are we to stop him!
• andrew cooke: ok, i deleted my comment in case it's an unwanted "spoiler" (sorry). if you want to know how to just write down the answer, email me.

Answer 1

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!!

• jgritty: A + B + C = 39, so D = 1, by necessity. I wasn't so sure about that. What if you had weights of 14 and 15, you could do 1 using those 2, one on each side, as 15-14 = 1. So not sure necessity is the right word.
• fraxel: @jgritty - but you can't get 39! If you are trying to weigh something that weighs 39, you're gonna need 3 elements for that :)
• jgritty: That's OK, I have 4! However, you obviously will run into a problem eventually.
• fraxel: @jgritty - er no, because the above method solves the problem: 1,3,9,27 :)
• fraxel: @Abid Rahman K - Cheers, :) I am going to provide a very interesting update to this answer with some code and more explanaition. It is a very fun problem. Using this method allows you to easily solve the problem: `A man drops a 1000000 Kg weight, his new weights allow him to weigh any weight up to 1000000 Kg! What are they, and how many are there?

Answer 2

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.

• Avaris: Wow! While I was writing the explanation, you were coding the same thing :).

Answer 3

You are close, very close :).

Since this is a puzzle you want to solve, I'll just give pointers. For this part:

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.

Consider this: Each weight can be put to one scale, the other or neither. So for the case of a, this can be represented as [a, -a, 0]. Same with the other three. Now you need all possible pairings with these 3 possibilities for each weight (hint: itertools.product). Then, a possible measuring of a pairing (lets say: (a, -b, c, 0)) is merely the sum of these (a-b+c+0).

All that is left is just checking if you could 'measure' all the required weights. set might come handy here.

PS: As it was stated in the comments, for the general case, it might not be necessary that these divided weights should be distinct (for this problem it is). You might reconsider itertools.combinations.

• Abid Rahman K: +1 - this can be represented as [a, -a, 0]. This trick didn't come to my mind. That one single statement is the turning point. Thank you.

Answer 4

I brute forced the hell out of the second part.

Do not click this if you don't want to see the answer. Obviously, if I was better at permutations, this would have required a lot less cut/paste search/replace:

http://pastebin.com/4y2bHCVr

• Abid Rahman K: Oh my god, i can't believe you wrote all those lines!!! it works fine with time = 0.185 s.

Answer 5

I don't know Python syntax, but maybe you can decode this Scala code; start with the 2nd for-loop:

def setTo40 (a: Int, b: Int, c: Int, d: Int) = {
val vec = for (
 fa <- List (0, 1, -1);
 fb <- List (0, 1, -1);
 fc <- List (0, 1, -1);
 fd <- List (0, 1, -1);
 prod = fa * a + fb * b + fc * c + fd * d;
 if (prod > 0)
 ) yield (prod)
 vec.toSet
}
for (a <- (1 to 9);
 b <- (a to 14);
 c <- (b to 20);
 d = 40-(a+b+c)
 if (d > 0)) { 
 if (setTo40 (a, b, c, d).size > 39)
 println (a + " " + b + " " + c + " " + d)
 }

Answer 6

With weights [2, 5, 15, 18] you can also measure all objects between 1 and 40kg, although some of them will need to be measured indirectly. For example, to measure an object weighting 39kg, you would first compare it with 40kg and the balance would pend to the 40kg side (because 39 < 40), but then if you remove the 2kg weight it would pend to the other side (because 39> 38) and thus you can conclude the object weights 39kg.

More interestingly, with weights [2, 5, 15, 45] you can measure all objects up to 67kg.

• Abid Rahman K: Hi, thank you for your answer. My question was not about finding its answer, but solving it programmatically, especially using python.
• Luís Pureza: That's ok, but please note that writing a program to find this answer is slightly more complicated, because you have to take into account the indirect measurements.

Answer 7

If anyone doesn't want to import a library to import combos/perms, this will generate all possible 4-move strategies...

# generates permutations of repeated values
def permutationsWithRepeats(n, v):
 perms = []
 value = [0] * n
 N = n - 1
 i = n - 1
 while i > -1:
 perms.append(list(value))
 if value[N] < v:
 value[N] += 1
 else:
 while (i > -1) and (value[i] == v):
 value[i] = 0
 i -= 1
 if i > -1:
 value[i] += 1
 i = N
 return perms
# generates the all possible permutations of 4 ternary moves
def strategy():
 move = ['-', '0', '+']
 perms = permutationsWithRepeats(4, 2)
 for i in range(len(perms)):
 s = ''
 for j in range(4):
 s += move[perms[i][j]]
 print s
# execute
strategy()

Answer 8

My solution as follows:

 #!/usr/bin/env python3
weight = 40
parts = 4
part=[0] * parts
def test_solution(p, weight,show_result=False):
 cv=[0,0,0,0]
 for check_weight in range(1,weight+1):
 sum_ok = False
 for parts_used in range(2 ** parts):
 for options in range(2 ** parts):
 for pos in range(parts):
 pos_neg = int('{0:0{1}b}'.format(options,parts)[pos]) * 2 - 1
 use = int('{0:0{1}b}'.format(parts_used,parts)[pos])
 cv[pos] = p[pos] * pos_neg * use
 if sum(cv) == check_weight:
 if show_result:
 print("{} = sum of:{}".format(check_weight, cv))
 sum_ok = True
 break
 if sum_ok:
 continue
 else:
 return False
 return True
for part[0] in range(1,weight-parts):
 for part[1] in range(part[0]+1, weight - part[0]):
 for part[2] in range( part[1] + 1 , weight - sum(part[0:2])):
 part[3] = weight - sum(part[0:3])
 if test_solution(part,weight):
 print(part)
 test_solution(part,weight,True)
 exit()

It gives you all the solutions for the given weights

Answer 9

More dynamic than my previous answer, so it also works with other numbers. But breaking up into 5 peaces takes some time:

#!/usr/bin/env python3
weight = 121
nr_of_parts = 5
# weight = 40
# nr_of_parts = 4
weight = 13
nr_of_parts = 3
part=[0] * nr_of_parts
def test_solution(p, weight,show_result=False):
 cv=[0] * nr_of_parts
 for check_weight in range(1,weight+1):
 sum_ok = False
 for nr_of_parts_used in range(2 ** nr_of_parts):
 for options in range(2 ** nr_of_parts):
 for pos in range(nr_of_parts):
 pos_neg = int('{0:0{1}b}'.format(options,nr_of_parts)[pos]) * 2 - 1
 use = int('{0:0{1}b}'.format(nr_of_parts_used,nr_of_parts)[pos])
 cv[pos] = p[pos] * pos_neg * use
 if sum(cv) == check_weight:
 if show_result:
 print("{} = sum of:{}".format(check_weight, cv))
 sum_ok = True
 break
 if sum_ok:
 continue
 else:
 return False
 return True
def set_parts(part,position, nr_of_parts, weight):
 if position == 0:
 part[position] = 1
 part, valid = set_parts(part,position+1,nr_of_parts,weight)
 return part, valid
 if position == nr_of_parts - 1:
 part[position] = weight - sum(part)
 if part[position -1] >= part[position]:
 return part, False
 return part, True
 part[position]=max(part[position-1]+1,part[position])
 part, valid = set_parts(part, position + 1, nr_of_parts, weight)
 if not valid:
 part[position]=max(part[position-1]+1,part[position]+1)
 part=part[0:position+1] + [0] * (nr_of_parts - position - 1)
 part, valid = set_parts(part, position + 1, nr_of_parts, weight)
 return part, valid
while True:
 part, valid = set_parts(part, 0, nr_of_parts, weight)
 if not valid:
 print(part)
 print ('No solution posible')
 exit()
 if test_solution(part,weight):
 print(part,' ')
 test_solution(part,weight,True)
 exit()
 else:
 print(part,' ', end='\r')

Answer 10

I gave OP’s challenge a shot to see if I could beat @fraxel ’s solution.

I figured swapping the while loop for a formula might speed things up:

import math
def find_weights_formula(W):
 n = math.ceil(math.log(2*W+1, 3)) - 1
 weights = [3**i for i in range(n)]
 total = sum(weights)
 weights.append(W - total)
 return weights

Turns out W isn’t big enough for the formula to noticeably outpace the while loop (from runs @colab):

Testing W = 39
find_weights_formula(39) = [1, 3, 9, 26], time: 3.50 μs
find_weights(39) = [1, 3, 9, 26], time: 3.83 μs
Testing W = 40
find_weights_formula(40) = [1, 3, 9, 27], time: 2.04 μs
find_weights(40) = [1, 3, 9, 27], time: 1.98 μs
Testing W = 41
find_weights_formula(41) = [1, 3, 9, 27, 1], time: 2.12 μs
find_weights(41) = [1, 3, 9, 27, 1], time: 2.62 μs
Testing W = 43
find_weights_formula(43) = [1, 3, 9, 27, 3], time: 1.74 μs
find_weights(43) = [1, 3, 9, 27, 3], time: 2.10 μs

At the same time, I noticed that for edge cases this method, i.e. ‘fixed’ to base 3, may produce solutions where a same weight shows up twice.

Alternative:

I recently came across Clingo ASP, which is a good fit for problems like this.
The code below provides a stable model with the minimum number of pieces for a given max. weight:

% Parameter
#const max = 41.
% Facts
piece(1..max).
target(1..max-1).
% Choice rules
{ w(W) : piece(W) }.
use(T,W,plus); use(T,W,minus); use(T,W,none) :- w(W), target(T).
% Constraints
:- #sum { W : w(W) } != max.
:- target(T), T != #sum { W : use(T,W,plus); -W : use(T,W,minus) }.
% Optimization
#minimize { 1,W : w(W) }.
% Output
#show w/1.

Output (W=41): min. 5 pieces
(copy & paste the code to run online)

clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
w(1) w(3) w(6) w(10) w(21)
Optimization: 5
OPTIMUM FOUND
Models : 1
 Optimum : yes
Optimization : 5
Calls : 1
Time : 0.358s (Solving: 0.16s 1st Model: 0.03s Unsat: 0.13s)
CPU Time : 0.000s

... for W=44: min. 5 pieces

clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
w(1) w(3) w(7) w(8) w(10) w(15)
Optimization: 6
Answer: 2
w(1) w(3) w(5) w(15) w(20)
Optimization: 5
OPTIMUM FOUND
Models : 2
 Optimum : yes
Optimization : 5
Calls : 1
Time : 0.461s (Solving: 0.26s 1st Model: 0.04s Unsat: 0.21s)
CPU Time : 0.000s

... and for W=40: min. 4 pieces

clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
w(1) w(3) w(7) w(8) w(9) w(12)
Optimization: 6
Answer: 2
w(1) w(3) w(6) w(11) w(19)
Optimization: 5
Answer: 3
w(1) w(3) w(9) w(27)
Optimization: 4
OPTIMUM FOUND
Models : 3
 Optimum : yes
Optimization : 4
Calls : 1
Time : 0.363s (Solving: 0.18s 1st Model: 0.03s Unsat: 0.04s)
CPU Time : 0.000s