I was playing Codingame and I found a question that I had no idea of how to solve. I thought of using recursion but I suck at it, just of curiosity I wanna learn how it was supposed to be solved :)
Question:
Three numbers a, b, and c are shown on the first line, separated by a space. The second line shows a single number d. Between a, b and c, you can place either +, - , * or / to create a formula. If you put + or - or * or / between a, b and c, the total number of expressions you can create is 16. Count how many of those expressions result in the answer d.
If there is one, output the formula. If there was not, output -1. If there is more than one, output the number of expressions.
Example 1: 3 2 1 = 5
In the case of the question 3*2-1 and 3+2*1, the two equations are 5. So the answer is 2, which is the number of equations that are correct.
Example 2: 1 1 1 3
In the case of the problem only 1+1+1 is 3, so the answer is 1+1+1.
Example 3: 10 5 1 = 1000
The answer is not 1000 no matter how you formulate the equation. Therefore, the answer is -1.
The simpliest solusions are usually the best
console.log(checkEquations(1, 1, 1, 3))
console.log(checkEquations(3, 2, 1, 5))
console.log(checkEquations(10, 5, 1, 1000))
function checkEquations(a, b, c, d) {
return [
a + b + c,
a + b - c,
a + b * c,
a + b / c,
a - b - c,
a - b + c,
a - b * c,
a - b / c,
a / b / c,
a / b + c,
a / b - c,
a / b * c,
a * b * c,
a * b + c,
a * b - c,
a * b / c,
].filter(value => value === d).length || -1
}Konrad's solution can be fine, but since some commentors wanted to see something more scalable, here is another solution (I used the construct laid out by Konrad).
The idea is to define all applicable functions and then generate all permutations with two loops. If the formula becomes longer than the number of loops would increase as well. If the number of loops becomes variable or very large one might use some other tricks.
I then just take each permutation function and apply it with the given inputs. I do get different results than Konrad, but I do not see an issue with his solution. This solution here will enforce a different order. It agrees with the posted solution above, but the order of operations might generally be an issue.
What solution is correct would be determined by the task.
const add = (a, b) => a + b;
const sub = (a, b) => a - b;
const mul = (a, b) => a * b;
const div = (a, b) => a / b;
const applicableFunctions = [add, sub, mul, div];
const formulaPermutations = [];
for(const firstFunction of applicableFunctions) {
for(const secondFunction of applicableFunctions) {
const singlePermutation = (a, b, c) => firstFunction(a, secondFunction(b, c));
formulaPermutations.push(singlePermutation);
}
}
console.log('Number of permutations:', formulaPermutations.length)
const checkEquations = (a, b, c, d) => {
return formulaPermutations
.map((formula) => formula(a, b, c))
.filter(value => value === d).length || -1
}
console.log(checkEquations(1, 1, 1, 3))
console.log(checkEquations(3, 2, 1, 5))
console.log(checkEquations(10, 5, 1, 1000))use eval ?
const build = (...opr) => {
const arr = [];
opr.forEach((x) => opr.forEach((y) => arr.push((a,b,c) => eval(`${a} ${x} ${b} ${y} ${c}`))));
return (a, b, c, d) => arr.filter((fn) => fn(a,b,c) === d).length || -1;
}
const checkEquations = build('+', '-', '*', '/');
console.log(checkEquations(1, 1, 1, 3));
console.log(checkEquations(3, 2, 1, 5));
console.log(checkEquations(10, 5, 1, 1000));or new Function
const build = (...opr) => {
const arr = [];
opr.forEach((x) => opr.forEach((y) => arr.push((a,b,c) => new Function(`return ${a} ${x} ${b} ${y} ${c};`).call())));
return (a, b, c, d) => arr.filter((fn) => fn(a,b,c) === d).length || -1;
}
const checkEquations = build('+', '-', '*', '/');
console.log(checkEquations(1, 1, 1, 3));
console.log(checkEquations(3, 2, 1, 5));
console.log(checkEquations(10, 5, 1, 1000));