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

I've created a program that parses the input. Despite the size (349+137 bytes), it's pretty fast (I think about the 1.5-2 seconds). Now time for optimizing and speeding up!

Btw, if you didn't know; you may have multiple BASIC programs, and call them, as long as they are BASIC Wink
PT_: what input are you benchmarking on?
elfprince13 wrote:
PT_: what input are you benchmarking on?

For now, I've used my own example, as posted in my previous post. I would recommend you all to use that all, to get the actual time. Otherwise anyone could get 5 seconds for a really long string, while I get 1 second for a small string.
Can I join too? I'd like to see how much I'm going to fail against you guys Very Happy .
Vital7788 wrote:
Can I join too? I'd like to see how much I'm going to fail against you guys Very Happy .

Of course. We're now at task #2. For the tasks, please look at some post of me at the previous pages.
How are you all going? It doesn't seem people get #2 to work Sad
I'm giving a hint of how I did it (mine almost work):
I've implemented my own version of the Shunting-yard algorithm. That algorithm converts the string from infix to postfix, and it's very easy to go from postfix to a value. C'mon people, tomorrow a new (maybe less harder) task!
Make 24 is a very simple game, with only 4 numbers trying to make 24, but programming is a lot harder... In this task, it is your task you output the string, which makes 24 if you call expr(<string>), of course with only 4 given numbers. I know; there are tons of them on the Internet, but you still need to remember that speed is more important than size, and that seems to be sometimes the problem Wink

