Skip to content

Instantly share code, notes, and snippets.

@oadam
Last active August 23, 2017 13:09
Show Gist options
  • Save oadam/d823a459d2add5c884e9edc042a50207 to your computer and use it in GitHub Desktop.
Save oadam/d823a459d2add5c884e9edc042a50207 to your computer and use it in GitHub Desktop.
countdown solver
#!/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