3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Clarification needed. 1.The requested number must be on top of stack? What if the stack is not empty after popping the result? 2.Division is integer or floating point? \$\endgroup\$ – edc65 Jul 14 '14 at 15:24
  • \$\begingroup\$ @edc65 1. Yes. It must be on the top of the stack. 2. Integer, floor. 53/ = 1, not 2. \$\endgroup\$ – Snack Jul 15 '14 at 2:25
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ If you can transform your functions (or some of them) to functional form, meaning that you can transform them such that a function like function F(a){return <lots of code>} becomes possible, you can use the ECMAscript 6 syntax F=(a)=><lots of code>. Furthermore, you have if(z==0)return"22-";if(z==1)return"22/";. I think you can compress that to if(z<2)return["22-","22/"][z];. (If z can be negative, add a &&z>=0.) \$\endgroup\$ – tomsmeding Jul 14 '14 at 6:27
  • \$\begingroup\$ +1 Great job! Golfed a little more and rewrited for EcmaScript 6 your code size is 406. X=$=>(S=Math.sqrt,M=(A,B)=>A.length<B.length?A:B,D=(q,w="",e,r,t,y)=>{for(e=9;e>1;e--)r=~~(q/e),t=q-r*e,y=t?G(r)+e+"*"+G(t)+"+":G(r)+e+"*",w=M(w||y,y);return w}, Q=(a,s=~~S(a))=>M(G(s)+">*"+G(a-s*s)+"+",G(++s)+">*"+G(s*s-a)+"-"), G=(z,v,b)=>{if(z<18)return z<2?"22"+"-/"[z]:z<10?z:"8"+(z-8)+"+";for(v=9;v>1;v--)if((b=~~(z/v))>1&b<10&b*v==z)return""+v+b+"*";return ~~(v=S(z))-v?M(D(z),Q(z)):G(v)+">*"},G($)) \$\endgroup\$ – edc65 Jul 15 '14 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.