Task 1
Code:
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:
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:
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:
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:
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:
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.
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
EndThis 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(2Because 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
EndThe 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)-1Since 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->L1This 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.