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).
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)
In [ ]: