Algorithm for splitting 40 kg stone in 4 parts to measure between 1-40 kg puzzle
0
/
2125
Problem Statement:-
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. DEMO:- The code that sits behind the iframe above is :-<html> <h2> Puzzle solution to splitting 40 kg weight into 4 parts </h2> <i><b>Click on Solve button below to see the detailed solution to this puzzle</b></i> <br/><br/> <textarea readonly style='font-weight:bold;color:green;font-size:14px;' id = 'solutionarea' rows = 30 cols = 100> </textarea> <br/> <input type = 'button' value = 'Solve' onclick = 'init()'/> </html> <script> //window.onload = init; function init() { var index = 0, weights = []; while (true) { var weight = Math.pow ( (Math.ceil(getBaseLog(4,40))), index++); if (weight > 40) { break; } else { weights.push(weight); } } if (document.getElementById('solutionarea').innerHTML.length) { document.getElementById('solutionarea').innerHTML = ''; } document.getElementById('solutionarea').innerHTML = "Split 40 kg weight into "+ weights +" to be able to measure weights between 1-40 kg all inclusive\n\n\n"; showCombinations(weights.sort(function(a, b){return b-a})); } function getBaseLog(x, y) { return Math.log(y) / Math.log(x); } function showCombinations(weights) { var index = 0; for (var i = 1; i <= 40; i++) { var retVal = weights.some(function(item) { return item === i; }); if (retVal) { document.getElementById('solutionarea').innerHTML += "\n\nWeight of "+i+" kg found in given combination of weights "+weights+"\n\n"; } else { // calc here for combinations 2,3.. until weights.length - 1 for (t = weights.length; t > 1; t--) { combinations(weights, t, 0, new Array(t), i); } } } } function combinations(arr, len, startPosition, result, valueToMatch){ if (len == 0){ return evaluate(result, valueToMatch); } for (var i = startPosition; i <= arr.length-len; i++){ result[result.length - len] = arr[i]; combinations(arr, len-1, i+1, result, valueToMatch); } return false; } function evaluate(res, valueToMatch) { var numOfOperators = res.length - 1; var retVal = false; for (x = 0; x < Math.pow(2, numOfOperators); x++) { retVal = solve(res, pad(x.toString(2,numOfOperators), numOfOperators), valueToMatch); } return retVal; } function pad(n, width, z) { z = z || '0'; n = n + ''; return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n; } function solve(arr, operators, valueToMatch) { var expression = ''; for (i = 0; i < arr.length-1; i++) { var operator = (parseInt(operators[i]))? '+' : '-'; expression += arr[i] + operator; } expression += arr[i]; if (Math.abs(eval(expression)) == valueToMatch) { document.getElementById('solutionarea').innerHTML += "\n\nEvaluating weight of " + valueToMatch+ "Kg by expression : "+ expression+" = "+ eval(expression)+" kg\n\n"; return true; } return false; } </script>