Short Python


  • 6
    def judgePoint24(self, nums):
        if len(nums) == 1:
            return math.isclose(nums[0], 24)
        return any(self.judgePoint24([x] + rest)
                   for a, b, *rest in itertools.permutations(nums)
                   for x in {a+b, a-b, a*b, b and a/b})
    

    Just go through all pairs of numbers a and b and replace them with a+b, a-b, a*b and a/b, . Use recursion for the now smaller list. Positive base case is the list being [24] (or close enough).

    I prevent division-by-zero by using b and a/b instead of just a/b. If b is zero, then b and a/b is zero. And it's ok to have that zero, since a*b is zero as well. It's not even a second zero, because I'm creating a set of the up to four operation results, so duplicates are ignored immediately.

    Oh and note that I'm using Python 3, so / is "true" division, not integer division like in Python 2. And it would be better to use fractions.Fraction instead of floats. I actually just realized that there is in fact an input where simple floats fail, namely [3, 3, 8, 8]. Floats calculate 23.999999999999989341858963598497211933135986328125 instead of 24. It's not in the judge's test suite, but it should be soon (Edit: it now is). Using Fraction however made my solution exceed the time limit, so I settled for the above approximation solution.


  • 0

    I get this error "'module' object has no attribute 'isclose'"?


  • 0

    @lee215 You're using the wrong Python version.


  • 0

    Stefan, you are pushing me to use Python. TAT.


  • 0

    @Nakanu Good :-)

    But what is "TAT"?


  • 0

    @StefanPochmann
    It is my crying face, lol.


  • 3
    H

    Thanks! :D
    Here is the C++ version.

    bool judgePoint24(vector<int>& nums){ return judge24({nums.begin(), nums.end()}); }
    
    static bool judge24(vector<double> nums) {
        auto n = nums.size();
        if(n == 1) return abs(nums[0] - 24) < 1e-10;
        
        sort(nums.begin(), nums.end());
        // For each permutation,
        do {
            // merge the last two numbers.
            vector<double> temp(nums.begin(), nums.end()-1);
            auto a = nums[n-1], b = nums[n-2];
            for(auto num: {a+b, a-b, a*b, a?b/a:0}){
                // For each merged number, combine with the rest and test it
                temp.back() = num; 
                if(judge24(temp)) return true;
            }
        } while(next_permutation(nums.begin(), nums.end()));
    
        return false;
    }
    

    EDIT: Modified based on comment


  • 0

    @hsi-hung Your !a?0:b/a looks pessimistic, I'd use a?b/a:0 :-)

    And note that we don't need - and / both ways, I forgot to take that out (It was leftover from an earlier solution of mine).


  • 0
    H

    @StefanPochmann Thanks! I modified the post based on your comment.


  • 0
    Z

    I felt permutation is carried more than enough times.

    to me I think 24 number permutations plus operation combinations should be enough.

    but here permutation is carried out recursively, which is more than needed.


  • 0

    @zinking said in Short Python:

    24 number permutations plus operation combinations should be enough.

    Can you write a solution doing that and show it to us?


  • 0

    Dang! worked my butt off to figure out how to deal with the rest of a and b elegantly
    I ended up did this:

        ...
                self.judgePoint24([o(nums[i], nums[j])] + [nums[k] for k in range(len(nums)) if k not in (i, j)])
                    for i in range(len(nums))
                    for j in range(len(nums)) if i != j
                    for o in ops if nums[j]
        ...
    

    Thanks for your posts, I always learn new things.


  • 0

    @waigx That's how I did it in an earlier version as well :-). Mine has a downside, though, in the top call I go through 4!=24 permutations and thus 24 recursive calls instead of just 4*3=12. But it gets accepted in about 440 ms, so that's not a problem.

    I also wrote a version that prevents those duplicates and more, it gets accepted in about 160 ms:

    def judgePoint24(self, nums):
        if len(nums) == 1:
            return math.isclose(nums[0], 24)
        return any(map(self.judgePoint24,
                       {tuple(sorted([x] + rest))
                        for a, b, *rest in itertools.permutations(nums)
                        for x in (a+b, a-b, a*b, b and a/b)}))
    

    Another version, using global memoization (i.e., across all test cases), fast enough to use Fraction (gets accepted in about 750 ms):

    from functools import lru_cache as memoize
    from fractions import Fraction
    
    class Solution:
        def judgePoint24(self, nums):
            return judge(tuple(sorted(nums)))
    
    @memoize(None)
    def judge(nums):
        if len(nums) == 1:
            return 24 in nums
        return any(map(judge,
                       {tuple(sorted([x] + rest))
                        for a, b, *rest in itertools.permutations(nums)
                        for x in (a+b, a-b, a*b, b and Fraction(a, b))}))
    

  • 0
    E

    @hsi-hung said in Short Python:

    Thanks! :D
    Here is the C++ version.

    bool judgePoint24(vector<int>& nums){ return judge24({nums.begin(), nums.end()}); }
    
    static bool judge24(vector<double> nums) {
        auto n = nums.size();
        if(n == 1) return abs(nums[0] - 24) < 1e-10;
        
        sort(nums.begin(), nums.end());
        // For each permutation,
        do {
            // merge the last two numbers.
            vector<double> temp(nums.begin(), nums.end()-1);
            auto a = nums[n-1], b = nums[n-2];
            for(auto num: {a+b, a-b, a*b, a?b/a:0}){
                // For each merged number, combine with the rest and test it
                temp.back() = num; 
                if(judge24(temp)) return true;
            }
        } while(next_permutation(nums.begin(), nums.end()));
    
        return false;
    }
    

    EDIT: Modified based on comment

    I was wondering if you can explain if there is an general approach to determine what fraction should one check the abs(difference) with as you have used '1e-10' in "abs(nums[0] - 24) < 1e-10"?

    Is there a way to figure out what the appropriate limit is for a fractional difference in such scenarios?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.