No, it's not. A program with dictionary compression/decompression contains a *fixed* dictionary; all information needed to decompress the string is already in the decompression program before anything is compressed.

thanks.

I don't know exactly what this discussion is about. I only want to say that if you need a dictionary, it will be added to the output size.
That is a fair way to test it

Today it's time for da new task! I will post it in some hours

An additional note on task #4: entries that don't compress will get 0 points. Otherwise someone could have a code like this:

Code:

Now the output is Str1, no compression, but he will get all the points for both speed and size, which is of course unfair

Last summer we had great news: TI releases a new color calculator, the TI-84+CE-T! Everyone happy, but not the ASM experts, because they found out that it was signed with a 2048-bit signing key, which is impossible to crack with the current possibilities. That is why they never can create Apps for the CE, until TI releases the SDK. Maybe we could help to crack that enormous number with BASIC?

The way to crack that key, is to find the factors of that key, such that P*Q=[signing key]. In the reverse, if you know the key, you can theoretically find P and Q, but that takes ages. That is what this task is about. You have to factor a number as fast as possible. I made this, because factorization is a pain and takes much time, especially with large numbers.

Task 5
Given the input in both N and Ans, output the two factors in L1 as a list. No limitations, and you may assume that number is withing the bounds of TI-BASIC.

Example: 5680842901 would be 60869*93329.

Good luck all and speed is still very important!




Submission
Now that the last task is being posted, you can submit your entries. Submit your entries by emailing them, in a ZIP file, to basiccompetition@gmail.com . Any entry before March 22th 11:59:59 pm GMT will be accepted, entries after that will be removed. Be sure to provide your Cemetech username in the subject or body of the email so we know who you are! Everyone can submit as many entries as they want, the last one will always be tested. If you have more programs for a task, please say which program is the main.

Testing
This is how I will test all the entries. I will first reset my whole calculator, including the Archive. Next, I transfer my timing program to the calculator, and after that, all the inputs. Finally, after that, I will transfer your program, so the VAT entry is for everyone equal.
I will test all the entries 3 times, and the speed is the average of that 3. You may assume no variable exists, without the input variable(s). I will measure the time with always the same program, upto 3 digits, so 4.193 can be the time for someone.
If you think it is not fair that I test my own programs, please pm me, and we will look for a solution

I will try to test all the programs as fast as possible, but it's dependant of the entries how many time that takes

I hope you all enjoy this competition, and it's not only for competing, but also for writing algorithms for yourself.

Summary of the 5 tasks:

1. Sort a list
2. Express a string
3. Make 24 with 4 numbers
4. Compress a string
5. Factorize a large number

I hope that there are many, many entries coming!

If you have still questions, please post or pm me

Good luck in the last week!

EDIT: somehow I forgot to say that: the number is always a product of 2 primes, a so-called semiprime

For the last challenge, PT_ specified the upper bound on the number to be 10^8 (less than in the given example).

I think I have about 5 seconds in the worst case, extrapolating from my monochrome time.

thanks.

I'm sorry I didn't explain it fully. You have to write only 1 program, for compressing the string which is in Ans and Str1. Output can be anything, so it don't need to be in Ans. Yesterday I had a small discussion with jonbush and you over SAX about the dictionary. When you use a static dictionary, such as one with the most important words in English, and that one is independant of the input, it will be only counted to the program size, not the compressed size. However, if you figured out that the word "TEST" appears in the input, and add "TEST" to a dictionary, that will be counted in the compressed size. A given example small code:

Code:

This is nice, but your decoding program don't know that cos( stands for THE. So you either need to add it to the output, or make a static dictionary. The only 'dictionary' you may use, is to replace ONE number with ONE token.

I hope this explains more, because I'm not a star in explaining
A program is not allowed, if it don't try to compress the string. Of course, there can be cases that you try to compress it, but it is a worse scenario, and that it fails. That is accepted. But if I only create a program that stores Str1 in Str2 and say that Str2 is my output, that is not allowed, because you don't try to compress it.


Here is an example for scoring for task #4: http://pastebin.com/KME3zWNK

For task #5, you may assume that the number is in the range 10^5 - 10^8, and a product of 2 primes.

Good luck all

I still have a few questions.
Will there be omitted parentheses at the end of the string for task 2?
Is there a minimum required decimal accuaracy? (also for task 2)
What is the maximum length of the string for task 4?

Yes, not all parentheses needs to be closed.
Only the accuracy of TI BASIC. If I need the square of something, don't round it up or down
Between 80 and 120 characters
Hope this helps!

Exactly one-and-a-half day to go, people!
If you haven't submitted your entries yet, don't hesitate to do so! Even if you don't have all the 5 (or more) programs, you can earn points.

And still 6 hours to go! I've received some entries, but these are still much less as the participants
Even if you don't have all the 5 programs, you can submit your entries!

My entries have been submitted.

I broke the evaluation solution into three parts, so I couldn't squeeze the size down much: 660 bytes.

I'll add further comments on my solutions once the deadline has passed.

Has it been solidifed yet how the performance of task 5 will be tested? Namely, how the inputs will be generated?

I'm still in favor of randomly generating numbers between sqrt(10^5) and sqrt(10^ until you find two primes, and then simply multiplying them together.

The best way to test this (what I think) is generating a list of semiprimes between 10^5 and 10^8 and then randomly picking one. There was much discussion over SAX about how to generate it

Yes, there was much discussion. And I believe the method I suggested is the only one (or one of two) suggested that actually generates a product of two medium-large primes most of the time. All the others have a large bias to generate a product of a small prime and a large prime, which is rather trivial to factor quickly by trial division. It also doesn't seem to match the task, a microcosm of RSA factoring, which should involve numbers that are a product of two primes of similar magnitude.

I recognize that my suggested method wouldn't even generate inputs with a prime factor less than sqrt(10^5), but for performance testing, I think that's ideal. For correctness testing, you can still require that solutions work for inputs with prime factors all the way down 2, but not count this for the performance.

Don't generate the list, download it: https://primes.utm.edu/lists/small/millions/

I just realized I misread the instructions; my program for Task 2 outputs in Ans instead of A. Will it be thrown out, or can the program with "->A" concatenated to the end be scored?

This should not come across as too much of a moan, because it's obviously up to us how often we visit this forum, but I think it's a shame there was such a narrow timeframe for entering this competition. Some folk have a lot of work to do, and can't visit the site too often. Now I get to my holidays and find I've missed out on this completely, yet I already have a good prgm for Task 5. I'll be interested to see how much the winner improves on it! Good luck to all who have competed.