Code:
```not(Ans->L2 For([recursiven],1,dim(Ans    1+L2(L1([recursiven]->L2(L1([recursiven] End 1->[recursiven] cumSum(L2->L2 For(X,1,dim(Ans    For([recursiven],[recursiven],L2(X       X->L1([recursiven]    End End```

This is an implementation of counting sort. Since the range of the algorithm is only 256, it is reasonable to have 256 buckets. Further advantages to counting sort are that the range matches up perfectly with 1~256, so the kth bucket can just be list position k.

At the start, I initialize L2 to all zeroes. From there it's pretty straightforward. I save two bytes by using dim(Ans twice instead of 256, which is possible because dim( is fast when passed a reference to a list.

I believe this solution to be close to optimal.

Code:
```// steps: // 1. tokenize as complex list (literals are real, operators imaginary) // 2. shunting-yard algorithm; output queue is complex list // 3. evaluate output queue //    using another list as a stack //tokens: ()sqrt(+-*/^ 0123456789.       //  123    45678 90123456789 //precedence: ^   */   +- "1.59*(5^3-9.5)/(5/3)^sqrt(4-2->Str1 //"1.59->Str1 "("+Str1+")?"->Str1       //padding "()sqrt(+-*/^0123456789.->Str7     //token lookup. 0 is position 9 seq(inString(Str7,sub(Str1,I,1)),I,1,length(Str1->L1 //raw 0->dim(|LTOK    //tokens ClrList |LS    //stack 0->dim(|LQ    //queue For(I,1,dim(L1    L1(I->T    If T<9     //if char not digit    Then       //then add it to list of tokens       1->D   //reset       1->F       T[i]->|LTOK(1+dim(|LTOK    Else      //it's part of a literal...       If imag(|LTOK(dim(|LTOK     //if the last token isn't a number       Then     //x-9 is value of digit; start new number          T-9->|LTOK(1+dim(|LTOK       Else                        //we are adding to a number          DF->F          If T=19          //decimal point          Then             .1->D          Else             //not a decimal point             |LTOK(dim(|LTOK    //take the number and             Ans10D+(T-9)F->|LTOK(dim(|LTOK  //correct it          End       End    End End Disp |LTOK //"()sqrt(+-*/^0123456789. //314.159 //         31 * 10 + 4*1 //314.     set D to .1 //    1    314 * 1 + 1 * .1 //     5   314.1 * 1 + 5 * .01 //      9  314.15 * 1 + 9 * .001 //F = factor to multiply new digit by //imag are commands, real are literals //now there's a trailing 0 in |LTOK //surrounded by () //tokens: ()sqrt(+-*/^ 0123456789. //        123    45678 90123456789 //stack contains reals; queue imag For(X,1,dim(|LTOK)-1    |LTOK(X->T    If not(imag(T    //if number    Then       T->|LQ(1+dim(|LQ    Else       imag(T->U           //now we have the token number. Real.       If U=1 or U=3 //token is sqrt(       Then           If U=3:3->|LS(1+dim(|LS   //sqrt          1->|LS(1+dim(|LS   //paren       End       If U>=4       //operator       Then          //priority is 00112 for tokens 45678          |LS(dim(|LS))   //Ans is top of stack          While Ans>3 and Ans<=8 and int(U/2)<=int(Ans/2   //precedence             Ans[i]->|LQ(1+dim(|LQ        //add to queue             dim(|LS)-1->dim(|LS       //and pop             |LS(Ans          End          U->|LS(1+dim(|LS   //push operator to stack       End       If U=2    //close paren       Then          |LS(dim(|LS          Repeat Ans=1    //there is always one operator before paren             Ans[i]->|LQ(1+dim(|LQ    //add to queue             dim(|LS)-1->dim(|LS       //and pop             |LS(Ans          End          //now we're at the left paren          dim(|LS)-1->dim(|LS    //pop          |LS(Ans          If Ans=3          Then             3[i]->|LQ(1+dim(|LQ   //add sqrt( to queue             dim(|LS)-1->dim(|LS          End       End    End    //now the stack is all left parens and operators    //ignore the parens and pop the operators End For(P,dim(|LS),1,~1)    If 1<|LS(P    [i]|LS(P->|LQ(1+dim(|LQ End {0->|LS    //|LS is now the number stack, not the token stack //tokens: ()sqrt(+-*/^ 0123456789. //        123    45678 90123456789 For(X,1,dim(|LQ    |LQ(X->T    imag(T->U    Pause |LS    If U    Then      //operator; pop and evaluate       dim(|LS->S       If U=3       Then          sqrt(|LS(Ans->|LS(Ans          Else          |LS(S->M          |LS(S-1->N          S-1->dim(|LS          If U=4          N+M          If U=5          N-M          If U=6          NM          If U=7          N/M          If U=8          N^M          Ans->|LS(S-1       End       Else  //number. push to stack       real(T->|LS(1+dim(|LS    End End |LS(2```

