habr_2016.py

from pprint import pprint
import itertools
from math import factorial


def fct(x):
    if x > 20:
        raise Exception()
    return factorial(x)


def pwr(x, y):
    if x > 1000 or y > 100:
        raise Exception()
    return x ** y


def allbtrees(s):
    if len(s) == 1:
        yield s
    else:
        for i in range(1, len(s), 2):
            for l in allbtrees(s[:i]):
                for r in allbtrees(s[i+1:]):
                    lv = type(l) == str and l or l[0]
                    rv = type(r) == str and r or r[0]
                    if s[i] == '**':
                        fstring = "(pwr({}, {}))"
                    else:
                        fstring = "({} %s {})" % s[i]

                    yield fstring.format(lv, rv)
                    # yield 'fct' + fstring.format(lv, rv)
                    # yield '~' + fstring.format(lv, rv)
                    yield '-' + fstring.format(lv, rv)


def alluops(nums, uops):
    for perm in itertools.product(uops, repeat=len(nums)):
        yield([k.format(v) for k, v in zip(perm, nums)])


def allbops(nums, bops):
    for perm in itertools.product(bops, repeat=len(nums)-1):
        yield([j for i in zip(nums, perm) for j in i] + [nums[len(nums)-1]])


def genlist(out, items, uops, bops):
    for u in alluops(items, uops):
        print("Apply bops for " + str(u))
        for b in allbops(u, bops):
            print("Gen trees for " + str(b))
            for t in allbtrees(b):
                try:
                    # print(t)
                    res = eval(t)
                    ires = int(res)
                    # print(res)
                    if 0 <= res <= 100 and ires == res:
                        if out[res] is None or len(out[res]) > len(t):
                            out[res] = t

                            # print(res, t)
                except:
                    pass

out = [None] * 101

uops = ["{}", "(-{})", "fct({})"]
bops = ["+", "*", "/", "**"]
# uops = ["{}", "(-{})", "(~{})", "fct({})"]
# bops = ["+", "*", "/", "**", "//", "%", "&", "|", "^"]
combs = [[2, 0, 1, 6], [20, 1, 6], [2, 1, 6], [20, 16], [2, 16], [201, 6]]

for comb in combs:
    genlist(out, comb, uops, bops)

print("Outkeys: " + ", ".join(str(k) for k, v in enumerate(out) if v is not None))
print("\n".join("%d: %s" % (k, v) for k, v in enumerate(out) if v is not None))