Find equivalent results by distribution and commutative laws

Question

I have a script that iterates over 5 vectors of numbers and mixes them with all four operations that are looking for a combination that results in a specific target number.

The script prints the output, for example:

312 / 130 x 350 - 122 + 282 = 1000.0 312 / 130 x 350 + 282 - 122 = 1000.0 312 - 282 x 372 / 15 + 256 = 1000.0 142 + 350 - 372 x 125 / 15 = 1000.0 142 + 350 - 372 / 15 x 125 = 1000.0 350 / 130 x 312 + 282 - 122 = 1000.0 350 + 142 - 372 x 125 / 15 = 1000.0 

Each line is formatted from a list of numbers and a list of operations.

What I would like to do is remove the equivalent results , i.e. have an output like:

 312 / 130 x 350 - 122 + 282 = 1000.0 312 - 282 x 372 / 15 + 256 = 1000.0 142 + 350 - 372 x 125 / 15 = 1000.0 

As a solution, at first I thought about “remembering” the numbers that already gave 1000, and skip them, but then I realized that this could obscure the new results, so I don’t know what to do.

How to find equivalent results for distribution and commutative laws?

Note: In the presented output, parentheses are NOT shown, but the order is reduced, which means, for example:

 142 + 350 - 372 x 125 / 15 = 1000.0 

calculated as:

 (((142 + 350) - 372) x 125) / 15 = 1000.0 

---

This is the code that I still have:

 import operator from itertools import permutations, product, count from functools import reduce vectors = [[87, 125, 209, 312], [29, 122, 254, 372], [15, 130, 277, 369], [142, 197, 282, 383], [64, 157, 256, 350]] OPER = {operator.add: '+', operator.sub: '-', operator.mul: 'x', operator.truediv: '/'} def format_result(nums, ops, res): s = ' '.join('{} {}'.format(n,OPER[op]) for n,op in zip(nums, ops)) s += ' {} = {}'.format(nums[-1], res) return s def calc(vectors, test=lambda x: x == 1000.): for vv in permutations(vectors): for indexes in product((0,1,2,3), repeat=5): numbers = tuple(v[i] for i,v in zip(indexes, vv)) for operations in permutations(OPER): res = reduce(lambda x,y,n=count(0): operations[next(n)](x,y), numbers) if test(res): print(format_result(numbers, operations, res)) calc(vectors) 

Answer 1

I think this problem can be approached by grouping operands in accordance with the operations performed on them. Example:

 312 / 130 x 350 + 122 + 282 => (/, [312, 130]), (x, [350]), (+, [122, 282]) 

Then you can set certain restrictions on the order of these groups:

• - groups cannot meet immediately before + groups of the Group
• / cannot occur immediately before * groups
• within each group, the order of numbers should be increasing.

Possible groupings look like this:

• "first 3 asc. operands associated with + , then 2 asc. operands associated with * "
• "first 1 asc. operand associated with + , then 2 asc. operands associated with * , then 2 asc. operands associated with / "

It would be impossible for something like this:

• "first 2 asc. operands associated with - , then 3 asc. operands associated with + " (would collide with "first 3 asc. operands associated with + , and then with two operands asc. -

I tried to use brute force to create and fill such groups, but it is unbearably slow. Perhaps you can optimize it to be more efficient :) It may also be that there is some kind of subtle mistake, but, unfortunately, I do not have more time to work on it:

 import operator import fractions from itertools import permutations, product, count from functools import reduce vectors = [[87, 125, 209, 312], [29, 122, 254, 372], [15, 130, 277, 369], [142, 197, 282, 383], [64, 157, 256, 350]] vectors = [[fractions.Fraction(x) for x in v] for v in vectors] operators = { '+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.div, } def create_groupings(n, exclude = ()): if n <= 0: yield () for i in range(1, n+1): if not '+' in exclude: for rest in create_groupings(n - i, ('+',)): yield ((i, '+'),) + rest if not '-' in exclude: for rest in create_groupings(n - i, ('+', '-')): yield ((i, '-'),) + rest if not '*' in exclude: for rest in create_groupings(n - i, ('*',)): yield ((i, '*'),) + rest if not '/' in exclude: for rest in create_groupings(n - i, ('/', '*')): yield ((i, '/'),) + rest def fill_grouping(groups, vectors): if len(groups) == 0: yield () return (group_size, op), grest = groups[0], groups[1:] for vv in permutations(vectors): vecs, vrest = vectors[:group_size], vectors[group_size:] for operands in map(list, product(*vecs)): # enforce ascending ordering to avoid collisions # like A + B == B + A if operands != sorted(operands): continue for rest in fill_grouping(grest, vrest): yield ((op, operands),) + rest groupings = create_groupings(5) for g in groupings: for groups in fill_grouping(g, vectors): evaluated = ((op, reduce(operators[op], x)) for (op, x) in groups) _, value = reduce(lambda (_, x), (op, y): (None, operators[op](x,y)), evaluated) if 1000 == value: print groups 

Hope this helps (at least the idea :)