Short Python


  • 11
    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
    This post is deleted!

  • 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.


  • 1

    @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?


  • 0
    A

    I am getting a syntax error for the use of *rest


  • 0

    @afrozalm You're using the wrong Python version.


  • 0
    I

    I think using itertools.combinations will sightly decrease the complexity but I cannot get the rest part of nums easily. Is there an easy way to do that?


Log in to reply
 

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