I am searching for a function in Javascript that takes in a String like this:
var str = '2?5?8?1?4?7?9?2?3'
and generates all possible combinations of the riddle with all question marks being substituted with basic mathematical operators (+-*/).
How would you go about that? And how would you do it for a dynamic length of riddles?
A simple DFS can get you the permutations that you are looking for. Basically, you have to replace the first occurrence of ? with the operator and recursively call the function again until there is no ? in the string.
Here we can make use of the replace() function as it leaves the original string unchanged.
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
Note: If there are x number of ? characters in the string, the number of possible permutations are going to be 4^x which can grow very quickly
Here is one way to do it using 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);For finding the first expression that matches target.
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);