itertools.permutationsto generate all the possible operands and operators to form an array of length 7, representing an equation of 4 operands and 3 operators.
possiblefunction tries to evaluate the equation with different combinations of brackets, terminating as soon as an equation evaluates to 24. Each time
evaluateis called, it reduces the length of the equation by 2, as it takes a triplet (operand, operator, operand) and evaluates into a value.
- Compare the final result of the equation with a small delta because of floating point inaccuracies.
By Yang Shun
class Solution(object): def judgePoint24(self, nums): """ :type nums: List[int] :rtype: bool """ import itertools TARGET = 24 EQN_LEN = 3 # (Operand, Operator, Operand) triplet. # Generate all possible number sequences. Convert to float string so that # division does not result in truncation. number_orders = set(tuple(itertools.permutations([str(num) + '.0' for num in nums]))) # Generate all possible operator sequences. operator_orders = set(tuple(itertools.permutations('***///+++---', len(nums) - 1))) # Evaluate an equation with different permutation of brackets # and return True if any of them evaluate to the target. def possible(equation): found = [False] def evaluate(eqn): # Reduces an equation by length 2 each time: # An equation of ['1.0', '*', '2.0', '+', '3.0', '/', '4.0'] becomes: # - [2.0', '+', '3.0', '/', '4.0'] (1.0 * 2.0 reduced to 2.0) # - [1.0', '*', '5.0', '/', '4.0'] (2.0 + 3.0 reduced to 5.0) # - [1.0', '*', '2.0', '+', '0.75'] (3.0 / 4.0 reduced to 0.75) if found: return if len(eqn) == EQN_LEN: val = eval(''.join(eqn)) # Compare against a delta because of floating point inaccuracies. if abs(val - TARGET) < 0.0001: found = True return # Recursively try different permutations # of operands + operators triplets, simulating brackets. for i in range(0, len(eqn) - 1, 2): try: # Wrap in try/except as there can be a division by 0 error. evaluate(eqn[:i] + [str(eval(''.join(eqn[i:i + EQN_LEN])))] + eqn[i + EQN_LEN:]) except: pass evaluate(equation) return found for number_order in number_orders: for operator_order in operator_orders: equation = [None] * (len(number_order) + len(operator_order)) for i, number in enumerate(number_order): equation[0 + i * 2] = number for i, operator in enumerate(operator_order): equation[1 + i * 2] = operator # Generate an equation to test whether it is possible to get 24 using it. # Example equation: ['1.0', '*', '2.0', '+', '3.0', '/', '4.0'] if possible(equation): return True return False
@yangshun Nice solution with some really good explanation in comments. DFS didn't come to my mind at first when I saw the question, now it makes sense. Thanks for posting it.