Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
Task 1


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.

Task 2

// 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: ^   */   +-

"("+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

   If T<9     //if char not digit
   Then       //then add it to list of tokens
      1->D   //reset
   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
      Else                        //we are adding to a number
         If T=19          //decimal point
         Else             //not a decimal point
            |LTOK(dim(|LTOK    //take the number and
            Ans10D+(T-9)F->|LTOK(dim(|LTOK  //correct it
Disp |LTOK


//         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

   If not(imag(T    //if number
      imag(T->U           //now we have the token number. Real.
      If U=1 or U=3 //token is sqrt(
          If U=3:3->|LS(1+dim(|LS   //sqrt
         1->|LS(1+dim(|LS   //paren
      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
         U->|LS(1+dim(|LS   //push operator to stack
      If U=2    //close paren
         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
         End          //now we're at the left paren
         dim(|LS)-1->dim(|LS    //pop
         If Ans=3
            3[i]->|LQ(1+dim(|LQ   //add sqrt( to queue
   //now the stack is all left parens and operators
   //ignore the parens and pop the operators

   If 1<|LS(P

{0->|LS    //|LS is now the number stack, not the token stack

//tokens: ()sqrt(+-*/^ 0123456789.
//        123    45678 90123456789

   Pause |LS
   If U
   Then      //operator; pop and evaluate
      If U=3
         If U=4
         If U=5
         If U=6
         If U=7
         If U=8
      Else  //number. push to stack

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.

Task 3


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


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

Task 4


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.

Task 5

If Ans=1
   While min(remainder(X,Ans

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.

» Go to Registration page
Page 1 of 1
» 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