TI-BASIC:Compression
Compression involves encoding data in an alternative format that has advantages over the un-encoded format. When determining whether to use compression, the main thing you should consider is its effectiveness (i.e., how much size and/or speed gain it results in). Of course, you need to decompress the data before you can use it again.
Contents
Graphing
One of the simplest ways of compressing data is by placing several related command values in a list, instead of listing out each individual command one after the other. A good example of this is when you are displaying a picture on the graph screen using several Pxl_On( commands. The Pxl-On( command has two arguments: an X and Y coordinate. After placing the coordinates in a list, we then just loop through the list with a For( loop:
:{10,10,25,25,50,50,60,60,35,35
:For(X,1,dim(Ans),2
:Pxl-On(Ans(X),Ans(X+1
:End
While this compression is effective, it can be improved upon. If you look at a number, it has an integer and fraction part. These two separate, but related parts can each be isolated using the IPart( and FPart( commands respectively.
Relating this back to our previous example, we should combine the two coordinates together, placing the Y coordinate as the integer and the X coordinate as the fraction. This effectively shrinks the list in half. For extracting each coordinate, you simply use the iPart( command to get the Y coordinate and multiply the fPart( command by 100 (E2) to get the X coordinate:
:{10.1,25.25,50.5,60.6,35.35
:For(X,1,dim(Ans
:Pxl-On(iPart(Ans(X)),E2fPart(Ans(X
:End
This compression technique was possible because the Pxl-On( command has two coordinates, but it would not be very effective if we were storing the Line( command's four coordinates: X1,Y1,X2,Y2. A better alternative would be to simply put all four coordinates together in the integer of the number. Probably the best example of this technique put to use is Bryan Thomas's Contra game.
The reason that this works is because a number can have up to 14 digits, so there are plenty of digits available for us to use. To extract each coordinate, you need to use a combination of iPart( and fPart(, multiplying by the related power of 10. The following code draws a line for each element in the list:
:{15231561,42133313,62186251,48604839
:For(X,1,dim(Ans
:Line(iPart(Ans(X)/ᴇ6),iPart(ᴇ2fPart(Ans(X)/ᴇ6)),iPart(ᴇ2fPart(Ans(X)/ᴇ4)),E2fPart(Ans(X)/ᴇ2
:End
(Note that the lines may not display correctly if you don't have the right graph screen coordinates, so you should set your calculator to a friendly graphing window to make all of the coordinates easily-compressible two-digit numbers. In this particular example, the graph screen coordinates are supposed to be X=0…94 and Y=0…62.)
Complex Numbers
Besides using the integer and fraction parts of a number, you can also use complex numbers. A complex number has two parts: the real part and the imaginary part. Just like how you were able to separate the integer and fraction part of a number, you can also separate the real and imaginary parts of a complex number:
:real(-5+8i // Returns -5 :imag(-5+8i // Returns 8
While this doesn't have much application because using the integer and fraction part of a number is generally sufficient, it can sometimes be used in place of a 2-by-n matrix; you just use a list of complex numbers, where column 1 is the real part and column 2 is the imaginary part.
Now we'll move on to a different programming situation. In games you sometimes need a switch that tells whether something is in the on or off state. It is fairly common to see beginner programmers utilize two or more variables to keep track of the switch and alternate one variable based on the other's value.
This is an ample place for not only compression but just good logical thinking. If you remember that each variable is considered a Boolean; that means the value indicates either true or false. A false value is zero while a true value is anything else. So, you just need to check to see if the value of the variable is zero:
:If not(F // Check if the flag variable is zero
Because the F variable can be either true or false, you have the switch built-in for you. Naturally you'll want to change the value of the switch from active to inactive or vice versa, either when a certain condition happens or you have gone through the game loop or whatever, and you can do that by simply using the not operator:
:not(F→F // Flip the value of the flag variable
Matrices
The most appropriate and needed place for compression is when storing lots of data, such as levels and maps. The most common variable used by people for storing data is matrices. This is because matrices are simple to use and they make sense since they are two-dimensional. However, matrices have one major disadvantage: size.
Instead of using matrices and wasting lots of precious space, the better approach is to use either lists or strings when storing your levels. Then when you want to use a level, you just convert it to a matrix and delete the matrix after you are done with it.
Compression via Lists
Here is a sample level stored as a list, with each element representing a row to be displayed on the home screen:
:3→dim(L1 :If L=1:Then // If level one :4444→L1(1 :5623→L1(2 :4567→L1(3 :End
Using the IPart( and FPart( commands that we discussed previously, you can break apart each number into its own separate integer and fraction elements. This allows us to then store each number into a specific position in the matrix, looping through it with a couple For loops:
:{3,4→dim([B]
:For(Y,1,3
:L1(Y→Z
:For(X,1,4
:iPart(10fPart(Z/10^X→[B](Y,5-X
:End:End
Compression via Strings
The formula for storing a level as a string and converting it to a matrix is not much different than it was for the list:
:If L=1:Then // If level 1
:"444456234567→Str1
:End
:1→F
:{3,4→dim([A]
:For(A,1,length(Str1
:exp(sub(Str1,A,1→[A]((fPart(A/4)!=0)+iPart(A/4),F
:F(F<4)+(F<4)+(F=4→F
:End
While this probably seems like a waste to go through all of this work just to compress a level, it is very important when you have lots of level that you want to store. In addition, the calculator only has a limited amount of memory to begin with, so you need to take advantage of every opportunity to save memory.
Single Digit Numbers
We can compress a list of up to 14 elements into a single integer whose digits are the elements in reverse. Say you had this 8-element list stored in L₁:
{7,0,3,4,1,6,6,2}
Then to compress, use this.
.1sum(L₁10^(cumSum(1 or L₁
Remember, 10^( is [2ND] then [LOG], not [1][0][^][(].
You should get this:
26614307
You'll notice that the digits are in reverse. That might be a bit confusing, but having it in reverse makes it smaller and faster.
So now, we decompress:
int(10fPart(Ans/10^(seq(Z,Z,1,8
In general, replace 8 with the dimension of your list, or log(Ans if the number of digits is unknown.
There you go. It is decompressed back into Ans. So, now we can compress single-digit data. But what about double-digits?
Double Digit Numbers
Double digits are a little more complicated, but they are also more useful because they allow up to 100 different positive integers instead of just 10.
Several methods were mentioned previously for decompressing 2-digit numbers, if you paid attention.
So, on to compressing! Say you had this 4-element list stored in L₁:
{24,47,36,42}
To compress it:
.01sum(L₁10^(2cumSum(1 or L₁
The answer:
42364724
The decompression:
int(E2fPart(Ans/10^(2seq(Z,Z,1,4
Multiple digits of any length
It is a little harder to compress multiple digit of any length into one number, so more code is needed to accomplish this. This method prompts the user for how many values should be entered and then prompts for each individual values. For the current version of this code, you must enter the values with zeroes in front if they are not of the maximum length. To change the maximum length, alter any occurrence of 10^(4) to e.g. 10^(5) for numbers of the length 5.
Example: If I want to input 3 numbers of the length 4. I would enter: 3 How many values I want to enter 001 075 254
That would then compress those numbers into a single number.
This code will not work if the resulting compressed number is longer than 14 digits long (the maximum calculator precision).
Key: A = compressed number N = how many values you want to input V = a new value to be processed = Denotes a comment in the code, shouldn't be included in your programs -> = Denotes the STO command
0->A Prompt N For(B,1,N) Prompt V A/10^(4)->A A+(V/10^(4))->A If B=N:A+B->A End Disp A // We are now decompressing A into L1 iPart(A)->N A-N->A N->dim(L1) For(B,1,N) A*10^(4)->A iPart(A)->L1(B) A-L1(B)->A End //Displaying the decompressed number in the form of a list Disp seq(L1(Z),Z,1,dim(L1),1)
I am currently trying to make this more friendly to programs that would possibly be able to use this within their own code.
References
- Bryan Thomas and his Contra game
- Arthur O'Dwyer and his Complete TI-83 Basic Optimization Guide tutorial
- Brandon Green and his Arrays: The Amazing Data Structure tutorial
- Martin Johansson and his String Compression tutorial
