"""
Usage: python 8yr.py <desired result> <usable numbers>*
 
Finds (and counts) all possible ways of making <desired result> using (all of) <usable numbers>
without repetitions (except for repetitions present in <usable numbers>), combined using the
standard algebraic operations + - * / (and implicitly including bracketing).
"""
 
usage = """\
Usage: python 8yr.py <desired result> <usable numbers>*
 
Finds (and counts) all possible ways of making <desired result> using (all of) <usable numbers>
without repetitions (except for repetitions present in <usable numbers>), combined using the
standard algebraic operations + - * / (and implicitly including bracketing).
"""
 
 
from itertools import combinations
from collections import Counter
from fractions import Fraction
import sys
import operator
 
def multiset_minus(initial, subtract):
    counter = Counter(initial)
    counter.subtract(subtract)
    return list(counter.elements())
 
def splittings(lst):
    for n_left in range(1, len(lst)):
        for left in combinations(lst, n_left):
            right = multiset_minus(lst, left)
            yield (left, right)
 
def trees(leaf_vals, branch_vals):
    """
    Returns all trees with branch_vals in branches and leaf_vals in leaves,
    where leaves may not repeat and must all appear as leaves, but branch_vals may repeat.
    """
    assert(leaf_vals)
 
    if len(leaf_vals) == 1:
        yield leaf_vals[0]
 
    for (left, right) in splittings(leaf_vals):
        yield from ((branch, ltree, rtree)
                for branch in branch_vals
                for ltree in trees(left, branch_vals)
                for rtree in trees(right, branch_vals))
 
def eval_tree(tree):
    if type(tree) is tuple:
        try:
            return tree[0](*map(eval_tree, tree[1:]))
        except ZeroDivisionError:
            return None
    else:
        return tree
 
def make_num(result, nums, ops):
    """
    Returns all trees in trees(nums, ops) that evaluate to result.
    """
    return (tree for tree in trees(nums, ops)
            if eval_tree(tree) == result)
 
opname_substs = {operator.add: '+', operator.sub: '-', operator.mul: '*', operator.truediv: '/'}
 
def treestr(tree):
    if type(tree) is tuple:
        opname = opname_substs.get(tree[0]) or tree[0].__name__
        left = treestr(tree[1])
        right = treestr(tree[2])
        return f'({opname} {left} {right})'
    else:
        return tree
 
if __name__ == '__main__':
    if len(sys.argv) == 1:
        print(usage)
        sys.exit()
 
    algebraic_ops = [operator.add, operator.sub, operator.mul, operator.truediv]
    desired_result = Fraction(sys.argv[1])
    usable_nums = list(map(Fraction, sys.argv[2:]))
 
    trees = list(make_num(desired_result, usable_nums, algebraic_ops))
 
    for tree in trees:
        print(treestr(tree))
    print(f'Found {len(trees)} solutions.')