Python 3, score 28806
import functools
import itertools
#import sympy
import math
STRINGABLE = sorted(b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~ ', reverse=True)
MAX = max(STRINGABLE)
ONECHAR = [*STRINGABLE, *range(15, 0, -1)]
MULTIPLES_O = {a*b:(a,b) for a in ONECHAR for b in ONECHAR}
SUMS_O = {a+b:(a,b) for a in ONECHAR for b in ONECHAR}
MM = {*range(16), *STRINGABLE}
def stringify(n):
infix = ''
prefix = ''
postfix = ''
options = []
while True:
if n < 16:
postfix = hex(n)[2:] + postfix
break
if n in STRINGABLE:
prefix += chr(n)
break
if n in SUMS_O:
a,b = SUMS_O[n]
postfix = '+' + postfix
if a < 16:
postfix = hex(a)[2:] + postfix
else:
prefix += chr(a)
if b < 16:
postfix = hex(b)[2:] + postfix
else:
prefix += chr(b)
break
if n in MULTIPLES_O:
a,b = MULTIPLES_O[n]
postfix = '*' + postfix
if a < 16:
postfix = hex(a)[2:] + postfix
else:
prefix += chr(a)
if b < 16:
postfix = hex(b)[2:] + postfix
else:
prefix += chr(b)
break
for i in ONECHAR:
if n+i in SUMS_O or n+i in MULTIPLES_O or n+i in ONECHAR:
n += i
postfix = '-' + postfix
if i < 16:
postfix = hex(i)[2:] + postfix
else:
prefix += chr(i)
break
if n-i in SUMS_O or n-i in MULTIPLES_O or n-i in ONECHAR:
n -= i
postfix = '+' + postfix
if i < 16:
postfix = hex(i)[2:] + postfix
else:
prefix += chr(i)
break
else:
for i in ONECHAR:
c = set(range(n%i, MAX+1, i)) & MM
if c:
if 0 in c:
prefix += chr(i)
postfix = '*' + postfix
n //= i
break
j = max(c)
if j in STRINGABLE:
prefix += chr(j)
postfix = '+' + postfix
else:
postfix = hex(j)[2:] + '+' + postfix
if i in STRINGABLE:
prefix += chr(i)
postfix = '*' + postfix
else:
postfix = hex(i)[2:] + '*' + postfix
n = (n-j) // i
break
# make n smaller ...
options.append("'" + prefix + "'" + most(n,0) + postfix)
options.append("'" + prefix + "'" + postfix)
return min(options, key=len)
def evaluate(s):
import io
s = io.StringIO(s)
stack = []
while True:
c=s.read(1)
if c=='': break
if c in '0123456789abcdef':
stack.append(int(c, 16))
elif c in '*+-%':
stack.append(eval(f'{stack.pop()}{c}{stack.pop()}'))
elif c == ':':
stack.append(stack[-1])
elif c == '~':
stack.pop()
elif c == '$':
stack.append(stack.pop(-2))
elif c == '@':
stack.insert(-2, stack.pop())
elif c == '"':
while True:
c = s.read(1)
if c == '"': break
stack.append(ord(c))
elif c == "'":
while True:
c = s.read(1)
if c == "'": break
stack.append(ord(c))
elif c == ',':
raise NotImplementedError
return stack
def factor(n):
from collections import Counter
p = 2
l = []
while n > 1:
if p*p > n:
l.append(n)
break
if n%p:
p += 1 + p%2
else:
l.append(p)
n //= p
return Counter(l)
#factor = sympy.factorint
def two_squares(n):
C = factor(n)
for i in C:
if i%4 == 3 and C[i]%2: return False
return True
def product(l):
z = 1
for i in l:
z *= i
return z
def divisors(n):
F, C = zip(*factor(n).items())
for t in itertools.product(*(range(i+1) for i in C)):
yield product(i**j for i,j in zip(F, t))
#from sympy import divisors
@functools.lru_cache(None)
def power(n):
if n < 2: return ''
options = [':'+power(n-1)+'*']
for i in divisors(n):
if 1 < i*i <= n:
options.append(power(i)+power(n//i))
return min(options, key=len)
def nth_root(k, p):
x = int(k**(1./p))+1
x1 = x-1
while x1 < x:
x = x1
xp1 = x**(p-1)
x1 = ((p-1)*x+k//xp1)//p
return x
#nth_root = lambda k,p:sympy.integer_nthroot(k, p)[0]
def massage(x, p):
options = [most(x) + power(p)]
if p%2 and p > 2:
options.append(most(x*x) + power(p//2) + most(x) + '*')
return min(options, key=len)
def powerful(n):
possibilities = []
for p in range(2, n):
x = nth_root(n, p)
if x == 1:
d2 = (x+1)**p-n
if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
break
d1 = n-x**p
if d1 == 0:
if x < n: possibilities.append((d1,x,p,None))
continue
d2 = (x+1)**p-n
if d1 < n and x < n: possibilities.append((d1,x,p,'+'))
if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
options = [most(d,0) + massage(x, p) + s if d else massage(x, p) for d,x,p,s in sorted(possibilities)[:2]]
return min(options, key=len)
def power2(n):
possibilities = []
for b in range(2, 20):
bc = 1
for c in range(1, n):
bc *= b
a = n//bc
if a*bc == n:
possibilities.append((a,b,c,None,''))
continue
d = (a+b)*bc - n
possibilities.append((a+1,b,c,d,'-'))
if a == 0: break
d = n - a*bc
possibilities.append((a,b,c,d,'+'))
a,b,c,d,s = min(possibilities, key=lambda t:t[0]+t[1]+(t[3]or 0))
postfix = most(a) + '*' if a > 1 else ''
if d is None: return most(b) + power(c) + postfix
return most(d) + most(b) + power(c) + postfix + s
def split(n):
D = sorted(i for i in divisors(n) if 1 < i*i <= n)
if len(D) == 0: return
options = []
for d in D[-3:]:
options.append(most(d,0) + most(n//d,0) + '*')
options.append(most(d,0) + ':' + most(n//d - d) + '+*')
options.append(most(n//d,0) + ':' + most(n//d - d) + '$-*')
return min(options, key=len)
def optimize(s):
return s.replace("''", '')
winners = [0,0,0]
@functools.lru_cache(None)
def most(n, depth=1):
if n < 16:
return hex(n)[2:]
if n < 31:
return hex(n-15)[2:] + 'f+'
if depth:
return stringify(n)
options = [stringify(n), powerful(n), split(n)]#, power2(n)]
options = [(optimize(s),i) if s else (s,i) for i,s in enumerate(options)]#list(map(optimize, filter(None, options)))
s,i = min(options, key=lambda t:len(t[0]) if t[0] else 1000000000)
winners[i] += 1
return s
#most(7**2)
def fib(n):
a,b = 0,1
for _ in range(n):
a,b = b,a+b
return a
if __name__ == '__main__':
L = sorted(I for I in {*range(1, 1501), *[i for i in range(1501, 7920) if list(factor(i).values()) == [1]], *[3**a+b for a in range(30) for b in range(-15, 16)], *[7**a + 5 + m*fb for fb in [fib(b) for b in range(30)] for a in range(10, 18) for m in [1,-1]]} if I > 0)
O = [most(i,0) for i in L]
for i,j in zip(O, L):
if evaluate(i)[0] != j:
print(i, j, evaluate(i))
break
print(f'{j}: {i}')
else:
print('Success!')
s = ''.join(O)
print(len(s))
print('\n' in s)
print(winners)
Try it online!
There are three methods this uses.
The first is to try to express the number using a single string of characters, and several multiplications/additions (more or less, it can also use single digits (0-f) outside of the string).
The next is to try to find a power that is close to the number, and express the number as a^p + b.
The third is to express the number as a product of two numbers (of similar magnitude).
It also removes any occurrences of '' (this saves nearly 200 bytes!)
O(n)in the number or in its number of digits? \$\endgroup\$