fork(4) download 
  1. sets = [None] * 2**7
  2. best_diff = 1000
  3. best_item = None
  4.  
  5.  
  6. def get_group(op):
  7.     if op == '+' or op == '-':
  8.         return '+'
  9.  
  10.     if op == '*' or op == '/':
  11.         return '*'
  12.  
  13.     return '#'
  14.  
  15.  
  16. def commut_group(op):
  17.     if op == '+' or op == '*':
  18.         return op
  19.     else:
  20.         return '#'
  21.  
  22.  
  23. def to_str(node, group): # (left, right, display, value)
  24.     left = right = lp = rp = ""
  25.  
  26.     if (node[0]):
  27.         op_group = get_group(node[2])
  28.         left = to_str(node[0], op_group)
  29.         right = to_str(node[1], commut_group(node[2]))
  30.  
  31.         if group == '#' or (group == '*' and op_group == '+'):
  32.             lp = '('; rp = ')'
  33.  
  34.     return lp + left + node[2]  + right + rp
  35.  
  36.  
  37. def move_node(to_tree, from_tree):
  38.     op = from_tree[2]
  39.  
  40.     if op == 'T':
  41.         return to_tree
  42.  
  43.     if from_tree[0][3] != None: # target to the right
  44.         if op == '+':
  45.             value = to_tree[3] - from_tree[0][3]
  46.             node = (to_tree, from_tree[0], '-', value)
  47.             return move_node(node, from_tree[1])
  48.         if op == '-':
  49.             value = from_tree[0][3] - to_tree[3]
  50.             node = (from_tree[0], to_tree, '-', value)
  51.             return move_node(node, from_tree[1])
  52.         if op == '*':
  53.             if from_tree[0][3] == 0:
  54.                 return (None, None, '0', 0)
  55.             value = to_tree[3] / from_tree[0][3]
  56.             node = (to_tree, from_tree[0], '/', value)
  57.             return move_node(node, from_tree[1])
  58.         if op == '/':
  59.             if to_tree[3] == 0:
  60.                 return (None, None, '0', 0)
  61.             value = from_tree[0][3] / to_tree[3]
  62.             node = (from_tree[0], to_tree, '/', value)
  63.             return move_node(node, from_tree[1])
  64.     else: # target to the left
  65.         if op == '+':
  66.             value = to_tree[3] - from_tree[1][3]
  67.             node = (to_tree, from_tree[1], '-', value)
  68.             return move_node(node, from_tree[0])
  69.         if op == '-':
  70.             value = to_tree[3] + from_tree[1][3]
  71.             node = (to_tree, from_tree[1], '+', value)
  72.             return move_node(node, from_tree[0])
  73.         if op == '*':
  74.             if from_tree[1][3] == 0:
  75.                 return (None, None, '0', 0)
  76.             value = to_tree[3] / from_tree[1][3]
  77.             node = (to_tree, from_tree[1], '/', value)
  78.             return move_node(node, from_tree[0])
  79.         if op == '/':
  80.             value = to_tree[3] * from_tree[1][3]
  81.             node = (to_tree, from_tree[1], '*', value)
  82.             return move_node(node, from_tree[0])
  83.  
  84.  
  85. def join(x, y):
  86.     if x[3] != None:
  87.         return move_node(x, y)
  88.     else:
  89.         return move_node(y, x)
  90.  
  91.  
  92. def val_none(value, target):
  93.     if target:
  94.         return None
  95.     else:
  96.         return value
  97.  
  98.  
  99. def merge(x, y, target):
  100.     res = {}
  101.  
  102.     for v1, s1 in x:
  103.         for v2, s2 in y:
  104.             res[v1 + v2] = (s1, s2, '+', val_none(v1 + v2, target))
  105.  
  106.             if v1 != 0 and v2 != 0:
  107.                 res[v1 * v2] = (s1, s2, '*', val_none(v1 * v2, target))
  108.  
  109.             for va, sa, vb, sb in ((v1, s1, v2, s2), (v2, s2, v1, s1)):
  110.                 res[va - vb] = (sa, sb, '-', val_none(va - vb, target))
  111.  
  112.                 if va != 0 and vb != 0:
  113.                     res[va / vb] = (sa, sb, '/', val_none(va / vb, target))
  114.  
  115.     return res
  116.  
  117.  
  118. def mrange(mask):
  119.     x = 0
  120.  
  121.     while x != mask:
  122.         x = (x - mask) & mask
  123.         yield x
  124.  
  125.  
  126. def is_single_not_root(x):
  127.     return (x & 1) == 0 and (x & (x - 1)) == 0
  128.  
  129.  
  130. def is_single(x):
  131.     return (x & (x - 1)) == 0
  132.  
  133.  
  134. def fill(pos):
  135.     cnt = bin(pos).count('1')
  136.     if sets[pos] or cnt > 4:
  137.         return
  138.  
  139.     results = {}
  140.  
  141.     for x in mrange(pos & (pos - 1)):
  142.         y = pos ^ x
  143.  
  144.         if cnt < 4 or (pos & 1) or not (is_single(x) or is_single(y)):
  145.             results.update(merge(sets[x], sets[y], (pos & 1) != 0))
  146.  
  147.         if is_single_not_root(x):
  148.             results.update(sets[y]) # x not used
  149.  
  150.         if is_single_not_root(y):
  151.             results.update(sets[x]) # y not used
  152.  
  153.     sets[pos] = sorted(results.items())
  154.  
  155.  
  156. def get_best(x, y):
  157.     global best_diff, best_item
  158.     joined = join(x[1], y[1])
  159.  
  160.     if joined[3] > 0 and abs(joined[3] - sets[1][0][0]) < best_diff:
  161.         best_diff = abs(joined[3] - sets[1][0][0])
  162.         best_item = joined
  163.  
  164.  
  165. def match(x, y):
  166.     pos_x = 0
  167.     pos_y = 0
  168.  
  169.     while pos_x < len(x) and pos_y < len(y):
  170.         get_best(x[pos_x], y[pos_y])
  171.  
  172.         if x[pos_x][0] < y[pos_y][0]:
  173.             pos_x += 1
  174.         else:
  175.             if x[pos_x][0] > y[pos_y][0]:
  176.                 pos_y += 1
  177.             else:
  178.                 pos_x += 1; pos_y += 1
  179.  
  180.  
  181. def scan():
  182.     for i in xrange(1, 7):
  183.         for j in xrange(1, i):
  184.             pos_with_root = 1 | (1 << i) | (1 << j)
  185.             pos_no_root = ((1 << 7) - 1) ^ pos_with_root
  186.             match(sets[pos_with_root], sets[pos_no_root])
  187.  
  188.             for k in xrange(1, j):
  189.                 match(sets[pos_with_root | (1 << k)],
  190.                       sets[pos_no_root & ~(1 << k)])
  191.  
  192.  
  193. def search(numbers, target):
  194.     sets[1] = [(target, (None, None, "T", None))]
  195.  
  196.     for i in range(6):
  197.         sets[2 ** (i + 1)] = \
  198.             [(float(numbers[i]),
  199.               (None, None, str(numbers[i]), float(numbers[i])))]
  200.  
  201.     for i in range(3, 2**7):
  202.         fill(i)
  203.  
  204.     scan()
  205.  
  206.     return to_str(best_item, '=') + " -> " + str(best_item[3])
  207.  
  208.  
  209. print search([4, 8, 6, 2, 15, 50], 590)
  210.  
Success #stdin #stdout 0.32s 7852KB
comments (?)
stdin 
Standard input is empty
stdout 
(50+15-(8-2))*(6+4) -> 590.0
https://ideone.com/SUKrgL
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
secret

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!