Because I couldn't figure out how to implement the algorithm all at once, I broke it up into three steps, as listed above. This cost me a significant amount of efficiency: it's nearly 5s compared to the winning <2.6s by PT_ and Runer112, and much larger.

Code:
```"int(tan(sinh(sinh(cosh^-1(sin^-1( For(X,1,4    Ans+"not("+sub("123456789",L1(X),1->Str1 End```

The trick for this one was to cheat. There are expressions that evaluate to 24 no matter what numbers are plugged in, and through a computer search I found one of the shortest.

When the string in the first line receives the argument 1, its value equals 24. We ensure that it always receives a 1 because the rightmost number provided is nonzero. There are 4 not(s, so this gets logically inverted an even number of times and

It would probably be optimal to either (a) unroll the whole thing to

Code:
```"123456789 "int(tan(sinh(sinh(cosh^-1(sin^-1("not("+sub(Ans,L1(1),1)+"not("+sub(Ans,L1(2),1+"not("+sub(Ans,L1(3),1+)"not("+sub(Ans,L1(4),1->Str1 ```

or (b) add a parentheses before the not( to ensure that the smaller strings are added first, which would probably increase speed, or both.

Code:
`sub(Ans,1,length(Ans)-1`

Since the scoring algorithm valued a combination of speed and program size almost as much as compression ratio (and the differences between compression ratios would be small anyway) I wrote a program that didn't compress very well but was very fast and short. This meant simply removing the period that we knew would be at the end of the string. Unfortunately, this was disqualified as not being "real" compression.

I note that this algorithm compresses better than two entries: noelnadal's and Vital7788's, both of whose entries' compressed outputs were actually larger than the input string.

Code:
```gcd(X,30 If Ans=1 Then    7+2{0,2,3,5,6,7,8,11    While min(remainder(X,Ans       Ans+30    End    min(Ans+|E9remainder(X,Ans End {Ans,X/Ans->L1```

This code first tests whether the number is divisible by 2, 3, or 5, and if not counts up by 30, testing divisibility by all numbers not divisible by 2, 3, or 5, starting from 7.

I made two mistakes here: first, trying to balance speed and size rather than getting the guaranteed 70 points for the fastest speed, and second, optimizing for the wrong distribution of primes.

As for the first mistake, Runer112 and earthnite/jonbush did the correct thing, and optimized for speed while almost ignoring the size of their programs. There was a significant difference between their ~2s and my ~7s total time. I didn't get many points for size either, since PT_ and noelthebest had even smaller factoring algorithms than mine. Since speed was given 70% of the weighting, Runer112 won round 5 by a significant margin even though his program was 6000 bytes in size.

As for the second, it was unclear which distribution of semiprimes PT_ was using to generate the test cases. I assumed that it would be the last method PT_ mentioned (generating random semiprimes between 10^5 and 10^8 and multiplying them), in which case they would probably have small factors.

Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
» All times are GMT - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum