Estoy buscando una función en Javascript que admita una cadena como esta:
var str = '2?5?8?1?4?7?9?2?3'y genera todas las combinaciones posibles del acertijo con todos los signos de interrogación sustituidos por operadores matemáticos básicos (+-*/).
¿Cómo harías eso? ¿Y cómo lo harías por una longitud dinámica de acertijos?
Un DFS simple puede brindarle las permutaciones que está buscando. Básicamente, tienes que reemplazar la primera aparición de ? con el operador y vuelva a llamar recursivamente a la función hasta que no haya ? en la cuerda.
Aquí podemos hacer uso de la función replace() ya que deja la cadena original sin cambios.
function dfsPermute(s){ // If the ? dosent exist then its index will be -1 // In that case print it to the console if(s.indexOf('?') === -1) { console.log(s); } else { let s1 = s.replace('?', '+') dfsPermute(s1); let s2 = s.replace('?', '-') dfsPermute(s2); let s3 = s.replace('?', '*') dfsPermute(s3); let s4 = s.replace('?', '/') dfsPermute(s4); } } dfsPermute('2?5?4'); 2+5+4 2+5-4 2+5*4 2+5/4 2-5+4 2-5-4 2-5*4 2-5/4 2*5+4 2*5-4 2*5*4 2*5/4 2/5+4 2/5-4 2/5*4 2/5/4 Nota: Si hay x número de ? caracteres en la cadena, el número de permutaciones posibles será 4^x que puede crecer muy rápidamente
Aquí hay una forma de hacerlo usando Backtracking :
const operators = ['+', '-', '*', '/']; const replaceAt = function(str, index, replacement) { return str.substr(0, index) + replacement + str.substr(index + replacement.length); } function getCombinations(str, start, combinations) { if (start === str.length) return combinations.push(str); if (str[start] !== '?') return getCombinations(str, start + 1, combinations); let temp = str[start]; for (let op of operators) { str = replaceAt(str, start, op); getCombinations(str, start + 1, combinations); str = replaceAt(str, start, temp); } } const str = '2?5?8?1'; const combinations = []; getCombinations(str, 0, combinations); console.log(combinations);Para encontrar la primera expresión que coincida con el objetivo.
const operators = ['+', '-', '*', '/']; const replaceAt = function(str, index, replacement) { return str.substr(0, index) + replacement + str.substr(index + replacement.length); } function getCombinations(str, start, target) { if (start === str.length) { if (eval(str) === target) return str; return false; } if (str[start] !== '?') return getCombinations(str, start + 1, target); let temp = str[start]; for (let op of operators) { str = replaceAt(str, start, op); const res = getCombinations(str, start + 1, target); if (res) return res; str = replaceAt(str, start, temp); } return false; } const str = '2?5?8?1'; const target = 16; const result = getCombinations(str, 0, target); console.log(result);