(Leetcode) 24 game in Python

Question

This is a Leetcode problem -

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

Note -

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.

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

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

Here is my solution to this challenge -

class Solution(object):
    def judge_point_24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 1:
            return nums[0] == 24 or abs(nums[0] - 24.0) <= 0.1
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                indexes = set([x for x in range(len(nums))])
                indexes.remove(i)
                indexes.remove(j)
                operations = []
                operations.append(float(nums[i]) + float(nums[j]))
                operations.append(float(nums[i]) - float(nums[j]))
                operations.append(float(nums[j]) - float(nums[i]))
                operations.append(float(nums[i]) * float(nums[j]))
                if nums[j] != 0:
                    operations.append(float(nums[i] / float(nums[j])))
                if nums[i] != 0:
                    operations.append(float(nums[j] / float(nums[i])))
                next_items = [nums[index] for index in indexes]
                for x in operations:
                    if self.judge_point_24(next_items + [x]) == True:
                        return True
        return False

Explanation - My solution is to reduce the nums size until it becomes the size of one. Once it is the size of one, check if we have reached 24 or close enough. Basically, I tried to pick two elements from the array and apply all the possible computations and recursively call itself now with the array that has the result of the computation and the rest. As soon as I see True from the call, I return True as well.

Here are some example outputs -

#output = Solution()

#print(output.judge_point_24([4, 1, 8, 7]))

>>> True

#Explanation - (8-4) * (7-1) = 24

---

#output = Solution()

#print(output.judge_point_24([1, 2, 1, 2]))

>>> False

Here are the times taken for these outputs -

%timeit output.judge_point_24([4, 1, 8, 7])
2.16 ms ± 46 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit output.judge_point_24([1, 2, 1, 2])
43 ms ± 902 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Here is my Leetcode result -

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Answer 1

Docstring

Is nums really of type List[int]? Perhaps the first time it is, but after the first step, it is going to turn into a List[float].

---

Efficiency

Assuming nums is a list of numbers (int or float), you never need to call float() on any of the values. If you expect a list of 4 strings ("1", through "9") from the contest input, turn them into numbers using int(_) and then pass the List[int] to your judge function.

---

The test nums[0] == 24 or abs(nums[0] - 24.0) <= 0.1 could be simplified to just abs(nums[0] - 24.0) <= 0.1.

---

Your doing a lot more work than you think you are. This code is looping through your list, finding pairs of values:

    for i in range(len(nums)):
        for j in range(len(nums)):
            if i == j:
                continue

For each pair, i & j, you compute all possible combinations of those values, including reverse subtraction and reverse division.

And later, you'll encounter the same pair only as j & i! And you'll compute all possible combinations of those values a second time.

If your inner loop started at one index after the current outer loop index, then you'd never generate a pair of indices with i > j ... or even i == j, so you can omit that test as well. Finally, since the inner loop starts at 1 index above the outer loop, the outer loop should end one index early:

    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):

---

You could also use enumerate( ) to loop over the values along with their indices at the same time.

    for i, a in enumerate(nums[:-1]):
        for j, b in enumerate(nums[i+1:], i+1):

And then you can refer to a instead of nums[i], and b instead of nums[j], which will prevent repeated indexing into the nums[] array, which will result in decreased performance.

---

Management of remaining values:

            indexes = set([x for x in range(len(nums))])
            indexes.remove(i)
            indexes.remove(j)
            next_items = [nums[index] for index in indexes]

First set([x for x in range(len(nums))]) could simply be set(range(len(nums))). There is no need for the list comprehension.

But this is still a lot of extra work. Simply copy the numbers to a new list, and then delete the i-th & j-th entries. Since i < j is guaranteed, deleting the j-th element first won't change the location of the i'th element:

            next_items = nums[:]
            del next_items[j]
            del next_items[i]

Or, build up the new list with just the elements you want by omitting the i-th and j-th elements:

            next_items = nums[:i] + nums[i+1:j] + nums[j+1:]

---

2+2 == 2*2 and 1*1 == 1/1 == reverse_div(1,1). It is a small optimization, but instead of making a list of all possible operations values, you could make a set() of the values, which would eliminate some redundant recursive steps.

---

If you don't need this to be a class as a requirement of the leetcode automated judging, you can gain some efficiency by not passing an extra self argument all the time. This can simply be a function.

---

Reworked Code

def judge_point_24(nums):

    for i, a in enumerate(nums[:-1]):
        for j, b in enumerate(nums[i+1:], i+1):
            operations = {a+b, a*b, a-b, b-a}
            if a:
                operations.add(b/a)
            if b:
                operations.add(a/b)

            if len(nums) > 2:
                next_items = nums[:i] + nums[i+1:j] + nums[j+1:]
                for x in operations:
                    if judge_point_24(next_items + [x]) == True:
                        return True
            else:
                return any(abs(x-24) < 0.1 for x in operations)

    return False

if __name__ == '__main__':

    def test(expected, nums):
        print(nums, judge_point_24(nums))
        assert judge_point_24(nums) == expected

    test(True, [4, 1, 8, 7])
    test(False, [1, 2, 1, 2])