Algorithm for splitting 40 kg stone in 4 parts to measure between 1-40 kg puzzle
There is a 40 kg stone that is to be broken into 4 pieces such that you can measure any weight between 1 kg to 40 kg using a balance. What are the weights of the broken pieces?
If you ever stumbled upon this puzzle and have wondered of solving it programmatically, golibrary, presents you a detailed explanation and demo of the solution to this puzzle.
Whenever, given a weight W and asked to split it in N parts , such that everything from 1 to W kg can be measured, there is a simple formula which can be used to calculate the set of N parts that are needed. The formula is as below :-
S ∈ [Rounding of (Log W/Log N)] 0<=m<=r such that each of set S > 0 and <= W. ————————————————(Eqn 1)
Below is a demo of this puzzle, which shows what weights will be needed to measure everything between 1 to 40 kg, all inclusive. The above formula is used by the algorithm to find the values of the set S. Later, we find different permutations and combinations of the weights and operators, to arrive at 36, different expressions which will show how different weights from the range can be calculated.
The code that sits behind the iframe above is :-
Understanding the above Algorithm:-
1. Find out the set of weights / 4 parts needed to cover all weights between 1 to 40 kg using the formula given in Eqn 1 denoted by Set S.
2. Find out if a given weight between 1 to 40 kg, is already present in set S.
3. If point number 2 is false, then find out all the Cartesian combinations nCr of the array set S.
4. Take out each of the cartesian combinations obtained in step 3, and try it with all permutations of operators + or -, to define an expression.
5. Evaluate the expression and compare it with weight i, to be measured where 1 <= i <=40.
6. If 5 is true, print the expression, if not repeat the process for each of the combinations obtained in step 4 until, it matches i.
7. Once all expressions for weights 1 to 40 kg are evaluated and found out, exit.
Leave a comment below, if any questions. Subscribe to our facebook Page to stay tuned with the latest technology blogs.