| |
WVL
Registered: Mar 2002
Posts: 902 |
WVL/Xenon's challenge!
A small challenge for all coders out there.
first let me explain how i got here. As most of you will know i'm working on a c64 conversion of Pinball Dreams. And as some will know, i'm rather stumbling on the 64K memory limit. So I'm always puzzling and optimizing to free up some more memory.
This morning i got an idea to optimize the way the clipmap data is stored. (what is the clipmap, you might ask? it's a black/white map that describes where the ball goes behind objects on the table).
Now this clipmap is stored as a 40*64 charscreen (RLE-ed) and a charset (lucky for me, it fitted in $a1 chars).
The idea comes to letting go of putting the chars at n*8 memory position with n integer and using pointers to point to where the data is to be fetched. The pointers will not costs any memory themselves, as for speed i'm already using a 512 table (lo/hi) with numbers times 8.
;---------------------------------------
so here's my challenge to you all!
;---------------------------------------
try to fit all $a1 chars of this charset : http://www.interstyles.nl/Charset.prg into the minimum amount of bytes you possibly can!
the answer has to be in the following form :
-a pointer table, with $a1 pointers to the positions in the chardata
-a chardata bin, as small as possible.
ofcourse all the chars still have to be made from the pointer table and the bin. All the chars have to lie COMPLETELY inside the bin, don't assume the bytes before or after the bin take on certain values.
Winner gets a beer + a hug if winner is a girl ;-)
regards,
WVL/XENON, who's anxious to win the competition himself ;-) |
|
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
How about something like this...
for each char (x)
....for each char (y)
........for each char (z)
............if (the gfx of x is within the gfx of the (y,z) or (z,y) combination)
............then store the z/y data, and the pointers to x/y/z
........if (there were no hits)
............check if x's gfx is within the allready stored char gfx
................if yes, store the pointer to it
................else store x's gfx and the pointer to it
|
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
It would be nice if the <code> or <pre> tag was enabled btw. |
| |
WVL
Registered: Mar 2002
Posts: 902 |
I'm already doing something like that, but more random. The thing is that the search space is just overwhelmingly large, imo about 16^640.
So far i managed to remove 630 bytes from the bin, not counting the pointertables.
I really wonder if other ppl will be able to do it better :) (btw, searching for 630 cost me about 3 hours on a athlon 2800+) |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
where do you get that 16^640 from? Guess you must do something completely different than my pseudo-code, since as far as I can see, it only runs through the inner loop $a1^3 times. |
| |
WVL
Registered: Mar 2002
Posts: 902 |
I'm just estimating the smallest bin is around 640 bytes long. Now i don't use every byte, but i only turn bit-pairs on/off. -> 16 possibilities for each byte. giving a total of 16^640.
ofcourse i don't hunt through it like this, instead i try to put the chars in different order, so i try $a1! permutations. The chars are chosen randomly, but weighted towards more overlapping bytes (the code generates a 2d table with the # of overlapping bytes for each char-pair). During generation of a permutation, it is constantly being checked if any of the other left chars have a match in the final bin.
So _my_ search space is $a1!, but i guess to find the optimal solution, one would have to search through 16^640. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
cruzer: theoretically you have to check all permutations of the order of those 161 chars. that gives you a search space of 161! = 7.6*10^286 permutations. your routine has a much better big-O performance because it does only search a small fraction of the permutations and will most likely give worse results. |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
I can't really see why you need to check all permutations of size $a1. Shouldn't it be enuff with size 2, since the 8 bytes of a char can only span across 2 other chars? |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
what you do is local optimization. however, a local optimum often causes other local optima being undiscovered which makes global optimisation impossible. to really find the best solution, you would have to scan all 161! possibilities. ofcourse this is an impossible task... but you still might find better solutions than the ones you find through strict local optimization. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
This problem is indeed NP-complete.
Imaging constructing a graph with N*M nodes, all connected with each other. (N,M=$A1)
D[N,M] = 7 - The number of saved bytes by letting N overlap M. (7 is the maximum number of bytes to be saved on a pair considering WVL already have removed duplicate chars)
So, we have N*M nodes, all connected with each other. The lenght of each edge i denoted by the D[N,M] matrix. And if we choose one particular pair to be next to each other, let's call them X and Y, then all other X,? and ?,Y becomes useless (other chars can be next to them at the same time). So, we want to choose N-1 pairs and at the same time minimising the sum of all D[N,M]. This is effectivly the TSP-problem but without having to reach the beginning again, which still is NP-complete to my knowledge.
So find a fast good approximative solution to TSP and you have a good approximate to your problem aswell.
One way is to create a minimum spanning tree, then take the hamiltonian tour of the MST which gives you a correct solution. Then apply local optimisations. This algorithm is O(n^2) and is fairly good. Dunno if it gets below your saving you already have, but it's certainly hellish much faster.
And most probably there are already some academic out there with a very long beard who has implemented a near optimal solution which is lightning fast in C, ready for you to download. :D
/JackAsser
|
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
Btw, since the charset is in double-pixel resolution with only 2 colors you could save half the gfx-data by packing 2 bytes in 1. This will ofcourse make the fetching a bit slower, so it requires that you're not running short on cycles too. |
... 38 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
