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?

CodePudding user response：

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){
    
    const i = s.indexOf('?');
    // If the ? dosent exist then print it
    if(i === -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');

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

CodePudding user response：

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