# Outputting a base-proof expression

## Background

In some possible futures, the world will convert their numerical systems from decimal (base 10 or b10) to some other base (binary b2, octal b8, hexadecimal b16, or even unary b1, in which case we're screwed!). Thus, in preparation for this possible world-changing event, you decide to base-proof all of your programs. This can be done by using only singular 0s and 1s in conjunction with operators to replace the existing number constants.

However, there's just one problem: You have a ton of programs to change, and manually converting each number to an expression would take weeks! Thus, you decide to write a program (or function) to decide for you what expression should replace each number.

## Input

The input will be a positive integer. Your code must be able to handle any integer up to 1000.

(If your code supports decimals and/or negative inputs, see Scoring below.)

## Output

Your code must output an expression that evaluates to the input in at least one language. This may be any language; it does not have to be the same one your program or function is written in. Also, this expression does not need to be a full program or function.

For clarity, the output may contain any of these operations:

• increment / decrement
• subtract / negate
• multiply / double (only if it doesn't directly involve the number 2!)
• divide / modulo
• exponents / logarithms
• square / sqrt (again, only if these don't directly involve the number 2!)
• bitwise operations (bOR, bAND, bNOT, bXOR, bit-shifts)
• setting / getting variables
• stack manipulation

You may not use eval() or any similar functions in the output. You may also not use in the output any functions that perform an action(s) other than the ones mentioned above.

Oh, and one more thing: since we want the output to be valid in as many bases as possible, the only number constants it may contain are 0 and 1. Numbers such as 10 (ten) are disallowed, unless the language interprets it as a 1 and a 0. Using strings to contain numbers is not allowed either, as is using characters such as CJam's A-K (which represent 10-20).

## Test-cases

(All outputs are in JavaScript, but may work in other languages.)

Input 1:

2

Possible output 1:

1+1

Input 2:

13

Possible output 2:

(a=1+1+1)*a+a+1

Input 3:

60

Possible output 3:

(b=(a=1+1+1+1)*a)*a-a

Input 4:

777

Possible output 4:

(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1

Input 5:

1000

Possible output 5:

Math.pow((a=1+1+1)*a+1,a)

## Scoring

The goal of this challenge is to shorten your code's output as much as possible. Your score will be calculated in this way:

• Base score: The average byte-count of all outputs for integers 1 to 1000.

• Decimal score: If your code supports at least 3 decimal places, this is the average byte-count of all outputs of the sequence of numbers starting at 0.001 and ending at 1000, increasing by 1.001 each time. 0.001, 1.002, 2.003...998.999, 1000.000 Then take 50% off of this score.

• Negative score: If your code supports negative numbers and zero, this is the average byte-count of the outputs of all integers from -1000 to 0. Then take 10% off of this score.

(The easiest way to calculate these would likely be a loop with your program/function inside.)

Your final score is the average of whichever of the above formulas apply.

If the output is non-deterministic (i.e. somewhat random; multiple runs with the same input produces multiple unique outputs), then the score for each input is determined by the largest output over ten runs on my CPU.

Also, as you don't know how precious computer data will be in the future, the byte-count of your generator code must be less than 512 bytes.

Lowest score in two weeks (on Sep 30) will be declared the winner. Congratulations to your winner, @ThomasKwa!

# Language name/Other language name, X points

# CJam/Pyth, 25.38 points

If you have any questions or suggestions, please let me know. Good luck!

• Can I use variables that hold 0 or 1 by default? – Dennis Sep 16 '15 at 16:05
• @Dennis I don't see any problem with that, so go ahead! – ETHproductions Sep 16 '15 at 16:07
• I'm assuming I can't do base conversion between base 2 and the default base. – Blue Sep 16 '15 at 17:05
• @muddyfish Nope, no base conversion allowed in the output. – ETHproductions Sep 16 '15 at 17:07
• I guess we also are not allowed to use something like Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)? I'm pretty sure parseInt uses only the allowed operations ;-) – Paŭlo Ebermann Sep 16 '15 at 20:19

# Python/Zilog Z80 machine code, 11.653 11.488

import math,numpy as np
def R(n):
if n==0:return []
if n<0:return -R(-n)
e=int(math.log(n,2))
if n >= 5/3 * 2**e:
return np.append(2**(e+1),-R(2**(e+1)-n))
return np.append(2**e,R(n-2**e))

def strR(n):
b = R(n)
s = ""
if n==0:return s
e=max(abs(b))
while e:
if e in b:s+="#"
elif -e in b:s+="+"
s+=")"
e//=2
return s[:-1]

Bonuses: Negative numbers.

Assumes that the hl register pair initially holds 0, and returns the result in hl.

Only these three instructions are used:

ASCII   Hex    Instruction
--------------------------
#       23     inc hl
+       2B     dec hl

We use a small modification of the minimum-weight balanced binary representation BBR2. Since BBR2 minimizes the weight (number of nonzero digits), but we want to minimize the weight plus the number of bit shifts, we change a constant in the algorithm from 3/2 to 5/3.

To compute the score and verify, use this code:

def verify(n):
v = 0
for c in strR(n):
if c=="#":v += 1
elif c=="+":v -= 1
else: v *= 2
return v==n

print(0.5*(sum([len(strR(n)) for n in range(1,1001)])/1000 + \
sum([len(strR(n)) for n in range(-1000,1)])/1001 * 0.9))

print(all([verify(n) for n in range(-1000,1001)]))

Example output:

strR(486)
'#)))))+)+))+)'

Or in assembly:

More example programs:

-256  +))))))))
-255  +))))))))#
-254  +)))))))#)
-253  +)))))))#)#
-252  +))))))#))
-251  +))))))#))#
-250  +))))))#)#)
-249  +)))))#)))+
-248  +)))))#)))
-247  +)))))#)))#
-246  +)))))#))#)
-245  +)))))#))#)#
-244  +)))))#)#))
-243  +)))))#)#))#
-242  +))))#)))+)
-241  +))))#))))+

-5  +))+
-4  +))
-3  +)+
-2  +)
-1  +
0
1  #
2  #)
3  #)#
4  #))
5  #))#

Possible optimizations: OP rules that the inc h and dec h instructions, which directly change the upper byte of hl, are illegal, but sla h and the undocumented sl1 h (left bit shifts by 1 on h that shift in a 0 and 1 respectively) are permitted. sla h and sl1 h are two bytes each, but they can sometimes shorten the output.

• Very nice, the lowest so far! I guess this is one instance where pure machine code comes in handy. ;) – ETHproductions Sep 17 '15 at 2:19
• +1 this is probably unbeatable. Also for the genius of using machine code (on a cpu with a largely 8 bit instruction set and some 16 bit registers.) – Level River St Sep 17 '15 at 7:56
• It's weird how + translates to dec. I keep reading the negative examples wrong. – ETHproductions Sep 19 '15 at 3:11

# CJam/CJam, 143.26342.71328.89923.90121.903 20.468

ri
[
['X\2b1>e`{~{"1)*)"*}{_({(')*1\"m<"}{"1)*"*}?}?}/]s
"X1)*"/"1)"*
"1)1)*"/"1)))"*
"X1)m<"/"1)))"*
_"1)"/("1):Y"+\'Y*+
]
{,}$0= No bonuses apply. Try it online: sample run | score calculator | verification ### Example runs 1 X 2 1) 3 1)) 4 1))) 5 1)))) 6 1))1)* 7 1))1)*) 8 X1))m< 9 1)))1)*) 10 1))))1)* 11 1))))1)*) 12 1))1)m< 13 1))1)*1)*) 14 1))1)*)1)* 15 1))1)*)1)*) 16 X1)))m< 17 X1))m<1)*) 18 1)))1)*)1)* 19 1)))1)*)1)*) 20 1))))1)m< 981 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*Y*) 982 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y* 983 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*) 984 1):Y)Y*)Y*)Y*Y*)Y*)Y)m< 985 1):Y)Y*)Y*)Y*Y*)Y*)Ym<Y*) 986 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y* 987 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*) 988 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Ym< 989 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*Y*) 990 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y* 991 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*) 992 1):Y)Y*)Y*)Y*)Y)))m< 993 1):Y)Y*)Y*)Y*)Y))m<Y*) 994 1):Y)Y*)Y*)Y*)Y)m<Y*)Y* 995 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*) 996 1):Y)Y*)Y*)Y*)Ym<Y*)Ym< 997 1):Y)Y*)Y*)Y*)Ym<Y*)Y*Y*) 998 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y* 999 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*) 1000 1):Y)Y*)Y*)Y*)Y*Y*)Y)m< • My word, that was fast! The links don't work in Firefox, though. – ETHproductions Sep 16 '15 at 16:14 • Since this isn't code golf, I replaced each % with a longer expression. The links should work now. – Dennis Sep 16 '15 at 16:15 • Input 34 gives 1. On which input does it work better – Kishan Kumar Sep 16 '15 at 16:27 • @KishanKumar The verification tests all 1000 possible inputs. Output 1 indicates that the comparison was successful. – Dennis Sep 16 '15 at 16:28 • Could you add some example outputs? – Paŭlo Ebermann Sep 16 '15 at 19:54 # ß/BrainFuck, 34.201 points ### ß source (194B): E='++[------>+<]>++'°\c[1]<0°{E&='.'µA=ß"-ß°°c[1]),'')µE&='+++'°/B=1°(A[0]°\A[B]='.'°{µE&='--.++'°]E&=ß~A'+',A[B])&'.'&ß~A'-',A[B])°}°)°'ß"&E,'+-')+ß"&E,'-+')>0µE=ß"'ß"'E,'-+',''),'+-','')°!€E) If someone is interested, I'll add an explanation. The BF output is pretty optimized already, but I guess I could use the remaining 318B of ß code to implement • a loop-nesting-optimization, • more 8bit overflow shortcuts, • operator collision removal. ### Samples: Running in windows:$ sharps encode.ss 42
++[------>+<]>+++++++++.--.--

$sharps encode.ss -42 ++[------>+<]>++.+++++++.--.--$ sharps encode.ss 1.427
++[------>+<]>++++++.---.++++++.--.+++++.-------

$sharps encode.ss -946.427 ++[------>+<]>++.++++++++++++.-----.++.--------.++++++.--.+++++.------- Running in linux:$ WINEDEBUG=-all wine sharps source.ss -4.72
++[------>+<]>++.+++++++.------.+++++++++.-----.--

Validate in the online BF interpreter.

### Scores:

1. Base average = 37.495.
2. Decimal average = 60.959 * 0.5 = ~30.48.
3. Negative avg. = 38.4765234765235 * 0.9 = ~34.629
4. Avg of the above, final score = (37.495 + 30.48 + 34.629)/3 = 34.201.
• I always like to see the new languages folks have created. :) Thanks for the score breakdown! I'd like to put more of a bonus on the decimal portion, so I've changed the deduction from 40% to 50%. – ETHproductions Sep 16 '15 at 23:56
• @ETHproductions Yeah, I'll try setting up an online interpreter for this. There are about 435 highly abstract operators, additional 9,9k can be defined ;-) . I've corrected the calculation (hopefully). – mınxomaτ Sep 17 '15 at 0:39

# Ruby/Ruby, 29.77885

31.873*0.9 (negative) 30.872 (positive).

Basic strategy is symmetrical base 3 representation ("balanced ternary"), ie when the digits are -1,0,1 instead of 0,1,2

#function
f=->n{m=n
a='0'
7.times{|i|
r=m%3;r-=r/2*3
m=(m-r)/3
#produce expression: replace 0 with (0*x+-1)
#only add 0*x if there are higher base 3 digits to follow.
#only add (..+-1) if the current base 3 digit is nonzero.
a.sub!('0',['','(','('][r]+(m.abs>0?'0*x':'')+['','+1)','-1)'][r])
}
#tidy up expression
a.sub!('(-1)*','-')          #remove internal (-1)*
a.sub!('(+1)*','')           #remove internal (+1)*
a[-1]==')' && a=a[1..-2]     #remove unnecessary global brackets
a.sub!('x','(x=1+1+1)')      #find the first x and define it as 1+1+1=3
#special cases for small numbers
n.abs<8 && a=n==0?'0':['','1'+'+1'*(n-1).abs,'-1'*n.abs][n<=>0]
a
}

#call like this
(1..1000).each{|p|
b=f.call(p)
puts b

Here's the output from 0 to 40 before cleanup

(+1)
((+1)*x-1)
(+1)*x
((+1)*x+1)
(((+1)*x-1)*x-1)
((+1)*x-1)*x
(((+1)*x-1)*x+1)
((+1)*x*x-1)
(+1)*x*x
((+1)*x*x+1)
(((+1)*x+1)*x-1)
((+1)*x+1)*x
(((+1)*x+1)*x+1)
((((+1)*x-1)*x-1)*x-1)
(((+1)*x-1)*x-1)*x
((((+1)*x-1)*x-1)*x+1)
(((+1)*x-1)*x*x-1)
((+1)*x-1)*x*x
(((+1)*x-1)*x*x+1)
((((+1)*x-1)*x+1)*x-1)
(((+1)*x-1)*x+1)*x
((((+1)*x-1)*x+1)*x+1)
(((+1)*x*x-1)*x-1)
((+1)*x*x-1)*x
(((+1)*x*x-1)*x+1)
((+1)*x*x*x-1)
(+1)*x*x*x
((+1)*x*x*x+1)
(((+1)*x*x+1)*x-1)
((+1)*x*x+1)*x
(((+1)*x*x+1)*x+1)
((((+1)*x+1)*x-1)*x-1)
(((+1)*x+1)*x-1)*x
((((+1)*x+1)*x-1)*x+1)
(((+1)*x+1)*x*x-1)
((+1)*x+1)*x*x
(((+1)*x+1)*x*x+1)
((((+1)*x+1)*x+1)*x-1)
(((+1)*x+1)*x+1)*x
((((+1)*x+1)*x+1)*x+1)

And after cleanup

0
1
1+1
1+1+1
1+1+1+1
1+1+1+1+1
1+1+1+1+1+1
1+1+1+1+1+1+1
(x=1+1+1)*x-1
(x=1+1+1)*x
(x=1+1+1)*x+1
((x=1+1+1)+1)*x-1
((x=1+1+1)+1)*x
((x=1+1+1)+1)*x+1
(((x=1+1+1)-1)*x-1)*x-1
(((x=1+1+1)-1)*x-1)*x
(((x=1+1+1)-1)*x-1)*x+1
((x=1+1+1)-1)*x*x-1
((x=1+1+1)-1)*x*x
((x=1+1+1)-1)*x*x+1
(((x=1+1+1)-1)*x+1)*x-1
(((x=1+1+1)-1)*x+1)*x
(((x=1+1+1)-1)*x+1)*x+1
((x=1+1+1)*x-1)*x-1
((x=1+1+1)*x-1)*x
((x=1+1+1)*x-1)*x+1
(x=1+1+1)*x*x-1
(x=1+1+1)*x*x
(x=1+1+1)*x*x+1
((x=1+1+1)*x+1)*x-1
((x=1+1+1)*x+1)*x
((x=1+1+1)*x+1)*x+1
(((x=1+1+1)+1)*x-1)*x-1
(((x=1+1+1)+1)*x-1)*x
(((x=1+1+1)+1)*x-1)*x+1
((x=1+1+1)+1)*x*x-1
((x=1+1+1)+1)*x*x
((x=1+1+1)+1)*x*x+1
(((x=1+1+1)+1)*x+1)*x-1
(((x=1+1+1)+1)*x+1)*x
(((x=1+1+1)+1)*x+1)*x+1
• I believe it's called "balanced ternary". – lirtosiast Sep 17 '15 at 5:33
• @ThomasKwa edited in, thanks – Level River St Sep 17 '15 at 5:37

## Ceylon/Ceylon, 49.86 40.95 points

The third version uses Ceylon 1.2 for the generator and 509 bytes of code:

import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}

It gets down to 35.22 points, but I won't put this in the title line because Celyon 1.2 only was published at october 29. I don't think I would be able to implement this algorithm in Ceylon 1.1 in this size.). More details down there, here I'll describe the second version. (The first version can be seen in the history – it supported only positive numbers, but did fit into 256 bytes.)

### Second version

Now the second version, which supports negative integers (and 0), and generally creates a bit shorter output by using in addition -. (This version actually uses the permitted length, the first one tried to stay under 256 bytes instead of 512.)

String proof(Integer n) {
if (n == 0) { return "0"; }
if (n < 0) { return "-" + p(-n, "-"); }
return p(n, "+");
}
String p(Integer n, String sign) {
if (n < 9) {
return sign.join([1].repeat(n));
}
value anti = (sign == "+") then "-" else "+";
value root = ((n^0.5) + 0.5).integer;
return "(" + p(root, "+") + ")^(1+1)" +
( (root^2 < n) then sign + p(n - root^2, sign) else
((n < root^2) then anti + p(root^2 - n, anti) else ""));
}

Code has length 487, so there is still some space for more optimizations later. (There are also lots of reserves in form of whitespace and long variable names.)

The scoring:

Total positive: 42652
Average positive:42.652
Total negative: 43653
Average negative: 43.60939060939061
With bonus:39.24845154845155
Overall score: 40.95022577422577

Some sample outputs:

27:  21: (1+1+1+1+1)^(1+1)+1+1
28:  23: (1+1+1+1+1)^(1+1)+1+1+1
29:  25: (1+1+1+1+1)^(1+1)+1+1+1+1
30:  27: (1+1+1+1+1)^(1+1)+1+1+1+1+1
31:  29: (1+1+1+1+1+1)^(1+1)-1-1-1-1-1
32:  27: (1+1+1+1+1+1)^(1+1)-1-1-1-1
33:  25: (1+1+1+1+1+1)^(1+1)-1-1-1
34:  23: (1+1+1+1+1+1)^(1+1)-1-1

-27:  22: -(1+1+1+1+1)^(1+1)-1-1
-28:  24: -(1+1+1+1+1)^(1+1)-1-1-1
-29:  26: -(1+1+1+1+1)^(1+1)-1-1-1-1
-30:  28: -(1+1+1+1+1)^(1+1)-1-1-1-1-1
-31:  30: -(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
-32:  28: -(1+1+1+1+1+1)^(1+1)+1+1+1+1
-33:  26: -(1+1+1+1+1+1)^(1+1)+1+1+1
-34:  24: -(1+1+1+1+1+1)^(1+1)+1+1

993:  65: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
994:  63: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1-1
995:  61: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1
996:  59: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1
997:  57: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1
998:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1
999:  53: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)
1000:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)+1

-993:  66: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1+1)^(1+1)-1-1-1-1-1
-994:  64: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1+1
-995:  62: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1
-996:  60: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1
-997:  58: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1
-998:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1
-999:  54: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)
-1000:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)-1

1:   1: 1
2:   3: 1+1
3:   5: 1+1+1
4:   7: 1+1+1+1
5:   9: 1+1+1+1+1
6:  11: 1+1+1+1+1+1
7:  13: 1+1+1+1+1+1+1
8:  15: 1+1+1+1+1+1+1+1
9:  13: (1+1+1)^(1+1)
10:  15: (1+1+1)^(1+1)+1

0:   1: 0
-1:   2: -1
-2:   4: -1-1
-3:   6: -1-1-1
-4:   8: -1-1-1-1
-5:  10: -1-1-1-1-1
-6:  12: -1-1-1-1-1-1
-7:  14: -1-1-1-1-1-1-1
-8:  16: -1-1-1-1-1-1-1-1
-9:  14: -(1+1+1)^(1+1)
-10:  16: -(1+1+1)^(1+1)-1

As you can see, the negative ones are always one byte (the leading -) longer than the corresponding positive ones.

The base idea is the same as the previous program: find a square near our target number, and represent its root and the remainder recursively. But now we allow our square being also some larger than the target number, which then makes the remainder negative. (The +0.5 can be changed to a different constant to tweak the algorithm, but it seems that I already did hit the optimum here – both 0.4 and 0.6 give worse results.)

To make negative values negative (and otherwise have the same structure as the positive ones, we pass the operator sign to our recursive function p – that is either "+" or "-". We can use that for the joiner in the trivial cases (i.e. n < 9) as well as for the remainder if it's positive, and use the opposite sign for the remainder if it is negative.

The proof function handles the initial sign (with a special case for 0), the p function does the actual work, with recursion.

### Third version, for Ceylon 1.2

import ceylon.language { S=String, I=Integer,e=expand }

// output a base-proof Ceylon expression for an integer
// (i.e. using only 0 and 1 as digits).
//
// Question: http://codegolf.stackexchange.com/q/58084/2338
//
// The goal is to produce an expression as short as possible, with
// the code staying under 512 bytes in length.
//
// This approach is to represent a positive integer as a square
// of a positive integer plus some remainder (where the remainder
// can be negative), and for negative integers replace the + on the
// outer level by -.

S q(I n) =>
n == 0 then "0"
else (n < 0 then "-" + p(-n, "-")
else p(n, "+"));

// cache for values of p
variable Map<[I, S],S> c = map { };

// Transforms a positive number into a base-proof term, using
// the given sign for the summation on the outer level.
S p(I n, S s) {
S v =
// look into the cache
c[[n, s]] else (
// hard-code small numbers
n < 8 then s.join([1].repeat(n)))
else
// do the complicated stuff
(let (a = "+-".replace(s,""))
e(e {
for (x in 2..8) // try these exponents
let (l = (n ^ (1.0 / x)).integer) // $sqrt[exp]{n}$ in LaTeX
{ for (r in l:2) // lowerRoot, lowerRoot + 1
if (r > 1)
let (w = r ^ x)
{ if (w-n < n) // avoid recursion to larger or same number
// format the string as  r^x + (n-w)
"(" + p(r, "+") + ")^(" + p(x, "+") + ")" +
(w < n then s + p(n - w, s)
else (n < w then a + p(w - n, a)
else ""))
} } })
// and now find the shortest formatted string
.reduce<S>((x, y) => x.size < y.size then x else y))
// this should never happen, but we can't tell the compiler
// that at least some of the iterables are non-empty due to the if clause.
else "";

// this builds a new cache in each step – quite wasteful,
// as this also happens when the value was found in the cache,
// but we don't have more characters remaining.
//// c = map { [n, s] -> v, *c };
///better way:
c = [n,s] in c then c else map{[n,s]->v, *c};
return v;
}

The golfed version (i.e. comments and whitespace removed) is posted at the top, at exactly 509 bytes of code.

This uses the same base principle as the second version, but instead of just squares, it also tries to use higher powers of numbers (trying exponents from 2 to 8), and uses the shortest result. It also caches the results, as otherwise this would be unacceptably slow for larger numbers with many recursive calls.

Scoring:

Total positive: 36622
Average positive: 36.622
Total negative: 37623
Average negative: 37.58541458541458
With bonus:33.826873126873124
Overall score: 35.22443656343656

The big indented construct in the middle are three nested iterable comprehensions, the inner two inside a let expression. These are then unnested using the expand function twice, and the reduce function finds the shortest of those strings.

I've filed a feature request to be able to do this in a single comprehension.

Inside the comprehension, we are building a string from the root r, the exponent x and the remainder (n-w or w-n).

The let expression and the map function are new in Ceylon 1.2. map could have been replaced by HashMap (which would have needed more characters for the import, although it would probably be even faster, as I wouldn't build the map new for each new entry). The let expressions like let (w = r ^ x) could have been replaced by using an if clause like if(exists w = true then r ^ x) (and then I wouldn't have needed the two expand calls either), but this would still be a bit longer, not fitting inside the 511 allowed bytes.

Here the sample outputs corresponding to those selected above, all of them except the really small numbers are shorter:

27:  15: (1+1+1)^(1+1+1)
28:  17: (1+1+1)^(1+1+1)+1
29:  19: (1+1+1)^(1+1+1)+1+1
30:  21: (1+1)^(1+1+1+1+1)-1-1
31:  19: (1+1)^(1+1+1+1+1)-1
32:  17: (1+1)^(1+1+1+1+1)
33:  19: (1+1)^(1+1+1+1+1)+1
34:  21: (1+1)^(1+1+1+1+1)+1+1

-27:  16: -(1+1+1)^(1+1+1)
-28:  18: -(1+1+1)^(1+1+1)-1
-29:  20: -(1+1+1)^(1+1+1)-1-1
-30:  22: -(1+1)^(1+1+1+1+1)+1+1
-31:  20: -(1+1)^(1+1+1+1+1)+1
-32:  18: -(1+1)^(1+1+1+1+1)
-33:  20: -(1+1)^(1+1+1+1+1)-1
-34:  22: -(1+1)^(1+1+1+1+1)-1-1

993:  39: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1-1
994:  37: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1
995:  35: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1
996:  33: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1
997:  31: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1
998:  29: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1
999:  27: ((1+1+1)^(1+1)+1)^(1+1+1)-1
1000:  25: ((1+1+1)^(1+1)+1)^(1+1+1)

-993:  40: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1+1
-994:  38: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1
-995:  36: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1
-996:  34: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1
-997:  32: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1
-998:  30: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1
-999:  28: -((1+1+1)^(1+1)+1)^(1+1+1)+1
-1000:  26: -((1+1+1)^(1+1)+1)^(1+1+1)

1:   1: 1
2:   3: 1+1
3:   5: 1+1+1
4:   7: 1+1+1+1
5:   9: 1+1+1+1+1
6:  11: 1+1+1+1+1+1
7:  13: 1+1+1+1+1+1+1
8:  13: (1+1)^(1+1+1)
9:  13: (1+1+1)^(1+1)
10:  15: (1+1+1)^(1+1)+1

0:   1: 0
-1:   2: -1
-2:   4: -1-1
-3:   6: -1-1-1
-4:   8: -1-1-1-1
-5:  10: -1-1-1-1-1
-6:  12: -1-1-1-1-1-1
-7:  14: -1-1-1-1-1-1-1
-8:  14: -(1+1)^(1+1+1)
-9:  14: -(1+1+1)^(1+1)
-10:  16: -(1+1+1)^(1+1)-1

For example, now we have 1000 = (3^2 + 1)^3, instead of 1000 = (6^2-4)^2-5^2+1.

• I did wrongly remember the program restriction as 256 bytes ... in 512 quite a bit more can be done. Will try that later. – Paŭlo Ebermann Sep 16 '15 at 23:37
• Nah, it says less than 512. Sou you can use a max. of 511 bytes ;) – mınxomaτ Sep 17 '15 at 1:25
• How have I never heard of this language?!? :O But seriously, excellent explanation! I love to understand the techniques others use in their answers. +1 – ETHproductions Sep 17 '15 at 2:13
• @ETHproductions I also only read of it about two weeks ago here on the site, and started to like it. So to get to know it better, I try to answer questions here using Ceylon. – Paŭlo Ebermann Sep 17 '15 at 17:09

