All Combinations of Riddle

Question

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?

Answer 1

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.

Code

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');

Output

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

Answer 2

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);