Solver

Target is

Numbers are (seperate by space)

The closest solution is:


Complexity Analysis

This problem is quite similar to the 24 puzzle game, but slightly different. They both provide 4 binary operators that we can choose from, namely $+$ $-$ $*$ and $/$. Thus, any valid expression that you construct naturally forms a full binary tree, which has a nice recursive structure, where there're $m$ leaves, each takes the value of a number, and $m-1$ non-leaf nodes, each takes one of the operators. So, the question becomes, how many different trees can you construct from $n$ numbers?

Let's consider the case where we use all of the numbers. Any solutions that use less numbers would just be a subtree of a tree of $n$ leaves. Let's consider the structure of the tree first. Starting from 2 leaves, there is only one way to construct it: two numbers, one operator. When we include the third number, we must choose one of the leaves and replace it with an operator node, and attach two number nodes as its children. We repeat this process for the rest of the numbers, each time we choose a leaf and replace it with an operator node, then attach two number nodes. There are $k-1$ choices when we include the $k$th number, so over all there are $(n-1)!$ structures.

Next, the number of different permutations of the numbers is $n!$, and the number of all combinations of the operators is $4^{n-1}$. Before we multiply them, notice that this problem has a symmetry: if we exchange the left and right subtree of a '$+$' or '$*$' operator node, the value of the expression doesn't change. If we consider a '$-$' node, we can exchange the subtrees when the two value on the subtrees are the same, and if they are different, one of the expressions is invalid, because the game prevents you from subtracting a large number from a small number. (Even if it's allowed, it wouldn't make a difference if the target is positive and at least one of the given numbers is also positive.) The same goes for '$/$' nodes. (Notice that in the case of the 24 puzzle, the situation is different. You have to use fractions in certain cases, e.g. 5 5 5 1, 3 3 7 7, etc.) So, for every ordering of the two subtrees of a operator node, only one needs to be considered. So the upper bound is $n!(n-1)!\frac{4^{n-1}}{2^{n-1}}=2^{n-1}n!(n-1)!$. In practice, though, the cases that one number is a multiple of the other is rare, so it would be closer to $\left(\frac{3}{2}\right)^{n-1}n!(n-1)!$, but it is a minor change on the complexity.

This is exactly how we are going to solve it. Each time we apply an operator on two of the numbers, record the new value (because we don't have to use all of the numbers, an intermediate result could be the solution. This is another difference between this problem and the 24 puzzle game) and its corresponding expression, then we take the new value and the rest of the numbers as the input to the same problem, but the number of the numbers is one less, so we can solve it recursively. If the solver finds the exact solution, we can return early. But if there's no exact solution, it returns the closest possible solution.

We can easily modify the function to return the first $k$ closest solutions, e.g. with a priority queue, but there will be many duplicated expressions with the same solution value. We can use a set to skip the expressions that give the same value that we've already found. Implementations are simple, so they're left as exercises! :)

An Example of Bad Code

I took a look at their JS code for puzzle generation, and I found this function: 

function getSmartOperation(firstNum, secondNum) {
  var randInt = getRandomInt(0, 100)
  const quotient = firstNum / secondNum
  if (randInt < 20 && firstNum + secondNum <= 999) {
    // 20% chance of +
    return '+'
  } else if (
    randInt >= 21 &&
    randInt < 40 &&
    firstNum - secondNum >= 0
  ) {
    // 20% chance of -
    return '−'
  } else if (
    randInt >= 41 &&
    randInt < 65 &&
    firstNum * secondNum <= 999
  ) {
    // 25% chance of x
    return '×'
  } else if (randInt >= 65 && Number.isInteger(quotient)) {
    // 35% chance of ÷
    return '÷'
  } else {
    return getSmartOperation(firstNum, secondNum)
  }
}

This is part of their algorithm to generate the target number from a randomly generated numbers' list. The problem with this function is in the last statement. If all the attempts to find an appropriate operator for the two numbers fail, it puts the same two numbers back into the function and repeats the process. Since the numbers are randomly generated, there's 50% chance that the first number is less than the second number, so when they are put back, if the RNG rolls to $-$ or $/$ again, it would just be a waste of time and we just roll the RNG again until it ends up being $+$ or $*$. The worse thing is, if the first number is smaller than the second number, and their summation and product are both larger than 999, the recursion will never end. (It doesn't happen in this particular scenario because the second number is always from the original list, which seems to be always small ($\leq 25$ from what I see), so if the first number $+$ the second one $\geq 999$, then the first number must be greater than the second one, so $-$ is always valid. But still, this function is bad in itself.)

A better approach is, exchange the two numbers if the first is less than the second, then attemp to assign the division operator with high probability. If they are not divisible, try multiplying and adding with their assigned probabilities. If both fail, just assign the $-$ operator, because the first number is larger or equal to the second number and the difference must be less or equal to the first number, it's guaranteed that the result is a valid number.