Task 1


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.

Task 2


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.

Task 3


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.

Task 4


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.

Task 5


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.

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

 

Advertisement