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

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

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

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.