""" Compute values of a(n): number of ones required to build n using +,^

The strategy here is to first determine all n such that a(n) = 2, then 3,
then 4, and so on. In each round, we take both operations of all pairs of
numbers whose previously known complexities add to the desired target. Since
we proceed in order of values, we know that discovered expressions are minimal
as desired.

Note that it is safe to ignore large arguments n without jeopardizing the values
for small n because both operators produce values larger than either argument
(except for trivial exponentiations 1^k and k^1, which produce nothing new).
"""
import math
import operator
reva = [[], [1]]
lopd = [[], [0]]
ropd = [[], [0]]
oper = [[], [1]]
known = {1: 1}

opadd = 2
opsub = 3
opmul = 4
opdiv = 5
oppow = 6
oprt  = 7
nops  = 8

expTwoignore = 30

def ignpow(b,p):
    if b == 1: return 1
    if expTwoignore == 0: return b**p
    if p > expTwoignore: return 0
    if b > 2 and p > expTwoignore/math.log(b,2): return 0
    return b**p

ops = {opadd: operator.add,
       #opsub: operator.sub,
       #opmul: operator.mul,
       #opdiv: operator.floordiv,
       oppow: ignpow,
       #oprt: introot
       }

trybothorders = {opadd: False,  opsub: False,
                 opmul: False,  opdiv: False,
                 oppow: True,   oprt:  True }
symbol = {1: '1', opadd: '+', opsub:'-', opmul:'*', opdiv:'/',
          oppow:'^', oprt:'√'}

ignore = 2**expTwoignore + 1
if expTwoignore == 0: ignore = 0

def printtree(k, prefix=''):
    report = f"{k}: "
    newprefix = prefix + ' '
    for c in range(0, len(reva)):
        try: ix = reva[c].index(k)
        except: continue
        report += f"{lopd[c][ix]}{symbol[oper[c][ix]]}{ropd[c][ix]}, "
        left = False
        if lopd[c][ix] > 5:
            report += printtree(lopd[c][ix], prefix=newprefix)
            left = True
        if ropd[c][ix] > 5:
            if left: report += f"\n{newprefix}"
            report += printtree(ropd[c][ix], prefix=newprefix)
        break
    if not prefix: report += "\n"
    return report

maxmoves = 32
for moves in range(2,maxmoves+1):
    fresh = []
    isfresh = {}
    newoper = []
    newlopd = []
    newropd = []
    print(f"Generating complexity {moves}...")
    for lmoves in range(1,moves//2+1):
        for mm in reva[lmoves]:
            for nn in reva[moves-lmoves]:
                big = nn; lil = mm;
                if (nn < mm):
                    big = mm; lil = nn
                for op in ops:
                    for ordr in range(0, 2 if trybothorders[op] else 1):
                        if ordr: (m,n) = (lil,big)
                        else: (m,n) = (big,lil)
                        candidate = ops[op](m,n)
                        if candidate <= 0: continue
                        if ignore > 0 and candidate > ignore: continue
                        if candidate in known: continue
                        fix = -1
                        if candidate in isfresh:
                            fix = isfresh[candidate]
                            if op >= newoper[fix]: continue
                        if fix < 0:
                            isfresh[candidate] = len(fresh)
                            fresh.append(candidate)
                            newoper.append(op)
                            newlopd.append(m)
                            newropd.append(n)
                        else:
                            newoper[fix] = op
                            newlopd[fix] = m
                            newropd[fix] = n
    fmin = fresh[0]
    fmax = fresh[0]
    for ix in range(0, len(fresh)):
        if fresh[ix] < fmin: fmin = fresh[ix]
        elif fresh[ix] > fmax: fmax = fresh[ix]

    print(f"Added {len(fresh)} values from {fmin} ln/n {math.log(fmin)/moves} to {fmax} ln/n {math.log(fmax)/moves}.")
    fmed = fresh[len(fresh)//2] # not actually median
    print(f"    Fresh middle {fmed} ln {math.log(fmed)} ln/n {math.log(fmed)/moves}")

    reva.append(fresh)
    lopd.append(newlopd)
    ropd.append(newropd)
    oper.append(newoper)
    for k in fresh:
        known[k] = moves

# print data
print([known[i] for i in range(1,79)])

# print annotated data
for n in range(2,101):
    print(printtree(n))

# print b-file
n = 1
limit = 10001
while n in known and n < limit:
    print(f"{n} {known[n]}")
    n += 1