Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Mystery sums

Original Problem

You are given an expression comprised of integers separated by operators, as well as the result of the expression preceded by an equals symbol =.
However, some of the digits in the expression have been replaced by question marks ?. 
You must restore the missing digits to the expression in such a way that it stays correct.

The digits to the right of the equals sign = will never be replaced by question marks ? .

Each expression can have several operators, but of the same type only.
INPUT:
A single line expression containing positive integers, and the operators +, -, *, / and the = sign. Some digits will be replaced by ? characters. Each number and symbol is separated by a space.

OUTPUT:
The same expression with each ? replaced with the proper digit for the expression to be true.

CONSTRAINTS:
expression contains less than 256 characters.

Solution

Since the given expressions are well formed, we don't need to write a sophisticated parser and just iterate over all ? combinations and use an expression evaluation, like JavaScripts eval() function. For one ? we have 10 combinations, for two ? we have 100 combinations, for three ? we have 1000 iterations and so on. For a general number of ? \(e\), the number of combinations is \(n=10^e\). We then simply iterate over the combinations and form a valid test expression:

var exp = readline();

var e = exp.replace(/[^?]/g, "").length;
var n = 10**e;

for (var i = 0; i < n; i++) {

  var test = exp;
  for (var j = 0; j < e; j++) {
    test = test.replace('?', (i / 10**j | 0) % 10);
  }

  if (eval(test.replace("=", "=="))) {
    print(test);
    break;
  }
}

« Back to problem overview