Solution for Rosetta Code Challenge - 24 game

Contributors
1

What is your hint or solution suggestion?

Summary 
function solve24(numStr) {
    return solve(numStr, 24);
}

function solve(numStr, target) {

    let perms = permutate(numStr);
    let factors = getfactors(target);
    let exp1, exp2, exp3;

    for (let perm of perms) {
        for (let factor of factors) {

            // Check if format exp(a,b, factor) * exp(c, d, 24/factor) works
            exp1 = expression(perm[0], perm[1], factor);
            exp2 = expression(perm[2], perm[3], target / factor);
            if (exp1 !== 'NA' && exp2 !== 'NA') {
                exp1 = exp1.length == 1 ? exp1 : '(' + exp1 + ')';
                exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
                return exp1 + '*' + exp2;
            }

        }

        for (let i = 1; i <= 3; i++) {

            // Check if format exp(a,b, 24*i) / exp(c, d, i) works
            exp1 = expression(perm[0], perm[1], target * i);
            exp2 = expression(perm[2], perm[3], i);
            exp1 = exp1.length > 1 ? exp1 : '(' + exp1 + ')';
            exp2 = exp2.length > 1 ? exp2 : '(' + exp2 + ')';
            if (exp1 !== 'NA' && exp2 !== 'NA') {
                exp1 = exp1.length == 1 ? exp1 : '(' + exp1 + ')';
                exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
                return exp1 + '/' + exp2;
            }

        }

        for (let i = 2; i <= 81; i++) {

            // Check if format exp(a,b, 24+i) - exp(c, d, i) works
            exp1 = expression(perm[0], perm[1], target - i);
            exp2 = expression(perm[2], perm[3], i);
            if (exp1 !== 'NA' && exp2 !== 'NA') {
                exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
                exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
                return exp1 + '+' + exp2;
            }

            // Check if format exp(a,b, 24-i) + exp(c, d, i) works
            exp1 = expression(perm[0], perm[1], target + i);
            exp2 = expression(perm[2], perm[3], i);
            if (exp1 !== 'NA' && exp2 !== 'NA') {
                exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
                exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
                return exp1 + '-' + exp2;
            }

        }

        if (numStr[0] == '0') {
            return 'no solution exists';
        }

        exp1 = parseInt(perm[0]);
        if (24 % exp1 == 0) {
            exp2 = solve('0' + perm.slice(1), 24 / exp1);
            if (exp2 !== 'no solution exists') {
                exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
                return exp1 + '*' + exp2;
            }
        }
        exp2 = solve('0' + perm.slice(1), 24 * exp1);
        if (exp2 !== 'no solution exists') {
            exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
            return exp2 + '/' + exp1;
        }
        exp2 = solve('0' + perm.slice(1), 24 + exp1);
        if (exp2 !== 'no solution exists') {
            exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
            return exp2 + '-' + exp1;
        }
        exp2 = solve('0' + perm.slice(1), 24 - exp1);
        if (exp2 !== 'no solution exists') {
            exp2 = exp2.length == 1 ? exp2 : '(' + exp2 + ')';
            return exp1 + '+' + exp2;
        }

    }

    return "no solution exists";

}

function expression(a, b, c) {

    a = parseInt(a);
    b = parseInt(b);
    c = parseInt(c);

    let mx = a > b ? a : b;
    let mn = mx == a ? b : a;

    if (a == 0) {
        return b == c ? b.toString() : 'NA';
    }

    if (b == 0) {
        return a == c ? a.toSring() : 'NA';
    }

    switch (c) {
        case mx + mn:
            return mx + '+' + mn;
        case mx - mn:
            return mx + '-' + mn;
        case mx / mn:
            return mx + '/' + mn;
        case mx * mn:
            return mx + '*' + mn;
        default:
            return 'NA';
    }

}

function getfactors(num) {
    let list = [1];
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            list.push(i);
            list.push(num / i);
        }
    }
    return list;
}

function permutate(numStr, list) {
    let list = [];
    let len = numStr.length;

    if (len == 0) {
        return [];
    }
    if (len == 1) {
        return [numStr];
    }
    if (len == 2) {
        return [numStr, numStr[1].concat(numStr[0])];
    } else {
        let prefix, postfix;
        let permlist = [];
        for (let i = 0; i < len; i++) {
            prefix = numStr.slice(0, i);
            postfix = numStr.slice(i + 1);
            permlist = permutate(prefix + postfix);
            list.push(...permlist.map((a) => numStr[i] + a));
        }
        return list;
    }

}

Challenge: 24 game

Link to the challenge:

2

Can you please update your solution to avoid the use of var since it’s a legacy feature? Use conste everywhere you can and use let where you cannot use const.

