countdown solver

solver.js

#!/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);
    }
  });
}