Skip to content

Instantly share code, notes, and snippets.

@mourner
Created July 7, 2011 13:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mourner/1069551 to your computer and use it in GitHub Desktop.
Save mourner/1069551 to your computer and use it in GitHub Desktop.
Brute-force JS solution for Xopus task (see http://goo.gl/Zy0a9)
<!DOCTYPE html>
<head>
<title>Test</title>
</head>
<body>
<button onclick="displayResult()">Search</button>
<script>
var numEvals;
function displayResult() {
var start = +new Date;
numEvals = 0;
var eq = searchEquation([3, 6, 9, 12, 15], ['-', '+', '*', '/'], 381);
document.body.innerHTML = (eq + ', num of evals: ' + numEvals + ', took ' + (+new Date - start) + 'ms');
}
function permute(variants) {
var permArr = [],
usedVariants = [];
function permuteStep(variants) {
for (var i = 0, variantsLen = variants.length, variant; i < variantsLen; i++) {
variant = variants.splice(i, 1)[0];
usedVariants.push(variant);
if (variants.length === 0) {
permArr.push(usedVariants.slice());
}
permuteStep(variants);
variants.splice(i, 0, variant);
usedVariants.pop();
}
}
permuteStep(variants);
return permArr;
}
function searchEquation(nums, ops, equals) {
var opsLen = ops.length,
numsLen = nums.length,
variantsNum = Math.pow(opsLen, numsLen);
var permutations = permute(nums);
for (var k = 0, permLen = permutations.length; k < permLen; k++) {
for (var i = 0; i < variantsNum; i++) {
var variantsStr = i.toString(opsLen),
leadZeroNum = numsLen - variantsStr.length,
equation = '';
for (var j = 0; j < numsLen; j++) {
var opsIndex = j < leadZeroNum ? 0 : parseInt(variantsStr.charAt(j - leadZeroNum), opsLen);
equation = (equation ? '(' + equation + ')' : '') + ops[opsIndex] + permutations[k][j];
}
var result;
try {
result = eval(equation);
numEvals++;
} catch(e) {
continue;
}
if (result == equals) {
return equation;
}
}
}
return null;
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment