arithmetic puzzle

gistfile1.txt

// each state element is of the form [value, bitmask, expression]
// - `expression` is a string representing an arithmetic expressoin
// - `value` is the arithmetic value of `expression`
// - `bitmask` is a bitmask recording which of the 4 numbers (6,6,5,2) we've
//    used
const state = [[6,1,"6"],[6,2,"6"],[5,4,"5"],[2,8,"2"]];

// combines compatible states using arithmetic operations to produce new states.
//
// x and y are states (see above)
// f is an arithmetic operator on numbers
// g is the same arithmetic operator, on expressions-as-strings
// eg. if f(x,y) = x + y, then g(x,y) = "(${x}+${y})".
function go(x, y, f, g) {
  // if the bitmasks share no set-bits, then they don't use the same input
  // number twice. (well, they can use 6 twice, because it appears twice, but
  // it's correspondingly assigned two different positions in the bitmask.)
  if ((x[1] & y[1]) == 0) {
    // we add a new state which combines both expressions using the operator
    state.push([f(x[0], y[0]), x[1] | y[1], g(x[2], y[2])]);
  }
}

// we pass over `state` repeatedly, each time generating new states by combining
// compatible old states using go(). we need only 3 passes because with four
// inputs, we can perform at most 3 arithmetic operations.
for (var pass = 0; pass < 3; pass++) {
  // In what follows, we will iterate over `state` and call go() as we iterate.
  // However, go() mutates `state`! but only by *appending* elements. So if we
  // grab the length of `state` ahead of time, our iteration only considers a
  // "snapshot" of `state`, which makes everything easier to think about.
  const L = state.length;

  // first we consider noncommutative operations: - and /
  // here we iterate over all possible pairs of states
  for (var i = 0; i < L; i++) {
    for (var j = 0; j < L; j++) {
      go(state[i], state[j], (x, y) => x - y, (x, y) => `(${x}-${y})`);
      go(state[i], state[j], (x, y) => x / y, (x, y) => `(${x}/${y})`);
    }
  }

  // now we consider commutative operations: * and +.
  for (var i = 0; i < L; i++) {
    // since these are commutative, once we consider a given input state-pair
    // (x,y), we need not consider (y,x). so we start `j` at value `i+1`. Why
    // not at `i`? Because an expression can't be combined with itself without
    // reusing inputs, which we aren't allowed to do.
    for (var j = i+1; j < L; j++) {
      go(state[i], state[j], (x, y) => x * y, (x, y) => `(${x}*${y})`);
      go(state[i], state[j], (x, y) => x + y, (x, y) => `(${x}+${y})`);

    }
  }
}

// Now that we've done everything, look for a state whose value is 17 and which
// uses all the inputs, and print its expression-string.
state.forEach(x => { if (x[0] == 17 && x[1] == 15) console.log(x[2])});