It would also help if you use a formatter to update your formatting to something more conventional.

Thanks

3

Solution updated as per feedback.

4

Thanks, I’ll review more and fix your formatting more probably on Monday

5
Summary 
function solve24(numStr) {
  return solveN(numStr, 24);
}

function solveN(numStr, target) {
  const perms = permutate(numStr);
  const factors = getfactors(target);

  for (let perm of perms) {
    let exp1, exp2;

    for (let factor of factors) {
      // Check if format exp(a,b, factor) * exp(c, d, 24/factor) works
      exp1 = expression(perm[0], perm[1], factor);
      exp2 = expression(perm[2], perm[3], target / factor);
      if (exp1 !== 'NA' && exp2 !== 'NA') {
        exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
        exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
        return exp1 + '*' + exp2;
      }
    }

    for (let i = 1; i <= 3; i++) {
      // Check if format exp(a,b, 24*i) / exp(c, d, i) works
      exp1 = expression(perm[0], perm[1], target * i);
      exp2 = expression(perm[2], perm[3], i);
      exp1 = exp1.length > 1 ? exp1 : '(' + exp1 + ')';
      exp2 = exp2.length > 1 ? exp2 : '(' + exp2 + ')';
      if (exp1 !== 'NA' && exp2 !== 'NA') {
        exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
        exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
        return exp1 + '/' + exp2;
      }
    }

    for (let i = 2; i <= 81; i++) {
      // Check if format exp(a,b, 24+i) - exp(c, d, i) works
      exp1 = expression(perm[0], perm[1], target - i);
      exp2 = expression(perm[2], perm[3], i);
      if (exp1 !== 'NA' && exp2 !== 'NA') {
        exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
        exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
        return exp1 + '+' + exp2;
      }

      // Check if format exp(a,b, 24-i) + exp(c, d, i) works
      exp1 = expression(perm[0], perm[1], target + i);
      exp2 = expression(perm[2], perm[3], i);
      if (exp1 !== 'NA' && exp2 !== 'NA') {
        exp1 = exp1.length === 1 ? exp1 : '(' + exp1 + ')';
        exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
        return exp1 + '-' + exp2;
      }
    }

    if (numStr[0] === '0') {
      return 'no solution exists';
    }

    exp1 = parseInt(perm[0]);
    if (target % exp1 === 0) {
      exp2 = solveN('0' + perm.slice(1), target / exp1);
      if (exp2 !== 'no solution exists') {
        exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
        return exp1 + '*' + exp2;
      }
    }
    exp2 = solveN('0' + perm.slice(1), target * exp1);
    if (exp2 !== 'no solution exists') {
      exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
      return exp2 + '/' + exp1;
    }
    exp2 = solveN('0' + perm.slice(1), target + exp1);
    if (exp2 !== 'no solution exists') {
      exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
      return exp2 + '-' + exp1;
    }
    exp2 = solveN('0' + perm.slice(1), target - exp1);
    if (exp2 !== 'no solution exists') {
      exp2 = exp2.length === 1 ? exp2 : '(' + exp2 + ')';
      return exp1 + '+' + exp2;
    }
  }

  return 'no solution exists';
}

function expression(a, b, c) {
  a = parseInt(a);
  b = parseInt(b);
  c = parseInt(c);
  const [min, max] = a < b ? [a, b] : [b, a];

  if (a === 0) {
    return b === c ? b.toString() : 'NA';
  }
  if (b === 0) {
    return a === c ? a.toSring() : 'NA';
  }
  switch (c) {
    case max + min:
      return max + '+' + min;
    case max - min:
      return max + '-' + min;
    case max / min:
      return max + '/' + min;
    case max * min:
      return max + '*' + min;
    default:
      return 'NA';
  }
}

function getfactors(num) {
  const factors = [1];
  const bound = Math.sqrt(num);

  for (let i = 2; i <= bound; i++) {
    if (num % i === 0) factors.push(i, num / i);
  }
  return factors;
}

function permutate(numStr, list) {
  list = [];

  switch (numStr.length) {
    case 0: return [];
    case 1: return [numStr];
    case 2: return [numStr, numStr[1].concat(numStr[0])];
    default:
      for (let i = 0; i < numStr.length; i++) {
        const prefix = numStr.slice(0, i);
        const postfix = numStr.slice(i + 1);
        const permlist = permutate(prefix + postfix);
        list.push(...permlist.map((a) => numStr[i] + a));
      }
      return list;
  }
}

Ok, it looks good to me. I made small updates for conventions and style.

Could you write up a brief explanation of the overall approach so we can post this in the Guide?

7

