fork download
copy 
  1. """
  2. Usage: python 8yr.py <desired result> <usable numbers>*
  3.  
  4. Finds (and counts) all possible ways of making <desired result> using (all of) <usable numbers>
  5. without repetitions (except for repetitions present in <usable numbers>), combined using the
  6. standard algebraic operations + - * / (and implicitly including bracketing).
  7. """
  8.  
  9. usage = """\
  10. Usage: python 8yr.py <desired result> <usable numbers>*
  11.  
  12. Finds (and counts) all possible ways of making <desired result> using (all of) <usable numbers>
  13. without repetitions (except for repetitions present in <usable numbers>), combined using the
  14. standard algebraic operations + - * / (and implicitly including bracketing).
  15. """
  16.  
  17.  
  18. from itertools import combinations
  19. from collections import Counter
  20. from fractions import Fraction
  21. import sys
  22. import operator
  23.  
  24. def multiset_minus(initial, subtract):
  25.     counter = Counter(initial)
  26.     counter.subtract(subtract)
  27.     return list(counter.elements())
  28.  
  29. def splittings(lst):
  30.     for n_left in range(1, len(lst)):
  31.         for left in combinations(lst, n_left):
  32.             right = multiset_minus(lst, left)
  33.             yield (left, right)
  34.  
  35. def trees(leaf_vals, branch_vals):
  36.     """
  37.     Returns all trees with branch_vals in branches and leaf_vals in leaves,
  38.     where leaves may not repeat and must all appear as leaves, but branch_vals may repeat.
  39.     """
  40.     assert(leaf_vals)
  41.  
  42.     if len(leaf_vals) == 1:
  43.         yield leaf_vals[0]
  44.  
  45.     for (left, right) in splittings(leaf_vals):
  46.         yield from ((branch, ltree, rtree)
  47.                 for branch in branch_vals
  48.                 for ltree in trees(left, branch_vals)
  49.                 for rtree in trees(right, branch_vals))
  50.  
  51. def eval_tree(tree):
  52.     if type(tree) is tuple:
  53.         try:
  54.             return tree[0](*map(eval_tree, tree[1:]))
  55.         except ZeroDivisionError:
  56.             return None
  57.     else:
  58.         return tree
  59.  
  60. def make_num(result, nums, ops):
  61.     """
  62.     Returns all trees in trees(nums, ops) that evaluate to result.
  63.     """
  64.     return (tree for tree in trees(nums, ops)
  65.             if eval_tree(tree) == result)
  66.  
  67. opname_substs = {operator.add: '+', operator.sub: '-', operator.mul: '*', operator.truediv: '/'}
  68.  
  69. def treestr(tree):
  70.     if type(tree) is tuple:
  71.         opname = opname_substs.get(tree[0]) or tree[0].__name__
  72.         left = treestr(tree[1])
  73.         right = treestr(tree[2])
  74.         return f'({opname} {left} {right})'
  75.     else:
  76.         return tree
  77.  
  78. if __name__ == '__main__':
  79.     if len(sys.argv) == 1:
  80.         print(usage)
  81.         sys.exit()
  82.  
  83.     algebraic_ops = [operator.add, operator.sub, operator.mul, operator.truediv]
  84.     desired_result = Fraction(sys.argv[1])
  85.     usable_nums = list(map(Fraction, sys.argv[2:]))
  86.  
  87.     trees = list(make_num(desired_result, usable_nums, algebraic_ops))
  88.  
  89.     for tree in trees:
  90.         print(treestr(tree))
  91.     print(f'Found {len(trees)} solutions.')
Success #stdin #stdout 0.03s 10284KB
comments (?)
stdin
copy 
111 11 2 1 9
stdout
copy 
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).
https://ideone.com/1vav7Q
language:
Python 3 (python  3.12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!