The 24 Game Algorithm using Depth First Search

  • 时间:2020-09-23 15:11:59
  • 分类:网络文摘
  • 阅读:94 次

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:
Input: [1, 2, 1, 2]
Output: False

Note:
The division operator / represents real division, not integer division. For example, 4 / (1 – 2/3) = 12.
Every operation done is between two numbers. In particular, we cannot use – as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 – 1 – 1 – 1 is not allowed.

You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

In 24 Point Poker Game Calculator, the complete list of the 24-game solutions has been implemented using PHP, via the bruteforce algorithm by iterating all possible solutions (which might contain duplicates such as communitive laws a+b=b+a).

Simple Depth First Search Algorithm to Check if 4 cards can make up to 24

As there are only four numbers, and four operators which are addition, subtraction, multiplication and divisor, the total solution space is constant.

The Depth First Search Algorithm will operate on a vector. The algorithm will bruteforce all pairs of the numbers in the vector, and apply four operators on these two numbers, push the result to the vector, and recursively calling itself until there is only 1 number in the vector – which we can easily check if it is 24 – remember, the types in the vector should be double i.e. converting the input integers to the doubles first.

As multiplication and additions are communitive so that we can slightly speed the process up by ignoring the pairs by comparing the indices.

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
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> arr;
        for (const auto &n: nums) {
            arr.push_back(n);
        }
        return search(arr);
    }
    
private:
    bool search(vector<double>& nums) {
        if (nums.empty()) return false;
        if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6;        
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = 0; j < nums.size(); ++ j) {
                if (i == j) continue;
                vector<double> nums2;
                for (int k = 0; k < nums.size(); ++ k) {
                    if (k != i && k != j) {
                        nums2.push_back(nums[k]);
                    }
                }
                for (int k = 0; k < 4; ++ k) {
                    if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication
                    switch (k) {
                        case 0: nums2.push_back(nums[i] + nums[j]); break;
                        case 1: nums2.push_back(nums[i] * nums[j]); break;
                        case 2: nums2.push_back(nums[i] - nums[j]); break;
                        case 3: 
                            if (nums[j] != 0) {
                                nums2.push_back(nums[i] / nums[j]); 
                            } else {
                                continue;    
                            }
                            break;                            
                    }
                    if (search(nums2)) return true;
                    nums2.pop_back();                    
                }
            }
        }
        return false;
    }
};
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> arr;
        for (const auto &n: nums) {
            arr.push_back(n);
        }
        return search(arr);
    }
    
private:
    bool search(vector<double>& nums) {
        if (nums.empty()) return false;
        if (nums.size() == 1) return abs(nums[0] - 24) < 1e-6;        
        for (int i = 0; i < nums.size(); ++ i) {
            for (int j = 0; j < nums.size(); ++ j) {
                if (i == j) continue;
                vector<double> nums2;
                for (int k = 0; k < nums.size(); ++ k) {
                    if (k != i && k != j) {
                        nums2.push_back(nums[k]);
                    }
                }
                for (int k = 0; k < 4; ++ k) {
                    if ((k < 2) && (j > i)) continue; // ignoring communitive additions and multiplication
                    switch (k) {
                        case 0: nums2.push_back(nums[i] + nums[j]); break;
                        case 1: nums2.push_back(nums[i] * nums[j]); break;
                        case 2: nums2.push_back(nums[i] - nums[j]); break;
                        case 3: 
                            if (nums[j] != 0) {
                                nums2.push_back(nums[i] / nums[j]); 
                            } else {
                                continue;    
                            }
                            break;                            
                    }
                    if (search(nums2)) return true;
                    nums2.pop_back();                    
                }
            }
        }
        return false;
    }
};

Special case has to be handled when checking the divisor being zero. The complexity of the algorithm is O(1) an the space complexity is also O(1) as they both do not grow as the size of the problem grows.

Remember to play at: 24 Point Poker Game Calculator

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
凤凰卫视香港台直播「高清」  香港卫视直播「高清」  阳光卫视在线直播「高清」  亚洲联合卫视直播「高清」  香港TVB8直播「高清」  卫视体育台直播_星空卫视体育台直播观看「高清」  华娱卫视在线直播「高清」  新城财经台直播「高清」  香港本港台直播-亚洲电视本港台直播-atv直播「高清」  深度剖析:电脑打板的全过程-故障排查 
评论列表
添加评论