# Ruby/dc, 20.29618.414 16.968

Dynamic programming! Defines a list of functions that, given a dc instruction, return a new expression and the numeric value of that expression. Then, starting with 1 prefined, it builds a list of all reachable values up to and including the wanted value.

### edit:

Added a function for n-1 and made it run the algorithm through multiple passes. It seems to need 7 passes to stabilize. Had to shorten some variable names to stay within 512 bytes.

### edit 2:

Added functions for n(n-1), n(n+1) and n^3 while I was at it. Shortened the code some more, landing at exactly 512 bytes.

N = gets.to_i

fns = [
->(n,s){[n-1,   s+'1-']},
->(n,s){[n+1,   s+'1+']},
->(n,s){[n*2,   s+'d+']},
->(n,s){[n*3,   s+'dd++']},
->(n,s){[n*~-n, s+'d1-*']},
->(n,s){[n*n,   s+'d*']},
->(n,s){[n*-~n, s+'d1+*']},
->(n,s){[n*n*n, s+'dd**']},
]

lst = []*(N+1)
lst[0..2] = %w[0 1 1d+]

loop do
prev = lst.dup

(1..N).each do |n|
fns.each do |f|
m,s = f[n, lst[n]]
lst[m] = s if m <= N && (lst[m].nil? || lst[m].size > s.size)
end
end

