Codingame Solution: Mystery sums
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.
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;
}
}