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

Ratio speed:size
70:30
 50%  [ 8 ]
75:25
 6%  [ 1 ]
80:20
 12%  [ 2 ]
85:15
 0%  [ 0 ]
90:10
 31%  [ 5 ]
Total Votes : 16

mr womp womp wrote:
This is equivalent to storing some of the string to another string and then claiming that only what is left of the initial string is the compressed version of the original string, which is not exactly the case.


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.
mr womp womp wrote:
earthnite wrote:
There should not be special rules that only apply to certain algorithms.

Well, in the case of dictionary encoding, part of the information required to decompress the compressed string is stored elsewhere since it can't be decoded without the dictionary. This is equivalent to storing some of the string to another string and then claiming that only what is left of the initial string is the compressed version of the original string, which is not exactly the case. This rule surely applies to any algorithm that requires additional information to decompress the string, not just dictionary encoding and it is only fair to tally up all the information.


I see your concern with other programs needed a possibly large program for decoding, however all algorithms will need some space to decode. Maybe if everyone has to make a decoding program that has to work independently then it would be fair for everyone, regardless of compression technique used.

So the programs might be tested like this:
"SECRET MESSAGE"->Str1
pgrmENCODE
save output variable somewhere
completely reset calculator
put output variable on calculator
pgrmDECODE
check to make sure it worked

and of course all the timing thingys when running the program

Size is the size of both programs
Time is the time of both programs
Compression ratio is [size of the input string]/[size of output variable]

The time is also probably dependent on the size of the string so maybe time should be [time]/[length of string]

But I dont makes the rules so... part of the competition is playing by the rules, even if you dont agree with them.

Keep in mind that the dictionary is needed to compress the string, so the compression program will include
the dictionary.
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.
earthnite wrote:

So the programs might be tested like this:
"SECRET MESSAGE"->Str1
pgrmENCODE
save output variable somewhere
completely reset calculator
put output variable on calculator
pgrmDECODE
check to make sure it worked.

That is a fair way to test it
Today it's time for da new task! I will post it in some hours Smile

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

Code:
1

Now the output is Str1, no compression, but he will get all the points for both speed and size, which is of course unfair Smile
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! Smile




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 Smile

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

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! Very Happy

If you have still questions, please post or pm me Wink

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.
PT_, in regards to task 4, I'm not sure I fully understand what you are expecting, please finalize how the programs are scored and how you will be testing the programs, what defines the output variable? Does it have to be in Ans at the end or can we just tell you that the output variable is, for example, [A]? Are we suppose to make a decoding program? Will the output variable be in Ans as well at the start of the decode program? If the size of the dictionary is to be included in the size of the output, what defines a dictionary?

What defines a program that is not allowed? Most programs will have a best and worse case scenario. If the worst case scenario is unable to compress the string then is it not allowed?

In regards to all of the tasks, I assume you will test the programs with a variety of inputs, I suggest that you test the same inputs for all of the programs, and select inputs that are not biased towards certain programs.

On another note, I have updated the form for task 5, if anyone is interested....you can submit your scores here... and see some results here.Please, it would be a shame if it went to waste.

Good luck everyone.
earthnite wrote:
PT_, in regards to task 4, I'm not sure I fully understand what you are expecting, please finalize how the programs are scored and how you will be testing the programs, what defines the output variable? Does it have to be in Ans at the end or can we just tell you that the output variable is, for example, [A]? Are we suppose to make a decoding program? Will the output variable be in Ans as well at the start of the decode program? If the size of the dictionary is to be included in the size of the output, what defines a dictionary?

What defines a program that is not allowed? Most programs will have a best and worse case scenario. If the worst case scenario is unable to compress the string then is it not allowed?

In regards to all of the tasks, I assume you will test the programs with a variety of inputs, I suggest that you test the same inputs for all of the programs, and select inputs that are not biased towards certain programs.

On another note, I have updated the form for task 5, if anyone is interested....you can submit your scores here... and see some results here.Please, it would be a shame if it went to waste.

Good luck everyone.

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:
If inString(Str1,"THE"
Then
  [replace THE with cos(
End

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 Wink
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 Smile
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?
Vital7788 wrote:
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! Smile
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. Smile
And still 6 hours to go! I've received some entries, but these are still much less as the participants Wink
Even if you don't have all the 5 programs, you can submit your entries! Smile
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^Cool until you find two primes, and then simply multiplying them together.
Runer112 wrote:
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^Cool 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 Wink
PT_ wrote:
Runer112 wrote:
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^Cool 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 Wink

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.
  
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 6 of 7
» 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

 

Advertisement