0

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?

K_NO
  • 29
  • 3

2 Answers2

3

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

DollarAkshay
  • 2,063
  • 1
  • 21
  • 39
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);
PR7
  • 1,524
  • 1
  • 13
  • 24
  • would there also be a way to program it so that the function automatically returns false and stops when the combination of the riddle is equal to a certain integer. For example: The function goes through all combinations and after each combination, it checks the solution of the particular combination. If this solution is equal to a certain number than the riddle returns false. – K_NO Apr 05 '22 at 11:48
  • @K_NO so for example to find `16` for combination `2?5?8?1`, it should return `2+5+8+1`. Is this your question ? – PR7 Apr 05 '22 at 13:58
  • yes, exactly. The function should stop if such a solution was found. – K_NO Apr 19 '22 at 16:18
  • Just need to add one extra condition for that. I have update the answer now. – PR7 Apr 20 '22 at 03:38