Estaba jugando a Codingame y encontré una pregunta que no tenía idea de cómo resolver. Pensé en usar la recursividad, pero apesto, solo por curiosidad, quiero saber cómo se suponía que debía resolverse :)
Pregunta:
Tres números a, b y c se muestran en la primera línea, separados por un espacio. La segunda línea muestra un solo número d. Entre a, b y c, puede colocar +, -, * o / para crear una fórmula. Si pones + o - o * o / entre a, b y c, el número total de expresiones que puedes crear es 16. Cuenta cuántas de esas expresiones dan como resultado la respuesta d.
Si hay uno, genera la fórmula. Si no lo hubiera, salida -1. Si hay más de uno, muestra el número de expresiones.
Ejemplo 1: 3 2 1 = 5
En el caso de la pregunta 3*2-1 y 3+2*1, las dos ecuaciones son 5. Entonces la respuesta es 2, que es el número de ecuaciones correctas.
Ejemplo 2: 1 1 1 3
En el caso del problema solo 1+1+1 es 3, entonces la respuesta es 1+1+1.
Ejemplo 3: 10 5 1 = 1000
La respuesta no es 1000 sin importar cómo formules la ecuación. Por lo tanto, la respuesta es -1.
Las soluciones más simples suelen ser las mejores.
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 }La solución de Konrad puede estar bien, pero dado que algunos comentaristas querían ver algo más escalable, aquí hay otra solución (utilicé la construcción presentada por Konrad).
La idea es definir todas las funciones aplicables y luego generar todas las permutaciones con dos bucles. Si la fórmula se vuelve más larga, el número de bucles también aumentaría. Si el número de bucles se vuelve variable o muy grande, se pueden usar otros trucos.
Luego tomo cada función de permutación y la aplico con las entradas dadas. Obtengo resultados diferentes a los de Konrad, pero no veo ningún problema con su solución. Esta solución aquí impondrá un orden diferente. Está de acuerdo con la solución publicada anteriormente, pero el orden de las operaciones generalmente puede ser un problema.
La solución correcta estaría determinada por la tarea.
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))usar 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)); o 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));