Last active
August 23, 2017 13:09
-
-
Save oadam/d823a459d2add5c884e9edc042a50207 to your computer and use it in GitHub Desktop.
countdown solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env node | |
"use strict"; | |
if (process.argv.length < 4) { | |
console.error( | |
"usage :" + process.argv.slice(0, 2).join(" ") + " target num1 num2..." | |
); | |
process.exit(-1); | |
} | |
var target = parseInt(process.argv[2]); | |
var inputNumbers = process.argv | |
.slice(3) | |
.map(function(n) { | |
return parseInt(n); | |
}) | |
.sort(function(a, b) { | |
return a - b; | |
}); | |
console.log("targeting " + target + " with " + inputNumbers.join(" ") + "\n"); | |
var best = 0; | |
var bestDist = target; | |
var bestStack = null; | |
const operators = [ | |
{ | |
_isOperator: true, | |
compute: function(a, b) { | |
return a + b; | |
}, | |
toString: function() { | |
return "+"; | |
} | |
}, | |
{ | |
_isOperator: true, | |
compute: function(a, b) { | |
return a - b; | |
}, | |
toString: function() { | |
return "-"; | |
} | |
}, | |
{ | |
_isOperator: true, | |
compute: function(a, b) { | |
return a * b; | |
}, | |
toString: function() { | |
return "x"; | |
} | |
}, | |
{ | |
_isOperator: true, | |
compute: function(a, b) { | |
return a / b; | |
}, | |
applies: function(a, b) { | |
return a % b === 0; | |
}, | |
toString: function() { | |
return "/"; | |
} | |
} | |
]; | |
var traversed = 0; | |
var progressAtDepth = [0, 0]; | |
var currentMaxDepth = 0; | |
class Node { | |
constructor(value, prev) { | |
this.value = value; | |
this.prev = prev; | |
} | |
} | |
function traverse(stringStack, stack, numbersBitSet, usedNumbersCount) { | |
traversed++; | |
if (stack && !stack.prev) { | |
var dist = Math.abs(stack.value - target); | |
if (dist < bestDist) { | |
bestDist = dist; | |
best = stack.value; | |
bestStack = stringStack; | |
} | |
if (dist == 0) { | |
throw new Error("found"); | |
} | |
} | |
if (stack && stack.prev) { | |
var a = stack.prev.value, b = stack.value; | |
// avoid computing both a b and b a | |
if (a >= b) { | |
for (var i = 0; i < operators.length; i++) { | |
var o = operators[i]; | |
if (o.applies && !o.applies(a, b)) { | |
continue; | |
} | |
var c = o.compute(a, b); | |
var newStack = new Node(c, stack.prev.prev); | |
var newStringStack = new Node(o, stringStack); | |
traverse(newStringStack, newStack, numbersBitSet, usedNumbersCount); | |
} | |
} | |
} | |
if (usedNumbersCount < currentMaxDepth) { | |
for (var i = 0; i < inputNumbers.length; i++) { | |
var n = inputNumbers[i]; | |
if (usedNumbersCount < 2) { | |
progressAtDepth[usedNumbersCount] = i; | |
var percent = (progressAtDepth[0] * inputNumbers.length + | |
progressAtDepth[1]) / | |
(inputNumbers.length * inputNumbers.length - 1); | |
process.stdout.write( | |
"\rsearching solutions of length " + | |
currentMaxDepth + | |
"... " + | |
(percent * 100).toFixed(0) + | |
"%" | |
); | |
} | |
if (numbersBitSet & 1 << i) { | |
continue; | |
} | |
// avoid duplicate computations | |
// do not run if previous number is the same and is not used | |
if ( | |
i > 0 && | |
inputNumbers[i] == inputNumbers[i - 1] && | |
!(numbersBitSet & 1 << i - 1) | |
) { | |
continue; | |
} | |
var newNumbersBitSet = numbersBitSet | 1 << i; | |
var newStack = new Node(n, stack); | |
var newStringStack = new Node(n, stringStack); | |
traverse( | |
newStringStack, | |
newStack, | |
newNumbersBitSet, | |
usedNumbersCount + 1 | |
); | |
} | |
} | |
} | |
for ( | |
currentMaxDepth = 1; | |
currentMaxDepth <= inputNumbers.length; | |
currentMaxDepth++ | |
) { | |
process.stdout.write("\n"); | |
try { | |
traverse(null, null, 0, 0); | |
} catch (e) { | |
if (e.message == "found") { | |
break; | |
} else { | |
throw new Error("unexpected error", e); | |
} | |
} | |
} | |
console.log("\n\n"); | |
if (best == target) { | |
console.log("solution :"); | |
} else { | |
console.log("approaching solution (" + best + ") :"); | |
} | |
var bestStackArray = []; | |
for (var n = bestStack; n != null; n = n.prev) { | |
bestStackArray.unshift(n.value); | |
} | |
if (bestStackArray.length == 1) { | |
console.log([bestStackArray[0], "=", bestStackArray[0]].join(" ")); | |
} else { | |
var stack = []; | |
bestStackArray.forEach(function(e) { | |
if (e._isOperator) { | |
var b = stack.pop(), a = stack.pop(); | |
var c = e.compute(a, b); | |
stack.push(c); | |
console.log([a, e, b, "=", c].join(" ")); | |
} else { | |
stack.push(e); | |
} | |
}); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment