Algorithm for splitting 40 kg stone in 4 parts to measure between 1-40 kg puzzle

0 / 2119
Algorithm for 40 kg stone puzzle

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

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts