2015.py

import itertools
import math
from sympy import Rational, simplify


ints = "2015"

def splits(seq):
    yield [seq]

    for i in range(1, len(seq)):
        begin, end = seq[:i], seq[i:]
        for end_splits in splits(end):
            split = [begin] + end_splits
            if all(n == "0" or not n.startswith("0") for n in split):
                yield split

def decimalize(num):
    yield num
    yield "." + num

def decimalize_sets(sets):
    for s in sets:
        yield from itertools.product(*[decimalize(x) for x in s])

def repeatize(num):
    yield num

    if "." in num:
        whole, frac = num.split(".")
        for i in range(len(frac)):
            yield num + "~" * (i + 1)

def repeatize_sets(sets):
    for s in sets:
        yield from itertools.product(*[repeatize(x) for x in s])

def num_to_sympy(num):
    if not "~" in num:
        return Rational(num)

    nrep = num.count("~")
    num = num[:-nrep]

    frac, rep = num[:-nrep], num[-nrep:]
    divisor = 10**len(frac.split(".")[1])

    if rep != "0": rep = rep.lstrip("0")

    return Rational(frac + "0") + Rational(rep + "/" + nrep*"9") / divisor

def negify(data, rational_data):
    new_data, new_rational_data = [], []
    for orig, rational in zip(data, rational_data):
        for do_negs in itertools.product(range(2), repeat=len(orig)):
            new_data.append(tuple("-("*s + orig[i] + ")" * s for i, s in enumerate(do_negs)))
            new_rational_data.append(tuple(rational[i] * (1 - 2*s) for i, s in enumerate(do_negs)))

    return new_data, new_rational_data

# def factorialify(data, rational_data):
#     new_data, new_rational_data = [], []
#     for orig, rational in zip(data, rational_data):
#         for do_fact in itertools.product(range(2), repeat=len(orig)):
#             if any(do and (not rational[i].denominator == 1 or not 0 < rational[i].numerator <= 10) for i, do in enumerate(do_fact)):
#                 continue

#             new_data.append(tuple("!("*s + orig[i] + ")" * s for i, s in enumerate(do_fact)))
#             new_rational_data.append(tuple(rational[i] if not do else mpq(fac(rational[i].numerator)) for i, do in enumerate(do_fact)))

#     return new_data, new_rational_data

def sqrtify(data, rational_data):
    new_data, new_rational_data = [], []
    for orig, rational in zip(data, rational_data):
        for do_sqrt in ((1,) + (0,)*(len(orig)-1), (0,) + (0,)*(len(orig)-1)):
            new_data.append(tuple("sqrt("*s + orig[i] + ")" * s for i, s in enumerate(do_sqrt)))
            new_rational_data.append(tuple(rational[i] if not do else eval_binop("^", rational[i], Rational(1, 2)) for i, do in enumerate(do_sqrt)))

    return new_data, new_rational_data

def uniquefy(data, rational_data):
    data, rational_data = sqrtify(data, rational_data)
    # data, rational_data = negify(data, rational_data)
    # data, rational_data = factorialify(data, rational_data)

    indices = reversed(sorted(range(len(data)), key=lambda i: (len(data[i]), -len("".join(data[i])))))
    seen = set()
    new_data, new_rational_data = [], []
    for i in indices:
        orig, rational = data[i], rational_data[i]
        # s = tuple(q.evalf() for q in rational)
        if rational in seen: continue

        seen.add(rational)
        new_data.append(orig)
        new_rational_data.append(rational)

    print(len(seen), len(data))

    return new_data, new_rational_data


def _eval_binop(binop, a, b):
    if binop == "+": return a + b
    if binop == "-": return a - b
    if binop == "*": return a * b
    if binop == "/": return a / b
    if binop == "^": return a ** b

def eval_binop(*args):
    r = _eval_binop(*args)
    return _eval_binop(*args)

input_sets = list(repeatize_sets(decimalize_sets(splits("2015"))))
rational_input_sets = [tuple(num_to_sympy(n) for n in s) for s in input_sets]

data, rational_data = uniquefy(input_sets, rational_input_sets)
# for orig, rational in zip(data, rational_data):
#     print("{:>40} | {}".format(" ".join("{:>7}".format(n) for n in orig), " ".join("{:<8}".format(str(n)) for n in rational)))

l = 4
while l > 1:
    if len(data[0]) < l:
        l -= 1
        data, rational_data = uniquefy(data, rational_data)

    expr = data.pop(0)
    expr_rat = rational_data.pop(0)

    for binop in "+-*/^":
        for i in range(l-1):
            try:
                nexpr = expr[:i] + ("(" + binop.join(expr[i:i+2]) + ")",) + expr[i+2:]
                nexpr_rat = expr_rat[:i] + (eval_binop(binop, *expr_rat[i:i+2]),) + expr_rat[i+2:]
            except (ZeroDivisionError, ValueError):
                continue

            data.append(nexpr)
            rational_data.append(nexpr_rat)

orirational = sorted(((orig, int(rational[0])) for orig, rational in zip(data, rational_data) if rational[0].is_integer), key=lambda t: t[1])
n = 0
for orig, num in orirational:
    if not 0 <= num <= 100: continue
    n += 1
    print("{:>40} | {}".format(" ".join("{:>7}".format(n) for n in orig), "{:<8}".format(num)))

print(n)