Find mathematical expression which is equals a given number using a set of numbers

Problem Statement

Goal of this exercise is to write code which accepts a set of numbers and then tries to devise an arithmetic expression that yields a requested value, using four basic arithmetic operations: addition, subtraction, multiplication and division. Each input number must be used exactly once in the expression. Division is applicable only to numbers that are divisible without remainder. All input numbers and the target number are integers greater than zero. There are no more than 5 input numbers and target number is not larger than 1000. Example 1: Suppose that numbers 4, 8 and 9 are given and value 18 should be constructed. One solution is: 9 * 8 / 4. Example 2: If numbers 6, 7 and 9 are given, number 3 requested, then solution is: 6 / (9 - 7).

References

Python implementation of the solution posted at http://www.codinghelmet.com/?path=exercises/expression-from-numbers


In [18]:
from Queue import Queue

In [14]:
def SolveAndPrint(numbers, targetValue):
    targetKey = (targetValue << len(numbers)) + (1 << len(numbers)) - 1
    # (value << numbers.Length) represents expression value
    # (1 << numbers.Length) - 1 represents mask with all bits set to 1,
    # i.e. mask in which each input number has been used exactly once
    # to build the expression.
    
    solvedKeys = set()
    # Each number in the collection indicates that corresponding value + mask
    # has been reached using arithmetical operations.
    
    keyToLeftParent  = dict()
    # For each solved key (value + mask), there is an entry indicating
    # result of the expression on the left side of the arithmetic
    # operator. Missing value indicates that key represents the
    # raw number (taken from the input list), rather than
    # the result of a calculation.
    
    keyToRightParent = dict()
    # Same as keyToLeftParent, only indicating the right parent
    # used to build the expression.
    
    keyToOperator = dict()
    # Indicates arithmetic operator used to build this node
    # from left and right parent nodes. Missing value for a given key
    # indicates that key is a raw value taken from input array,
    # rather than result of an arithmetic operation.
    
    queue = Queue()
    # Keys (value + mask pairs) that have not been processed yet

    # First step is to initialize the structures:
    # Add all input values into corresponding array entries and
    # add them to the queue so that the operation can begin
    for i in range(len(numbers)):
        key = (numbers[i] << len(numbers)) + (1 << i)
        solvedKeys.add(key)
        queue.put(key)
    
    # Now expand entries one at the time until queue is empty,
    # i.e. until there are no new entries populated.
    # Additional stopping condition is that target key has been generated,
    # which indicates that problem has been solved and there is no need to
    # expand nodes any further.
    while (not queue.empty() > 0 and (targetKey not in solvedKeys)):
        curKey = queue.get()

        curMask = curKey & ((1 << len(numbers)) - 1)
        curValue = curKey >> len(numbers)
        
        # Now first take a snapshot of all keys that
        # have been reached because this collection is going to
        # change during the following operation
        keys = solvedKeys.copy()

        for keys_i in keys:
            mask = keys_i & ((1 << len(numbers)) - 1)
            value = keys_i >> len(numbers)

            if ((mask & curMask) == 0):
                # Masks are disjoint, i.e. two entries do not use
                # the same input number twice.
                # This is sufficient condition to combine the two entries
                for op in range(6):
                    opSign = '\0'
                    newValue = 0
                    if op == 0: # Addition
                        newValue = curValue + value
                        opSign = '+'
                    elif op == 1: # Subtraction - another value subtracted from current
                        newValue = curValue - value
                        opSign = '-'
                    elif op == 2: # Subtraction - current value subtracted from another
                        newValue = value - curValue
                        opSign = '-'
                    elif op == 3: # Multiplication
                        newValue = curValue * value
                        opSign = '*'
                    elif op == 4: # Division - current divided by another
                        newValue = -1  # Indicates failure to divide
                        if (value != 0 and curValue % value == 0):
                            newValue = curValue / value
                        opSign = '/'
                    elif op == 5: # Division - other value divided by current
                        newValue = -1  # Indicates failure to divide
                        if (curValue != 0 and value % curValue == 0):
                            newValue = value / curValue
                        opSign = '/'

                    if (newValue >= 0):
                        # Ignore negative values - they can always be created
                        # the other way around, by subtracting them
                        # from a larger value so that positive value is reached.
                        newMask = (curMask | mask)
                        # Combine the masks to indicate that all input numbers
                        # from both operands have been used to produce
                        # the resulting expression
                        
                        newKey = (newValue << len(numbers)) + newMask
                        if (newKey not in solvedKeys):
                            # We have reached a new entry.
                            # This expression should now be added
                            # to data structures and processed further
                            # in the following steps.

                            # Populate entries that describe newly created expression
                            solvedKeys.add(newKey);
                            if (op == 2 or op == 5):
                                # Special cases - antireflexive operations
                                # with interchanged operands
                                keyToLeftParent[newKey]= keys_i
                                keyToRightParent[newKey] =  curKey
                            else:
                                keyToLeftParent[newKey] = curKey
                                keyToRightParent[newKey]= keys_i
                            keyToOperator[newKey] = opSign
                            # Add expression to list of reachable expressions
                            solvedKeys.add(newKey)
                            # Add expression to the queue for further expansion
                            queue.put(newKey)
    # Now print the solution if it has been found
    if (targetKey not in solvedKeys):
        print "Solution has not been found."
    else:
        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, targetKey, len(numbers))
        print "={0}".format(targetValue)

In [15]:
def PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, key, numbersCount):
    if (key not in keyToOperator):
        print "{0}".format(key >> numbersCount),
    else:
        print "(",
        # Recursively print the left operand
        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, keyToLeftParent[key], numbersCount)
        # Then print the operation sign
        print keyToOperator[key],
        # Finally, print the right operand
        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, keyToRightParent[key], numbersCount)
        print ")",

In [23]:
SolveAndPrint([2,2,22], 24)


Solution has not been found.

In [ ]: