This is a Leetcode problem -
You have 4 cards each containing a number from
1
to9
. You need to judge whether they could be operated through*
,/
,+
,-
, (,
) to get the value of24
.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 as12 + 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.