Python with explanation - Generate All Possibilities


  • 3
    1. Use itertools.permutations to generate all the possible operands and operators to form an array of length 7, representing an equation of 4 operands and 3 operators.
    2. The possible function tries to evaluate the equation with different combinations of brackets, terminating as soon as an equation evaluates to 24. Each time evaluate is called, it reduces the length of the equation by 2, as it takes a triplet (operand, operator, operand) and evaluates into a value.
    3. Compare the final result of the equation with a small delta because of floating point inaccuracies.

    - Yangshun

    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[0]:
                        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[0] = 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[0]
    
            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
    

  • 1
    A

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


Log in to reply
 

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