break if lst == prev
end

puts lst[N]

### Generated numbers:

Output consists entirely of five different characters: 1 pushes the value 1 on the stack; d duplicates the top of the stack; +, -, and * pops the two top values and pushes their sum, difference, and product, respectively. Each generated expression adds only one value to the stack after execution.

1: 1
2: 1d+
3: 1dd++
4: 1d+d+
5: 1d+d+1+
6: 1d+dd++
7: 1d+dd++1+
8: 1d+dd**
9: 1dd++d*
10: 1d+d+1+d+
11: 1d+d+1+d+1+
12: 1dd++d1+*
13: 1dd++d1+*1+
14: 1d+dd++1+d+
15: 1d+d+d*1-
16: 1d+d+d*
17: 1d+d+d*1+
18: 1dd++d*d+
19: 1dd++d*d+1+
20: 1d+d+d1+*
21: 1d+d+d1+*1+
22: 1d+d+1+d+1+d+
23: 1d+dd**dd++1-
24: 1d+dd**dd++
25: 1d+d+1+d*

...

989: 1d+d+d*d+d1-*1-1-1-
990: 1d+d+d*d+d1-*1-1-
991: 1d+d+d*d+d1-*1-
992: 1d+d+d*d+d1-*
993: 1d+d+d*d+d1-*1+
994: 1d+d+d*d+d1-*1+1+
995: 1d+d+d*d+d1-*1+1+1+
996: 1d+d+1+dd**d+1-d+d+
997: 1d+d+1+d+dd**1-1-1-
998: 1d+d+1+d+dd**1-1-
999: 1d+d+1+d+dd**1-
1000: 1d+d+1+d+dd**
• Pretty good, beating everything but z80 machine code so far (even Dennis' CJam!). Do you think you might be able to add in a - operator while staying within the byte count? – ETHproductions Sep 19 '15 at 3:17
• @ETHproductions How's that? ;) It shouldn't be hard to add negative numbers now, either. – daniero Sep 19 '15 at 12:45

# Python 2.6, 78.069 - 66.265 points

Submitting my answer for what it's worth (not a lot in this case ... but clearly demonstrating that for this challenge it's not enough to simply think of composing the output as a sum of bit-shifted values; when taken into account that no digits outside of 0 or 1 may appear in the output). I might come back later with a different way of generating output.

The code itself is not too long (176 characters):

def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print"".join(f(int(input())))

It generates correct but verbose output:

17
1+(1<<1+1+1+1)

800
(1<<1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1+1)

Snippet that calculates the score:

def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print sum(len("".join(f(i)))for i in range(1000))