Make a Number Expression

Question

Few years ago, an esoteric programming language named 아희(Aheui) was created. Well, actually you don't need to know about this language or Korean characters.

Aheui uses stacks and a queue, but this time we use one stack and ignore other stacks and queue. You can push a number between 2 and 9 into a stack. You can do arithmetic operations by popping two numbers and pushing result. And you can duplicate a top number.

So, when I need a big number in Aheui, making a number was not an easy work. Push, push, multiply, duplicate, push, multiply, push, add…. It takes too much time and sometimes waste of bytes. I need a shortest expressions.

Summary

Your task is to write a function or a program which takes a number n (0 <= n <= 1000000) and returns concatenation of tokens.

Tokens are basically a postfix notation. Tokens are consisted of

• Number between 2 and 9, which means "push number into stack"
• +, -, /, *, which means "pop two numbers from stack, do arithmetic operation, push the result into stack". All calculations are in integer.
• >, which means "duplicate a top number"

Tokens will be concatenated with empty string, so 5 5 + will be 55+.

After calculations, n must be on the top of the stack.

Sample input and output

INPUT = 0
OUTPUT = 22-
(or 33-, 44-, whatever)

INPUT = 1
OUTPUT = 22/
(or 32-, 33/, whatever)

INPUT = 5
OUTPUT = 5
(We don't need calculations, just push)

INPUT = 64
OUTPUT = 88*
(or 8>*)

INPUT = 1337
OUTPUT = 75*2+>*48*-
(This may not be a shortest solution)

Scoring

This is a list of test cases. Test cases are seperated by a new line character. You may write a test script which converts those bunch of numbers to string of tokens, or you can do it by your hand.

Let

• S = size of complete function or program
• O = length of converted strings
• I = size of test cases (In this case, I = 526)

Then your score will be S * (O / I). Sizes are in bytes.

S includes function declarations, #includes, imports, whatever. Test script is not counted.

Scoring example

Let S is 150.

Sample Test cases

0
1
5
64
1337

Sample Output

22-22/588*75*2+>*48*-

In this case, I = 9, and O = 21. So your score is 150 * (21 / 9) = 350.

Rules

• Standard "loopholes" are forbidden.
• Lowest score wins.
• If there is a tie, smaller code size wins.
• Winner will be selected after three weeks (2014-08-04).

---

I wrote a validator in Node.js. Put input.txt and output.txt in same directory, and run node validator.js.

And I found two-year-old similar question. But scoring is different (this question includes code size in score), and this question can't use 1. So I hope it's not a duplicate.

Answer 1

Javascript, Score = 1663.46768

function X($){S=Math.sqrt;function J(A){return A.join("")}function M(A,B){return A.length<B.length?A:B}function D(q){var w="",e,r,t,y;for(e=9;e>1;e--){r=~~(q/e);t=r*e-q;if(t==0)y=J([G(r),e,"*"]);else y=J([G(r),e,"*",G(-t),"+"]);if(w=="")w=y;w=M(w,y)}return w}function Q(a){var s=~~S(a),d=a-s*s,f=J([G(s),">*",G(d),"+"]),g;s=Math.ceil(S(a));d=s*s-a;g=J([G(s),">*",G(d),"-"]);return M(f,g)}function G(z){var x,c,v,b,n,m;if(z==0)return"22-";if(z==1)return"22/";if(z>1&&z<10)return""+z;if(z>9&&z<19){x=~~(z/2);c=z-x;return J([x,c,"+"])}for(v=9;v>1;v--){b=~~(z/v);if(b>1&&b<10&&b*v==z)return J([v,b,"*"])}n=S(z);if(~~n==n)return J([G(n),">*"]);return M(D(z),Q(z))}return G($)}

This is my attempt for my question, and this is output. Code size is 671, and output size is 1304. Score is 1663.46768 (rounded up to 5 decimal places).