--description--

The 24 Game tests a person's mental arithmetic.

The aim of the game is to arrange four numbers in a way that when evaluated, the result is 24

--instructions--

Implement a function that takes a string of four digits as its argument, with each digit from 1 to 9 (inclusive) with repetitions allowed, and returns an arithmetic expression that evaluates to the number 24. If no such solution exists, return "no solution exists".

Rules:

<ul> <li> Only the following operators/functions are allowed: multiplication, division, addition, subtraction. </li> <li> Division should use floating point or rational arithmetic, etc, to preserve remainders. </li> <li> Forming multiple digit numbers from the supplied digits is disallowed. (So an answer of 12+12 when given 1, 2, 2, and 1 is wrong). </li> <li> The order of the digits when given does not have to be preserved. </li> </ul>

Example input	Example output
<code>solve24("4878");</code>	<code>(7-8/8)*4</code>
<code>solve24("1234");</code>	<code>314*2</code>
<code>solve24("6789");</code>	<code>(6*8)/(9-7)</code>
<code>solve24("1127");</code>	<code>(1+7)*(2+1)</code>

--before-each--

const testCases_ = [
  '4878',
  '1234',
  '6789',
  '1127'
];

const OPERATORS_ = {
  '+': (a, b) => a + b,
  '-': (a, b) => a - b,
  '*': (a, b) => a * b,
  '/': (a, b) => a / b
};

const PRECEDENCE_ = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2
};

function evaluate_(expression) {
  expression = expression.replace('/\\s+/g', '');
  const stack = [];
  let postfix = '';

  // Convert from infix to postfix
  let head = 0;
  while (head < expression.length) {
    let c = expression[head];
    switch (c) {
      case '(':
        stack.push(c);
        break;
      case ')':
        let last = stack.pop();
        while (last !== '(') {
          postfix += last;
          last = stack.pop();
        }
        break;
      case '+':
      case '-':
      case '*':
      case '/':
        while (stack.length && PRECEDENCE_[c] <= PRECEDENCE_[stack[stack.length - 1]]) {
          postfix += stack.pop();
        }
        stack.push(c);
        break;
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
        postfix += c;
        break;
      default:
        return false;
    }
    head++;
  }

  // Clear out stack
  while (stack.length) {
    postfix += stack.pop();
  }

  // Evaluate postfix
  for (let c of postfix) {
    switch (c) {
      case '+':
      case '-':
      case '*':
      case '/':
        const b = +stack.pop();
        const a = +stack.pop();
        stack.push(OPERATORS_[c](a, b));
        break;
      default:
        stack.push(c);
    }
  }
  return stack.pop();
}

function isValidSolution_(userSolution) {
  return evaluate_(userSolution) === 24;
}

--hints--

solve24 should be a function.

assert(typeof solve24 === 'function');

solve24("4878") should return (7-8/8)*4, 4*(7-8/8), or a similar valid string

assert(isValidSolution_(solve24(testCases_[0])));

solve24("1234") should return 1*2*3*4 or a similar valid string

assert(isValidSolution_(solve24(testCases_[1])));

solve24("6789") should return (6*8)/(9-7), (8*6)/(9-7), or a similar valid string

assert(isValidSolution_(solve24(testCases_[2])));

solve24("1127") should return (1+7)*(1+2) or a similar valid string

assert(isValidSolution_(solve24(testCases_[3])));

--seed--

--seed-contents--

function solve24 (numStr) {

  return true;
}

--solutions--

function solve24(numStr) {
  const digitsArr = numStr.split('');
  const answers = [];

  const digitPermutations = [];
  const operatorPermutations = [];

  function generateDigitPermutations (digits, permutations = []) {
    if (digits.length === 0) {
      digitPermutations.push(permutations);
    }
    else {
      for (let i = 0; i < digits.length; i++) {
        const curr = digits.slice();
        const next = curr.splice(i, 1);
        generateDigitPermutations(curr.slice(), permutations.concat(next));
      }
    }
  }

  function generateOperatorPermutations (permutations = []) {
    const operators = ['+', '-', '*', '/'];
    if (permutations.length === 3) {
      operatorPermutations.push(permutations);
    }
    else {
      for (let i = 0; i < operators.length; i++) {
        const curr = permutations.slice();
        curr.push(operators[i]);
        generateOperatorPermutations(curr);
      }
    }
  }

  generateDigitPermutations(digitsArr);
  generateOperatorPermutations();

  interleave();

  return answers[0];

  function interleave () {
    for (let i = 0; i < digitPermutations.length; i++) {
      for (let j = 0; j < operatorPermutations.length; j++) {
        const d = digitPermutations[i];
        const o = operatorPermutations[j];
        const perm = [
          `${d[0]}${o[0]}${d[1]}${o[1]}${d[2]}${o[2]}${d[3]}`,
          `(${d[0]}${o[0]}${d[1]})${o[1]}${d[2]}${o[2]}${d[3]}`,
          `${d[0]}${o[0]}(${d[1]}${o[1]}${d[2]})${o[2]}${d[3]}`,
          `${d[0]}${o[0]}${d[1]}${o[1]}(${d[2]}${o[2]}${d[3]})`,
          `${d[0]}${o[0]}(${d[1]}${o[1]}${d[2]}${o[2]}${d[3]})`,
          `(${d[0]}${o[0]}${d[1]}${o[1]}${d[2]})${o[2]}${d[3]}`,
          `(${d[0]}${o[0]}${d[1]})${o[1]}(${d[2]}${o[2]}${d[3]})`
        ];

        perm.forEach(combination => {
          const res = eval(combination);

          if (res === 24) {
            return answers.push(combination);
          }
        });
      }
    }
  }
}

24 game