Task 3:
Output a string with 4 numbers and any mathematical token that makes 24 if you call expr(<string>). Input is both in Ans and L1 and contains the 4 numbers from 1-9 to create 24. Note: you may assume you CAN make 24 with the input, so it is not impossible. Output should be a string in Str1 which contains the string. If someone call expr(Str1), it should return 24. Limitations: no extra numbers. You can use any TI-BASIC command, as far as you may not add numbers to it (like +1, ^2). sqrt( is still allowed.
I'm looking forward to see your solutions, and if you don't have finished task #2 yet, please don't forget it Smile

Good luck everyone! Good Idea Good Idea
I remember working with Electromagnet8 on a 24 solver a while back; this should be a fun challenge.

On SAX, by the way, PT_ said that the 10^(, e^(, ^^2 and ^^3 tokens are disallowed, concatenating numbers is disallowed, and that we can assume radian mode.

EDIT: Based on the algorithm from the topic above, I think I can get a program working in about 40 seconds worst-case, and in about 250 bytes.

What inputs will be tested? The worst-case time of most algorithms should be much greater than the average case.
Maybe it's time for a sneak peek at task #4 to motivate you all to finish this competition (5 tasks)?

- It's not only speed and size, but more than that...
- The more the size, the less the size...
- Too large, too small...
- At the end, you're not at the end...

Good luck everyone for solving these tasks!
TI-BASIC.

Integers.

Lists.

Matrices.

Do you know that they take up a bunch of memory in the RAM? One single TI-OS variable is 18 bytes, a list is 12+9*[dimension], and matrices 11+9*[width]*[height]. And often is that not necessary. Many people have booleans in their programs, like not(A->A. You can store that in only 1 bit, instead of 18*8=144 bits....
And that is what this task is for. You need to compress data as much as possible, and then you're still not at the end. A very simple example of compressing, is storing booleans as bits, and not as 9-byte floating numbers, which saves much free space in RAM. Your task is to create a lossless compression algorithm (lossless = you can restore it to the original data).

Task #4:
Write an algorithm that compresses data without losing stuff. The input is a string in both Str1 and Ans, which contains a normal English text with these possible characters: ABCDEFGHIJKLMNOPQRSTUVWXYZ_.,. Not more, not less (no lowercase letters!). The length is about 100 characters. Output is very simple: it can be anything, what you prefer, but remember what I said about integers, lists and matrices, which takes up much space. You may use ANY BASIC-command, because there is no compress-command Wink. You only need the compression algorithm for scoring, but you should be able to decompress it as well! I say this, because otherwise people could say their algorithms are lossless, but in the meantime...

Extra: You can 10 points if can get the size < 5/10 of the original size Smile

Anyway, to give you enough time, I decided to make #5 easy. In 2 weeks, this competition will be closed, so be sure to start today! Smile

Score:
Not only speed and size is important, the compressed size too (without header!!!)
Ratio speed:compressed_size:size = 3:5:1

This would be an example as an input:

Code:
"CHRISTOPHER LIVES IN NEW YORK CITY, ONE OF HIS SEVERAL LOVES ALONG WITH CALCULATORS, TECHNOLOGY, AND TRAINS."->Str1
prgmCOMPRESS


Good luck everyone, and have fun! Very Happy
This one sounds like a very interesting competition, If i can think up a way to do it and find the time, I will definitely be participating. Also I love that the compressed_size is the most important category because i fell like adding layers of compression one over the other might improve the compression but also make it considerably longer to decompress. Good luck to all who will be participating!
My algorithm is in my mind, but I hardly transcribe it in TI-Basic...I'm still looking for an elegant solution !
I have an idea too, wich can compress (in optimal cases) to about 50-55% or whatever. Just time for programming that
mr womp womp wrote:
This one sounds like a very interesting competition, If i can think up a way to do it and find the time, I will definitely be participating. Also I love that the compressed_size is the most important category because i fell like adding layers of compression one over the other might improve the compression but also make it considerably longer to decompress. Good luck to all who will be participating!

Edit, I finally got my idea to come to life (it was a pain) but unfortunately, the compression is kind of lame, only 20%, but its quite fast and big haha I think I might be able to bump it up a little but I'm just wondering, do I need to have a program that can decompress it or to just prove that it can be done...
Also, I forgot that the space was a character which will require me modifying my barely working code D:
I have updated the form and the chart to include Task 4, I have defined compressed_size to be the ratio of the size of the original string to the size of the output variable ([size of Str1]/[size of output variable]) because the size of the output variable probably depends on the input, and I assume input will vary.

jonbush and I are currently in the lead, followed closely by PT_, and the rest have not done more than 1 task, or have not submitted your scores. Please remember that adding your programs can negatively affect your opponents scores, and improve your rank. Also remember that just completing the task will greatly improve your score, especially if no one else has (+100 points).

Check out the full chart here.
Submit your information here so we can keep your score up to date.

I'm eager to see what solutions you guys come up with, these tasks are pretty challenging.
It can happen some of you uses a kind of dictionary, and then replacing pairs of letters with a single token. Ok, very nice, but for counting the compressed size a bit unfair. The dictionary will be added to the output size. A simple example would be this:

Code:
dictionary = "<input string";
compressed size = "<a 1-byte token>";

Then the compressed size is NOT 1+9=10 bytes, but the length of the input as well.

Anyway, good luck! Smile
There are not enough tokens to replace two letters with 1 character, that would require 29^2 unique tokens. Even if you could, that would result in a compression ratio of 1:2.

jonbush and I have used similar techniques before, and for this challenge, it seems you can only get about 2:3 compression ratio using a similar technique. if other programs can get a 1:2 ratio then these type of programs are not the ones you should be worrying about.

There should not be special rules that only apply to certain algorithms.

Using a ratio is better is better because it should be more consistent over inputs of different length.
earthnite wrote:
There are not enough tokens to replace two letters with 1 character, that would require 29^2 unique tokens. Even if you could, that would result in a compression ratio of 1:2.

jonbush and I have used similar techniques before, and for this challenge, it seems you can only get about 2:3 compression ratio using a similar technique. if other programs can get a 1:2 ratio then these type of programs are not the ones you should be worrying about.

There should not be special rules that only apply to certain algorithms.

Using a ratio is better is better because it should be more consistent over inputs of different length.


I agree with earthnite's judgement. Real compression formats are judged based on the compression ratio in most cases. It is also important to note that compression algorithms like zip and 7z use special codes to replace larger data structures losslessly, similar to how it would be possible to replace several letters with fewer tokens.
Yes I had the same trouble :
tokens from 0 to 255 ... This is impossible because some doesn't exist, then can't be used/seen/accepted by TI-OS
(when put inside a string) . That paralysed me Sad
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.
  
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 5 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