The challenge is to use the 4 digits of the given number as operands and create an expression that evaluates to 24 using 3 operators. Given that a, b, c, d are the digits, and op1, op2, and op3 are operators, the expression can exist in below formats.

  1. (a op1 b) op2 (c op3 d)
  2. ((a op1 b) op2 c) op3 d

Note that a, b, c and d are interchangeable. So are op1, op2 and op3 which could be any of the four operators (+, -, /, *)

Expression →
We’ll first create a helper function called expression, that will take 3 input parameters → a, b and c. This function will check if any of the below 4 possibilities hold true.

  1. a + b = c
  2. a - b = c
  3. a / b = c
  4. a * b = c

Otherwise, return ‘NA’ meaning it’s not possible to create an expression with a and b that evaluates to c. This function will come in handy when solving the 24 game.

Permutate -
Another helper function we’ll create is permutate. This will return to us all permutations in which the 4 digits of a number can be arranged into the format ‘abcd’. This takes care of the fact that if the original order of a, b, c, d doesn’t work, the numbers can be rearranged to get the solution. We’ll simply take every permutation and see if we get any solution with that ordering.

Now to the actual solution →

  1. get all permutations of the digits a, b, c, d to get all possible orderings

  2. Iterate through each ordering of a, b, c and d. Let’s focus on the format (a op1 b) op2 (c op3 d). Now, there are 4 possibilities for op2 → (*, /, + and -)
    a. Let’s assume op2 to be multiplication (*).
    This leaves us with following possibilities to evaluate to 24 → 1*24, 2*12, 3*8, 4*6.
    Note that all these numbers are factors of 24. Hence, we’ll take help of a function called getfactors to get factors of 24.
    For every factor, we’ll get an expression a op1 b that evaluates to the factor, and c op3 d that evaluates to 24 divided by the factor.
    If we get valid expressions for both, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op2.
    b. Let’s assume op2 to be division (/).
    This leaves us with following possibilities to evaluate to 24 → 24/1, 48/2, 72/3.
    Note that the greatest number we can create from multiplication of 2 operands is 81 (9*9). Hence, we’ll not consider 96/4, 120/5 and so on.
    For every possibility, we’ll get an expression a op1 b that evaluates to (24, 48 or 72), and c op3 d that evaluates to 1, 2 or 3.
    If we get valid expressions for both, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op2.
    c. Let’s assume op2 to be subtraction (-).
    For every possibility, we’ll get an expression a op1 b that evaluates to any number between 2 and 81, and c op3 d that evaluates to 24 plus that number.
    If we get valid expressions for both, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op2.
    d. Let’s assume op2 to be addition (+).
    For every possibility, we’ll get an expression a op1 b that evaluates to any number between 2 and 81, and c op3 d that evaluates to 24 subtracted by that number.
    If we get valid expressions for both, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next step.

  3. At this point, no solution exists with the format (a op1 b) op2 (c op3 d), so we’ll consider the format ((a op1 b) op2 c) op3 d
    Now, we have 4 possible operators for op3. Hence we split the expression into d and (a op1 b) op2 c), which can be rewritten as (a op1 b) op2 (c op4 0). We observe that this expression can be solved from the approach defined in Step #2. Hence, we’ll recursively call our solve function, setting a different target each time. (Now you know why we send 24 as a target into the solve function separately).
    a. Let’s assume op3 to be multiplication (*).
    This tells us that the expression (a op1 b) op2 c should evaluate to 24 divided by d. Hence, we call solve to get a solution for (a op1 b) op2 c , setting input number as 0abc and target as 24 / d.
    If we get a valid expression, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op3.
    b. Let’s assume op3 to be division (/).
    This tells us that the expression (a op1 b) op2 c should evaluate to 24 multiplied by d. Hence, we call solve to get a solution for (a op1 b) op2 c , setting input number as 0abc and target as 24 * d.
    If we get a valid expression, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op3.
    c. Let’s assume op3 to be subtraction (-).
    This tells us that the expression (a op1 b) op2 c should evaluate to 24 + d. Hence, we call solve to get a solution for (a op1 b) op2 c, setting input number as 0abc and target as 24 + d.
    If we get a valid expression, we get a solution that evaluates to 24. Otherwise, no solution is possible and we move on to the next possible operator for op3.
    c. Let’s assume op3 to be addition (+).
    This tells us that the expression (a op1 b) op2 c should evaluate to 24 - d. Hence, we call solve to get a solution for (a op1 b) op2 c, setting input number as 0abc and target as 24 - d.
    If we get a valid expression, we get a solution that evaluates to 24. Otherwise, no solution is possible.

  4. If Steps 2 and 3 don’t yield a solution, then we have checked for all possibilities and no solution exists for given number abcd that evaluates to 24.

8

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.