sets = [None] * 2**7
best_diff = 1000
best_item = None
def get_group(op):
if op == '+' or op == '-':
return '+'
if op == '*' or op == '/':
return '*'
return '#'
def commut_group(op):
if op == '+' or op == '*':
return op
else:
return '#'
def to_str(node, group): # (left, right, display, value)
left = right = lp = rp = ""
if (node[0]):
op_group = get_group(node[2])
left = to_str(node[0], op_group)
right = to_str(node[1], commut_group(node[2]))
if group == '#' or (group == '*' and op_group == '+'):
lp = '('; rp = ')'
return lp + left + node[2] + right + rp
def move_node(to_tree, from_tree):
op = from_tree[2]
if op == 'T':
return to_tree
if from_tree[0][3] != None: # target to the right
if op == '+':
value = to_tree[3] - from_tree[0][3]
node = (to_tree, from_tree[0], '-', value)
return move_node(node, from_tree[1])
if op == '-':
value = from_tree[0][3] - to_tree[3]
node = (from_tree[0], to_tree, '-', value)
return move_node(node, from_tree[1])
if op == '*':
if from_tree[0][3] == 0:
return (None, None, '0', 0)
value = to_tree[3] / from_tree[0][3]
node = (to_tree, from_tree[0], '/', value)
return move_node(node, from_tree[1])
if op == '/':
if to_tree[3] == 0:
return (None, None, '0', 0)
value = from_tree[0][3] / to_tree[3]
node = (from_tree[0], to_tree, '/', value)
return move_node(node, from_tree[1])
else: # target to the left
if op == '+':
value = to_tree[3] - from_tree[1][3]
node = (to_tree, from_tree[1], '-', value)
return move_node(node, from_tree[0])
if op == '-':
value = to_tree[3] + from_tree[1][3]
node = (to_tree, from_tree[1], '+', value)
return move_node(node, from_tree[0])
if op == '*':
if from_tree[1][3] == 0:
return (None, None, '0', 0)
value = to_tree[3] / from_tree[1][3]
node = (to_tree, from_tree[1], '/', value)
return move_node(node, from_tree[0])
if op == '/':
value = to_tree[3] * from_tree[1][3]
node = (to_tree, from_tree[1], '*', value)
return move_node(node, from_tree[0])
def join(x, y):
if x[3] != None:
return move_node(x, y)
else:
return move_node(y, x)
def val_none(value, target):
if target:
return None
else:
return value
def merge(x, y, target):
res = {}
for v1, s1 in x:
for v2, s2 in y:
res[v1 + v2] = (s1, s2, '+', val_none(v1 + v2, target))
if v1 != 0 and v2 != 0:
res[v1 * v2] = (s1, s2, '*', val_none(v1 * v2, target))
for va, sa, vb, sb in ((v1, s1, v2, s2), (v2, s2, v1, s1)):
res[va - vb] = (sa, sb, '-', val_none(va - vb, target))
if va != 0 and vb != 0:
res[va / vb] = (sa, sb, '/', val_none(va / vb, target))
return res
def mrange(mask):
x = 0
while x != mask:
x = (x - mask) & mask
yield x
def is_single_not_root(x):
return (x & 1) == 0 and (x & (x - 1)) == 0
def is_single(x):
return (x & (x - 1)) == 0
def fill(pos):
cnt = bin(pos).count('1')
if sets[pos] or cnt > 4:
return
results = {}
for x in mrange(pos & (pos - 1)):
y = pos ^ x
if cnt < 4 or (pos & 1) or not (is_single(x) or is_single(y)):
results.update(merge(sets[x], sets[y], (pos & 1) != 0))
if is_single_not_root(x):
results.update(sets[y]) # x not used
if is_single_not_root(y):
results.update(sets[x]) # y not used
sets[pos] = sorted(results.items())
def get_best(x, y):
global best_diff, best_item
joined = join(x[1], y[1])
if joined[3] > 0 and abs(joined[3] - sets[1][0][0]) < best_diff:
best_diff = abs(joined[3] - sets[1][0][0])
best_item = joined
def match(x, y):
pos_x = 0
pos_y = 0
while pos_x < len(x) and pos_y < len(y):
get_best(x[pos_x], y[pos_y])
if x[pos_x][0] < y[pos_y][0]:
pos_x += 1
else:
if x[pos_x][0] > y[pos_y][0]:
pos_y += 1
else:
pos_x += 1; pos_y += 1
def scan():
for i in xrange(1, 7):
for j in xrange(1, i):
pos_with_root = 1 | (1 << i) | (1 << j)
pos_no_root = ((1 << 7) - 1) ^ pos_with_root
match(sets[pos_with_root], sets[pos_no_root])
for k in xrange(1, j):
match(sets[pos_with_root | (1 << k)],
sets[pos_no_root & ~(1 << k)])
def search(numbers, target):
sets[1] = [(target, (None, None, "T", None))]
for i in range(6):
sets[2 ** (i + 1)] = \
[(float(numbers[i]),
(None, None, str(numbers[i]), float(numbers[i])))]
for i in range(3, 2**7):
fill(i)
scan()
return to_str(best_item, '=') + " -> " + str(best_item[3])
print search([4, 8, 6, 2, 15, 50], 590)
c2V0cyA9IFtOb25lXSAqIDIqKjcKYmVzdF9kaWZmID0gMTAwMApiZXN0X2l0ZW0gPSBOb25lCgoKZGVmIGdldF9ncm91cChvcCk6CiAgICBpZiBvcCA9PSAnKycgb3Igb3AgPT0gJy0nOgogICAgICAgIHJldHVybiAnKycKCiAgICBpZiBvcCA9PSAnKicgb3Igb3AgPT0gJy8nOgogICAgICAgIHJldHVybiAnKicKCiAgICByZXR1cm4gJyMnCgoKZGVmIGNvbW11dF9ncm91cChvcCk6CiAgICBpZiBvcCA9PSAnKycgb3Igb3AgPT0gJyonOgogICAgICAgIHJldHVybiBvcAogICAgZWxzZToKICAgICAgICByZXR1cm4gJyMnCgoKZGVmIHRvX3N0cihub2RlLCBncm91cCk6ICMgKGxlZnQsIHJpZ2h0LCBkaXNwbGF5LCB2YWx1ZSkKICAgIGxlZnQgPSByaWdodCA9IGxwID0gcnAgPSAiIgoKICAgIGlmIChub2RlWzBdKToKICAgICAgICBvcF9ncm91cCA9IGdldF9ncm91cChub2RlWzJdKQogICAgICAgIGxlZnQgPSB0b19zdHIobm9kZVswXSwgb3BfZ3JvdXApCiAgICAgICAgcmlnaHQgPSB0b19zdHIobm9kZVsxXSwgY29tbXV0X2dyb3VwKG5vZGVbMl0pKQoKICAgICAgICBpZiBncm91cCA9PSAnIycgb3IgKGdyb3VwID09ICcqJyBhbmQgb3BfZ3JvdXAgPT0gJysnKToKICAgICAgICAgICAgbHAgPSAnKCc7IHJwID0gJyknCgogICAgcmV0dXJuIGxwICsgbGVmdCArIG5vZGVbMl0gICsgcmlnaHQgKyBycAoKCmRlZiBtb3ZlX25vZGUodG9fdHJlZSwgZnJvbV90cmVlKToKICAgIG9wID0gZnJvbV90cmVlWzJdCgogICAgaWYgb3AgPT0gJ1QnOgogICAgICAgIHJldHVybiB0b190cmVlCgogICAgaWYgZnJvbV90cmVlWzBdWzNdICE9IE5vbmU6ICMgdGFyZ2V0IHRvIHRoZSByaWdodAogICAgICAgIGlmIG9wID09ICcrJzoKICAgICAgICAgICAgdmFsdWUgPSB0b190cmVlWzNdIC0gZnJvbV90cmVlWzBdWzNdCiAgICAgICAgICAgIG5vZGUgPSAodG9fdHJlZSwgZnJvbV90cmVlWzBdLCAnLScsIHZhbHVlKQogICAgICAgICAgICByZXR1cm4gbW92ZV9ub2RlKG5vZGUsIGZyb21fdHJlZVsxXSkKICAgICAgICBpZiBvcCA9PSAnLSc6CiAgICAgICAgICAgIHZhbHVlID0gZnJvbV90cmVlWzBdWzNdIC0gdG9fdHJlZVszXQogICAgICAgICAgICBub2RlID0gKGZyb21fdHJlZVswXSwgdG9fdHJlZSwgJy0nLCB2YWx1ZSkKICAgICAgICAgICAgcmV0dXJuIG1vdmVfbm9kZShub2RlLCBmcm9tX3RyZWVbMV0pCiAgICAgICAgaWYgb3AgPT0gJyonOgogICAgICAgICAgICBpZiBmcm9tX3RyZWVbMF1bM10gPT0gMDoKICAgICAgICAgICAgICAgIHJldHVybiAoTm9uZSwgTm9uZSwgJzAnLCAwKQogICAgICAgICAgICB2YWx1ZSA9IHRvX3RyZWVbM10gLyBmcm9tX3RyZWVbMF1bM10KICAgICAgICAgICAgbm9kZSA9ICh0b190cmVlLCBmcm9tX3RyZWVbMF0sICcvJywgdmFsdWUpCiAgICAgICAgICAgIHJldHVybiBtb3ZlX25vZGUobm9kZSwgZnJvbV90cmVlWzFdKQogICAgICAgIGlmIG9wID09ICcvJzoKICAgICAgICAgICAgaWYgdG9fdHJlZVszXSA9PSAwOgogICAgICAgICAgICAgICAgcmV0dXJuIChOb25lLCBOb25lLCAnMCcsIDApCiAgICAgICAgICAgIHZhbHVlID0gZnJvbV90cmVlWzBdWzNdIC8gdG9fdHJlZVszXQogICAgICAgICAgICBub2RlID0gKGZyb21fdHJlZVswXSwgdG9fdHJlZSwgJy8nLCB2YWx1ZSkKICAgICAgICAgICAgcmV0dXJuIG1vdmVfbm9kZShub2RlLCBmcm9tX3RyZWVbMV0pCiAgICBlbHNlOiAjIHRhcmdldCB0byB0aGUgbGVmdAogICAgICAgIGlmIG9wID09ICcrJzoKICAgICAgICAgICAgdmFsdWUgPSB0b190cmVlWzNdIC0gZnJvbV90cmVlWzFdWzNdCiAgICAgICAgICAgIG5vZGUgPSAodG9fdHJlZSwgZnJvbV90cmVlWzFdLCAnLScsIHZhbHVlKQogICAgICAgICAgICByZXR1cm4gbW92ZV9ub2RlKG5vZGUsIGZyb21fdHJlZVswXSkKICAgICAgICBpZiBvcCA9PSAnLSc6CiAgICAgICAgICAgIHZhbHVlID0gdG9fdHJlZVszXSArIGZyb21fdHJlZVsxXVszXQogICAgICAgICAgICBub2RlID0gKHRvX3RyZWUsIGZyb21fdHJlZVsxXSwgJysnLCB2YWx1ZSkKICAgICAgICAgICAgcmV0dXJuIG1vdmVfbm9kZShub2RlLCBmcm9tX3RyZWVbMF0pCiAgICAgICAgaWYgb3AgPT0gJyonOgogICAgICAgICAgICBpZiBmcm9tX3RyZWVbMV1bM10gPT0gMDoKICAgICAgICAgICAgICAgIHJldHVybiAoTm9uZSwgTm9uZSwgJzAnLCAwKQogICAgICAgICAgICB2YWx1ZSA9IHRvX3RyZWVbM10gLyBmcm9tX3RyZWVbMV1bM10KICAgICAgICAgICAgbm9kZSA9ICh0b190cmVlLCBmcm9tX3RyZWVbMV0sICcvJywgdmFsdWUpCiAgICAgICAgICAgIHJldHVybiBtb3ZlX25vZGUobm9kZSwgZnJvbV90cmVlWzBdKQogICAgICAgIGlmIG9wID09ICcvJzoKICAgICAgICAgICAgdmFsdWUgPSB0b190cmVlWzNdICogZnJvbV90cmVlWzFdWzNdCiAgICAgICAgICAgIG5vZGUgPSAodG9fdHJlZSwgZnJvbV90cmVlWzFdLCAnKicsIHZhbHVlKQogICAgICAgICAgICByZXR1cm4gbW92ZV9ub2RlKG5vZGUsIGZyb21fdHJlZVswXSkKCgpkZWYgam9pbih4LCB5KToKICAgIGlmIHhbM10gIT0gTm9uZToKICAgICAgICByZXR1cm4gbW92ZV9ub2RlKHgsIHkpCiAgICBlbHNlOgogICAgICAgIHJldHVybiBtb3ZlX25vZGUoeSwgeCkKCgpkZWYgdmFsX25vbmUodmFsdWUsIHRhcmdldCk6CiAgICBpZiB0YXJnZXQ6CiAgICAgICAgcmV0dXJuIE5vbmUKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIHZhbHVlCgoKZGVmIG1lcmdlKHgsIHksIHRhcmdldCk6CiAgICByZXMgPSB7fQoKICAgIGZvciB2MSwgczEgaW4geDoKICAgICAgICBmb3IgdjIsIHMyIGluIHk6CiAgICAgICAgICAgIHJlc1t2MSArIHYyXSA9IChzMSwgczIsICcrJywgdmFsX25vbmUodjEgKyB2MiwgdGFyZ2V0KSkKCiAgICAgICAgICAgIGlmIHYxICE9IDAgYW5kIHYyICE9IDA6CiAgICAgICAgICAgICAgICByZXNbdjEgKiB2Ml0gPSAoczEsIHMyLCAnKicsIHZhbF9ub25lKHYxICogdjIsIHRhcmdldCkpCgogICAgICAgICAgICBmb3IgdmEsIHNhLCB2Yiwgc2IgaW4gKCh2MSwgczEsIHYyLCBzMiksICh2MiwgczIsIHYxLCBzMSkpOgogICAgICAgICAgICAgICAgcmVzW3ZhIC0gdmJdID0gKHNhLCBzYiwgJy0nLCB2YWxfbm9uZSh2YSAtIHZiLCB0YXJnZXQpKQoKICAgICAgICAgICAgICAgIGlmIHZhICE9IDAgYW5kIHZiICE9IDA6CiAgICAgICAgICAgICAgICAgICAgcmVzW3ZhIC8gdmJdID0gKHNhLCBzYiwgJy8nLCB2YWxfbm9uZSh2YSAvIHZiLCB0YXJnZXQpKQoKICAgIHJldHVybiByZXMKCgpkZWYgbXJhbmdlKG1hc2spOgogICAgeCA9IDAKCiAgICB3aGlsZSB4ICE9IG1hc2s6CiAgICAgICAgeCA9ICh4IC0gbWFzaykgJiBtYXNrCiAgICAgICAgeWllbGQgeAoKCmRlZiBpc19zaW5nbGVfbm90X3Jvb3QoeCk6CiAgICByZXR1cm4gKHggJiAxKSA9PSAwIGFuZCAoeCAmICh4IC0gMSkpID09IDAKCgpkZWYgaXNfc2luZ2xlKHgpOgogICAgcmV0dXJuICh4ICYgKHggLSAxKSkgPT0gMAoKCmRlZiBmaWxsKHBvcyk6CiAgICBjbnQgPSBiaW4ocG9zKS5jb3VudCgnMScpCiAgICBpZiBzZXRzW3Bvc10gb3IgY250ID4gNDoKICAgICAgICByZXR1cm4KCiAgICByZXN1bHRzID0ge30KCiAgICBmb3IgeCBpbiBtcmFuZ2UocG9zICYgKHBvcyAtIDEpKToKICAgICAgICB5ID0gcG9zIF4geAoKICAgICAgICBpZiBjbnQgPCA0IG9yIChwb3MgJiAxKSBvciBub3QgKGlzX3NpbmdsZSh4KSBvciBpc19zaW5nbGUoeSkpOgogICAgICAgICAgICByZXN1bHRzLnVwZGF0ZShtZXJnZShzZXRzW3hdLCBzZXRzW3ldLCAocG9zICYgMSkgIT0gMCkpCgogICAgICAgIGlmIGlzX3NpbmdsZV9ub3Rfcm9vdCh4KToKICAgICAgICAgICAgcmVzdWx0cy51cGRhdGUoc2V0c1t5XSkgIyB4IG5vdCB1c2VkCgogICAgICAgIGlmIGlzX3NpbmdsZV9ub3Rfcm9vdCh5KToKICAgICAgICAgICAgcmVzdWx0cy51cGRhdGUoc2V0c1t4XSkgIyB5IG5vdCB1c2VkCgogICAgc2V0c1twb3NdID0gc29ydGVkKHJlc3VsdHMuaXRlbXMoKSkKCgpkZWYgZ2V0X2Jlc3QoeCwgeSk6CiAgICBnbG9iYWwgYmVzdF9kaWZmLCBiZXN0X2l0ZW0KICAgIGpvaW5lZCA9IGpvaW4oeFsxXSwgeVsxXSkKCiAgICBpZiBqb2luZWRbM10gPiAwIGFuZCBhYnMoam9pbmVkWzNdIC0gc2V0c1sxXVswXVswXSkgPCBiZXN0X2RpZmY6CiAgICAgICAgYmVzdF9kaWZmID0gYWJzKGpvaW5lZFszXSAtIHNldHNbMV1bMF1bMF0pCiAgICAgICAgYmVzdF9pdGVtID0gam9pbmVkCgoKZGVmIG1hdGNoKHgsIHkpOgogICAgcG9zX3ggPSAwCiAgICBwb3NfeSA9IDAKCiAgICB3aGlsZSBwb3NfeCA8IGxlbih4KSBhbmQgcG9zX3kgPCBsZW4oeSk6CiAgICAgICAgZ2V0X2Jlc3QoeFtwb3NfeF0sIHlbcG9zX3ldKQoKICAgICAgICBpZiB4W3Bvc194XVswXSA8IHlbcG9zX3ldWzBdOgogICAgICAgICAgICBwb3NfeCArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgaWYgeFtwb3NfeF1bMF0gPiB5W3Bvc195XVswXToKICAgICAgICAgICAgICAgIHBvc195ICs9IDEKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHBvc194ICs9IDE7IHBvc195ICs9IDEKCgpkZWYgc2NhbigpOgogICAgZm9yIGkgaW4geHJhbmdlKDEsIDcpOgogICAgICAgIGZvciBqIGluIHhyYW5nZSgxLCBpKToKICAgICAgICAgICAgcG9zX3dpdGhfcm9vdCA9IDEgfCAoMSA8PCBpKSB8ICgxIDw8IGopCiAgICAgICAgICAgIHBvc19ub19yb290ID0gKCgxIDw8IDcpIC0gMSkgXiBwb3Nfd2l0aF9yb290CiAgICAgICAgICAgIG1hdGNoKHNldHNbcG9zX3dpdGhfcm9vdF0sIHNldHNbcG9zX25vX3Jvb3RdKQoKICAgICAgICAgICAgZm9yIGsgaW4geHJhbmdlKDEsIGopOgogICAgICAgICAgICAgICAgbWF0Y2goc2V0c1twb3Nfd2l0aF9yb290IHwgKDEgPDwgayldLAogICAgICAgICAgICAgICAgICAgICAgc2V0c1twb3Nfbm9fcm9vdCAmIH4oMSA8PCBrKV0pCgoKZGVmIHNlYXJjaChudW1iZXJzLCB0YXJnZXQpOgogICAgc2V0c1sxXSA9IFsodGFyZ2V0LCAoTm9uZSwgTm9uZSwgIlQiLCBOb25lKSldCgogICAgZm9yIGkgaW4gcmFuZ2UoNik6CiAgICAgICAgc2V0c1syICoqIChpICsgMSldID0gXAogICAgICAgICAgICBbKGZsb2F0KG51bWJlcnNbaV0pLAogICAgICAgICAgICAgIChOb25lLCBOb25lLCBzdHIobnVtYmVyc1tpXSksIGZsb2F0KG51bWJlcnNbaV0pKSldCgogICAgZm9yIGkgaW4gcmFuZ2UoMywgMioqNyk6CiAgICAgICAgZmlsbChpKQoKICAgIHNjYW4oKQoKICAgIHJldHVybiB0b19zdHIoYmVzdF9pdGVtLCAnPScpICsgIiAtPiAiICsgc3RyKGJlc3RfaXRlbVszXSkKCgpwcmludCBzZWFyY2goWzQsIDgsIDYsIDIsIDE1LCA1MF0sIDU5MCkK