Daily Coding Day Three Thirty Four

, ,

This problem was asked by Twitter. Most of these interviews sound like a real fun time. This one is at least a game, but how I wish there was less LBJ style technical interviewing. I think one of the real gotchas here would be floating point precision, because we have to include division. JS solution is after the text. Almost ‘25 time!

The 24 game is played as follows. You are given a list of four integers, each between 1 and 9, in a fixed order. By placing the operators +, -, *, and / between the numbers, and grouping them with parentheses, determine whether it is possible to reach the value 24.

For example, given the input [5, 2, 7, 8], you should return True, since (5 * 2 - 7) * 8 = 24.

Write a function that plays the 24 game.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function canReach24(nums) {
    if (nums.length === 1) {
        return Math.abs(nums[0] - 24) < 0.00001; // Floating point check, to ensure things like 23.99 = 24
    }

    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i === j) continue; // Avoid using the same number twice

            let remaining = nums.filter((_, index) => index !== i && index !== j);

            let possibleResults = [
                nums[i] + nums[j],
                nums[i] - nums[j],
                nums[j] - nums[i],
                nums[i] * nums[j]
            ];

            if (nums[j] !== 0) possibleResults.push(nums[i] / nums[j]);
            if (nums[i] !== 0) possibleResults.push(nums[j] / nums[i]);

            for (let res of possibleResults) {
                if (canReach24([...remaining, res])) return true;
            }
        }
    }

    return false;
}

// Example Usage:
console.log(canReach24([5, 2, 7, 8])); // true
console.log(canReach24([1, 1, 1, 1])); // false
console.log(canReach24([44,18,9,1]))   // unknown