CODEWITHSUNDEEP
pythonalgorithmmathbrute-force
user3125470
user3125470

Reputation: 109

Finding (or brute-forcing) mathematical expression for a list of values and math operations

So I have a list containing some values e.g. [230, 67, 34, 60, 2, 10]
and a list of operations [operations.add, operations.sub, operations.mul, operations.div] and a result number, which I know beforehand.

What would be the best way to find all possible mathematical expressions which give me the result.

For example, if the result is 154, one possible solution would be 60*2+34.

The problem I have in designing this algorithm, is because I don't know beforehand which values and operations will be used for the expression, and which won't, or maybe all will be used.
Would appreciate it if you could provide some python code.
Thanks in advance

Upvotes: 0

Views: 275

Answers (1)

wookie919
wookie919

Reputation: 3134

You could create a tree that represents all possible combinations, where a Node represents either a number or an operator. Then by performing DFS or BFS on the resulting tree, you can find all Nodes such that the expression represented by the path from the root to the Node calculates to the desired value. Here's the code in Python:

class Node():
    def __init__(self, type, val, parent, children):
        self.type = type
        self.value = val
        self.parent = parent
        self.children = children
        self.total = None


def expandBranch(node, numList, opList):

    if len(numList) == 0:
        return

    if node.type == "Operator" or node.type is None:
        for i in range(len(numList)):
            newList = numList[:]
            num = newList.pop(i)
            newNode = Node("Number", num, node, [])
            node.children.append(newNode)
            expandBranch(newNode, newList, opList)
    else:
        for op in opList:
            newNode = Node("Operator", op, node, [])
            node.children.append(newNode)
            expandBranch(newNode, numList, opList)


def dfs(node, result):

    if len(node.children) == 0:
        return

    if node.type == "Number":
        if node.parent.type == None:
            node.total = node.value
        elif node.parent.value == "+":
            node.total = node.parent.total + node.value
        elif node.parent.value == "-":
            node.total = node.parent.total - node.value
        elif node.parent.value == "*":
            node.total = node.parent.total * node.value
        elif node.parent.value == "/":
            node.total = node.parent.total / node.value
        else:
            pass # should never come here
        if node.total == result:
            output = []
            while node.parent is not None:
                output.insert(0, node.value)
                node = node.parent
            print(output)
            return
    elif node.type == "Operator":
        node.total = node.parent.total
    else:
        pass # root node, nothing to do

    for child in node.children:
        dfs(child, result)


def main():
    nums = [230, 67, 34, 60, 2, 10]
    ops = ["+", "-", "*", "/"]
    root = Node(None, None, None, [])
    expandBranch(root, nums, ops)
    dfs(root, 154)

if __name__ == "__main__":
    main()

Which gives the output:

[230, '+', 10, '/', 2, '+', 34]
[67, '+', 10, '*', 2]
[67, '*', 10, '/', 230, '*', 60, '+', 34]
[67, '/', 230, '+', 60, '*', 2, '+', 34]
[67, '/', 230, '+', 2, '*', 60, '+', 34]
[34, '-', 67, '*', 2, '+', 230, '-', 10]
[34, '-', 67, '*', 2, '-', 10, '+', 230]
[34, '-', 2, '*', 67, '/', 10, '-', 60]
[34, '/', 230, '+', 67, '+', 10, '*', 2]
[34, '/', 230, '+', 10, '+', 67, '*', 2]
[34, '/', 60, '+', 67, '+', 10, '*', 2]
[34, '/', 60, '+', 10, '+', 67, '*', 2]
[34, '/', 2, '+', 67, '+', 60, '+', 10]
[34, '/', 2, '+', 67, '+', 10, '+', 60]
[34, '/', 2, '+', 60, '+', 67, '+', 10]
[34, '/', 2, '+', 60, '+', 10, '+', 67]
[34, '/', 2, '+', 10, '+', 67, '+', 60]
[34, '/', 2, '+', 10, '+', 60, '+', 67]
[60, '*', 2, '+', 34]
[60, '/', 230, '+', 67, '+', 10, '*', 2]
[60, '/', 230, '+', 10, '+', 67, '*', 2]
[60, '/', 34, '+', 230, '-', 67, '-', 10]
[60, '/', 34, '+', 230, '-', 10, '-', 67]
[60, '/', 34, '-', 67, '+', 230, '-', 10]
[60, '/', 34, '-', 67, '-', 10, '+', 230]
[60, '/', 34, '-', 10, '+', 230, '-', 67]
[60, '/', 34, '-', 10, '-', 67, '+', 230]
[60, '/', 34, '*', 67, '+', 10, '*', 2]
[60, '/', 34, '*', 10, '+', 67, '*', 2]
[2, '*', 60, '+', 34]
[10, '+', 230, '/', 2, '+', 34]
[10, '+', 67, '*', 2]
[10, '*', 67, '/', 230, '*', 60, '+', 34]
[10, '/', 230, '+', 60, '*', 2, '+', 34]
[10, '/', 230, '+', 2, '*', 60, '+', 34]
[10, '/', 67, '+', 60, '*', 2, '+', 34]
[10, '/', 67, '+', 2, '*', 60, '+', 34]

The code is quite rough and can probably be improved. Note that Integer division will be occurring in the code. Also note that the program will get exponentially slower as you add more numbers to the original list.

Upvotes: 1

Related Questions