|
|
|||||||
Update: Code now has case-sensitivity enabled to eliminate potential problems in sorting algorithms. ============================= The Burrows-Wheeler Transform ============================= This month we are going to decode a string mangled with the Burrows Wheeler Transform. Please don't be scared by the somewhat long motivation that follows, even if you are a beginner. At the end you will be shown a few pretty simple algorithms. Download the complete package at http://people.bu.edu/jenmeyer/kixtart/kixgolf_bwt.zip. You MUST use this package as it includes a UDF that will be used to score your entry automatically.It also includes a printable PDF document outlining the Burrows-Wheeler Transform. Please note the Special Recognition section further down in the desciption. ========== Motivation ========== The Burrows-Wheeler Transform (BWT) is a method that takes a block of text as input and rearranges it using a sorting algorithm. The unexpected thing is that the transform is reversible (which you normally don't expect. "sort" rarely comes with an "unsort"). The result of the transform is a block of text where consecutive letters are very often the same, so it can be easily compressed with even very naive algorithms. The BZIP program is based on this. So how does it work ? It's pretty easy in fact. Let's assume the input text is "DRDOBBS". Write the string and all rotated versions under each other like this: quote:Next sort rows: quote:And finally, write down the last column: "OBRSDDB". Also note that the D in the last column of the second-last row (that's the new row 5, or the old row 1) is the D that starts the word "DRDOBBS". These two together are the result of the transform: "OBRSDDB" and 5. It's pretty unexpected that this transform is reversible. One way to do that is to recover the (row n) lines in the sorted table. Let's first try to recover the sorted table a bit. We obviously already know: quote:In fact, we also know the first column, because it's just the letters in the last column, but sorted: quote:But this helps a lot ! From the row labeled with "(row 1)" we now know that R follows that D (remember that the strings were rotated, so the letter in the first column follows the letter in the last column). So if we know that the R is the first letter in row 1, we also know it's the last letter in row 2. So we can now extend our table to: quote:Now repeat the same reasoning for the row labeled "(row 2)" We see that the letter after R must be a D which corresponds to row 3. We already have one of the D's labeled, so it must be the other one. And let's repeat this process: quote:Oops, here we run into a problem. We know from the row labeled "(row 4)" that the letter after O is a B, but there are two of them in the last column. After which one should we write "(row 5)" ? To answer that, consider the letters that follow each B. By looking at a B in the last column and looking at the corresponding letter in the first column, we know they are B and S respectively. And since all rows are sorted, we in fact know: quote:This B and that S in the second column of course also occur in the first column somewhere (on the second and last row in fact), and since the first column is also sorted, they occur in the same order, B first (on the second row) and the S later (on the last row), and they each have a B in their last column). So after this subtle bit of reasoning we get to a very simple rule: if you have repeated letters in the first row (the B in BB and BS), they correspond to that same letter in the last row in exactly the same order. So the lines in a picture like this will never cross: The B in the first column of row one corresponds to the B in the last column of the second row, and the B in the first column of the second row corresponds to the B in the last column of the last row. Let's go back to our question. We had O which was followed by B due to the top row. This is the first B in column 1, so it corresponds to the first B in the last column, the one on the second row. Therefore that's the one we must label with "(row 5)". So we get: quote:The rest is simple (don't forget that after row 6 we get row 0, not row 7): quote:And finally we write down the first letters from the rows labeled "(row 0)", "(row 1)", ..., "(row 6)" and we get "DRDOBBS" ========== Algorithms ========== =========== Algorithm 1 =========== Wow, that was hard ! Or was it ? Let's redo the exercise using the special rule we found: "All occurrences of the same letter in the first column will correspond to all occurrences of that letter in the last column in the same order" (see the picture where this rule is demonstrated if the letter is B). Then we can start with the encoded string with below it the sorted string and position 5 marked: OBRSDDB BBDDORS In the sorted string at the bottom we see the first R marked. Now mark the first R in the top string (and the D below it): OBRSDDB BBDDORS So now we have the first D below marked. Now mark the first D at the top and the O below it (forget the old mark): OBRSDDB BBDDORS First O at the bottom marked, mark first O at the top: OBRSDDB BBDDORS First B at the bottom marked (this also happens to be the first time we are processing a B, but "first" here means it's the first B in the string "BBDDORS"), mark the first B at the top (that is, the first B in the string "OBRSDDB"): OBRSDDB BBDDORS Second B at the bottom marked, so mark the second B at the top: OBRSDDB BBDDORS First S at the bottom marked, mark first S at the top: OBRSDDB BBDDORS Second D at the bottom marked, but when we mark the second D at the top, we see we are back at the original: OBRSDDB BBDDORS When we look at each of the letters we marked at the top in order, we see: "DRDOBBS" =========== Algorithm 2 =========== Another way is to observe that if you know the first few columns in the sorted table, you can fill in the last column too. And since the letters in the last column are prefixes of the string you already have in a row, you can move that letter to the front, and you get a set of strings that must also be in the sorted table (but not sorted yet). Sort them, and we are in the start situation again, but all strings are one letter longer. This leads to the following method: First write down a column consisting of the encoded string: O B R S D D B Then sort it: B B D D O R S Now write the encoded string in front of that again: OB BB RD SD DO DR BS And sort it again: BB BS DO DR OB RD SD Repeat prefixing and sorting until you get: BBSDRDO BSDRDOB DOBBSDR DRDOBBS OBBSDRD RDOBBSD SDRDOBB Now take row 5, and move the D at the end to the front, giving: DRDOBBS Many more algorithms exist of course. Maybe they even lead to shorter programs... ============= Specification ============= You will have to write a KiXtart function called BWTDecode, which will decode a BWT-encoded string with a length between 0 and 999 characters. The valid character space of the encoded string is ASCII codes 32-126. The function will also require an integer offset. The offset number represents the character that will be the first character of the output (counting starts at zero, and the number will be less than the string length, you don't have to handle invalid input). The function must return the decoded string or an empty string in case the decoding fails. We use normal ASCII sorting. So if you get code:then the cosole output should be:$encoded = ’OBRSDDB’ code:=============encoded = OBRSDDB General rules =============
======== Deadline ======== The game starts December 18 (3:00pm EST). The private coding phase ends Sunday, December 29 at 3pm EST and the public coding phase ends January 5 (3:00pm EST). ============ Test program ============ A test program is provided to help screen entries and to provide the Golf Score. Any program that passes the test program can be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help me identify bugs in the test program. =================== Special Recognition =================== Special recognition for the person who can identify the author of input array element 4. ================================================================ KiXtart GOLF - How To Play ================================================================ Most importantly, anybody can play, no age restrictions, no penalties, no handicap! The object in "real" golf is to hit the ball in the hole in the fewest strokes. The object in KiXtart Golf is to get from input (tee) to target (hole) in the fewest keystrokes. Example: How many positive elements are in array $a? Array $a could be of structure $a=[1, 2 ,-3, 4, -5, -7, 8, 9] One approach: code:for a score of 45.for $b=0 to ubound($a) Another solution is: code:for a score of 53.DO Better approach: Code sample 1 ================================================================ KiXtart GOLF - The Rules ================================================================ 1) The goal of KiXtart Golf is to score the lowest strokes. 2) Strokes are all characters in a piece of code except whitespace characters, unless the whitespace character is necessary for the line of code to work. Therefore, carriage returns and line feeds do not count or spaces in between the '=' sign when assigning variables, e.g. '$a = $b' scores 5. 3) Code can be constructed any way you like, as long as it is syntactically correct with KiXtart. 4) The final solution MUST pass all test scripts that accompagny the KiXtart golf challenge. 5) The use of '$' as a variable is allowed. 6) In case of questions about a particular way to count the KiXtart Golf Challenge organizer has the last call. 7) During the private coding phase, no code is allowed to be posted. Violations result in disqualification of said player. 8) During the public coding phase, code should be posted, reused, and borrowed from other players. 9) The following script can be used to count the KiXtart Golf score: http://www.kixtart.org/cgi-bin/ultimatebb.cgi?ubb=get_topic;f=2;t=003608 ================================================================ KiXtart GOLF - The Duration of the Competition ================================================================ 1) Private coding phase: From date/time of posting the tournament challenge to the following Sunday, 3pm EST (BBS+6 time) 2) Public coding phase: From Sunday, 3pm EST (BBS+6 time) to the following Sunday, 3pm EST (BBS+6 time) 3) Final results: Sunday, 3pm EST (BBS+6 time) code:; KiXtart Golf [ 23. December 2002, 21:35: Message edited by: sealeopard ] |
||||||||
|
|
|||||||
sweet {edit} just one beer... then I'll start... {/edit} [ 18. December 2002, 21:21: Message edited by: Lonkero ] |
||||||||
|
|
|||||||
What do you mean? Not done yet? |
||||||||
|
|
|||||||
I have tight MSN conversation going on for next generation kixCode the beer is still in freezer. |
||||||||
|
|
|||||||
Breaking my head over this one... Jooel, just for you: Cheers |
||||||||
|
|
|||||||
I have auto update... that MS thingie... it broke my mediaplayer, will look that out later. anyway, I got bored after 20 lines of reading. jens, where is task so I can skip to that? |
||||||||
|
|
|||||||
Code is at the bottom, additionally, the ZIP file reference on the top contains everything you'll need including an external Golf Score UDF (kixgolf3.udf). It also includes the background as a PDF document. |
||||||||
|
|
|||||||
ok, finally, I got it to bottom. still skipped half trying again... |
||||||||
|
|
|||||||
what is the special stuff? didn't get it, didn't get it at all... |
||||||||
|
|
|||||||
quote:I guess it's time to read the complete post Or download the ZIP package! |
||||||||
|
|
|||||||
I might later, I found myself sleeping at my desk... anyway, I don't think checking the package will clear the person up and what to do with him. will check it anyway. |
||||||||
|
|
|||||||
look familiar? http://perlgolf.sourceforge.net/TPR/0/6/ |
||||||||
|
|
|||||||
Yes, that's one of my sources for KiXGolf. However, their solutions will not help you much as external programs are prohibited and thus a call to perl wouldn't work BTW, another inspirational website is at http://www.mathworks.com/contest/protein.cgi/home.html. Unfortunately, most of their contests are a little bit too much for KiXtart, though the Protein-folding one was very interesting. [ 19. December 2002, 16:21: Message edited by: sealeopard ] |
||||||||
|
|
|||||||
Not to mention the fact the contest is closed, so you can't see any of their perl solutions. |
||||||||
|
|
|||||||
Actually yes you can browse all the results. Go to the home page and follow the "post-mortem" link for the exercise. |
||||||||
|
|
|||||||
Yes, they have very interesting Perl solutions. You can't even tell whether the solution is encrypted or not by the way some of the code looks. Anyway, what's going on here? Nobody's posted anything yet, not even an answer to the 'Special Recognition' challenge. |
||||||||
|
|
|||||||
Im in - just doing my homework ... Charles Dickens ? |
||||||||
|
|
|||||||
Or should I say: DC*hirknsaceesl ? |
||||||||
|
|
|||||||
Congrats! And which story? Just kidding! I thought it would be fitting to test the encoder/decoder with the first two paragraphs of Charles Dicken's "A Christmas Carol". Anyway, good luck with coding the BWT-Decoder. |
||||||||
|
|
|||||||
oh - i wish Split() was more powerful |
||||||||
|
|
|||||||
Jens - you got those %?#@!@$ strict options turned on .... erggg lol |
||||||||
|
|
|||||||
ok - i just got this - is this good: quote: |
||||||||
|
|
|||||||
Well if Shawn is close to providing a solution I guess I will have to start investigating this challenge. |
||||||||
|
|
|||||||
I think i got a solution - just trying to get it to verify with Jen`s checker thingy ... something is broke somewhere - prob my routine - highly HIGHLY un-optimized at 800+ chars ... Jens - can we use the bsort routine included in the checker ? [ 19. December 2002, 19:37: Message edited by: Shawn ] |
||||||||
|
|
|||||||
From above: quote: |
||||||||
|
|
|||||||
Im not using Jens`s bsort routine - just fun'n |
||||||||
|
|
|||||||
Jens, Haven't dug deep into your checker or anything, but shouldn't this line here: case $sEncoded==$sDecoded be like this: case $sSource==$sDecoded -Shawn |
||||||||
|
|
|||||||
Shawn: Yes, you're right. I will correct this and post updated code both in the ZIP package and the top post in the thread. I also cleaned up those long lines a little bit. |
||||||||
|
|
|||||||
The validation routine has been updated due to a bug that Shawn found. Both the ZIP package and the posted code have now been corrected. BTW, if you'd like to post official results then you can use the kixgolf_bwt.txt file that is created in the script directory. Ultimately, this file will contain some info about the Kixtart process that ran the challenge. The idea is to create some kind of weighted average of keystrokes, running time, and memory usage to create the final score. This way somebody might be able to achieve a better score by e.g. optimizing memory usage but using up more keystrokes. This might make it more interesting. Comments on this idea are welcome. |
||||||||
|
|
|||||||
Shawn, I got the same thing. It looks like my function works, but I get "Validation = failed (unknown error)" -Eric |
||||||||
|
|
|||||||
Oh...There's two pages in this topic. I'm an idiot. Disregard the my last post. -Eric |
||||||||
|
|
|||||||
There will be more! I think we average 5 pages and 100+ post for each of the phases (private/public). [ 19. December 2002, 21:14: Message edited by: sealeopard ] |
||||||||
|
|
|||||||
ok, now as had time, I got the mission and the transform into my head. jens, it was matter of 2 not so clear statements. anyway, this looks nice and I'm sad that can't participate on the first round. |
||||||||
|
|
|||||||
Well, I have a working solution. quote:It works for all of the input strings. Now it's time to start chopping it down. |
||||||||
|
|
|||||||
maciep, have you tried it with longer input? if yes, then congratulations. |
||||||||
|
|
|||||||
Yeah, it works for all of them. I just didn't want to display the results from the longer ones because well...they're long. But there's still some trimming to do. |
||||||||
|
|
|||||||
I would like to propose a recommendation here - not sure if this is a requirement or not, but I think it is ... The Checker should make the following setting: setoption("casesensitivity","on") I believe (and correct me if im wrong) but this has to be done to get consistency across diff versions of sort routines ... it ensures that a series of mixed-cased letters are in proper order. Currently, bsort is NOT case sensitive so depdending on the string, you could have a series like this: mmmMMmmm then if you change the string slightly (add chars etc) the series could flip for no good reason: MmmmmmmM The mix of upper and lower is random ... if you actually dump the sorted string for minor variations of strings, might see it. Anyone have any comments ? |
||||||||
|
|
|||||||
Maybe we could ask Ruud to see if there is something that KiXtart does internally that would be suitable for a KiXgolf score. It could be an undocumented macro like @KIXGOLF or disguised as something legit like @COMMANDSUSED maybe? cj |
||||||||
|
|
|||||||
ceej, you are alive! [ 20. December 2002, 07:54: Message edited by: Lonkero ] |
||||||||
|
|
|||||||
I thought someone said my name 3 times cj |
||||||||
|
|
|||||||
Tadaa... quote:Long text takes very long... Must be the sorting... Will dig... |
||||||||
|
|
|||||||
who cares about speed? |
||||||||
|
|
|||||||
quote: |
||||||||
|
|
|||||||
As posted above, I playing with the idea of a weighted average of keystrokes, memory, and processing time I will also implement the SETOPTION('CaseSensitivity','on') into the code after a short test. |
||||||||
|
|
|||||||
but, that is just play right? that it does not count in this golf yet, right? |
||||||||
|
|
|||||||
Bummer, in some cases i loose Uppercase characters ??? Will check code Posted my score to early, it seems [ 20. December 2002, 13:51: Message edited by: Schuliebug ] |
||||||||
|
|
|||||||
Hey guys - the thingy with the case sensitivity is this - my premise is that this statement is required for both the checker sort and the solution sort. Obviously if the solution script doesn't need sorting than this is a non-issue. I think the thing that I would like to know is - of the people that have already submitted a solution script - did you need to turn on case sensitivity. If yes, then suggest we turn it on in the checker script - if no then obviously this isn't required and we should not turn it on. -Shawn |
||||||||
|
|
|||||||
No, I didn't have to turn on case sensitivity. Works fine without it. I think that as long as the encoder and decoder are sorting the same way, it's not an issue. |
||||||||
|
|
|||||||
I suggest that we turn it on anyways - just on matter of principle (i think). Don't think we can make the assumption that the encoder and decoder will be using the same sort routine. imho - think its more important that the encoder perform a proper (perfect) mixed-case ascii sort especially when this game gets down to the short strokes. |
||||||||
|
|
|||||||
I think I should have Shawn check the KiXGolf codes before posting as he already found two issues (nothing beats peer-review). Well done, Shawn. I tested the case-sensitivity and the encoded string differs based on whether case-sensitivity is enabled or not. Therefore, I have enabled case-sensitivity in order to guarantee correct ASCII sorting. Both the posted code and the downloadable ZIP file have been updated. There are still two modifications planned for the test script. Modification #1 would put the actual KiXGolf function BWTDecode() into it's own external UDF. This would easy upgrades to the test script. Modification #2 will be the implementation of extended statistics about the UDF. However, the extended stats will not influence the scoring process. I might do a third round of coding in the second week of January where we can experiment with those extended stats and see whether they would create interesting programming challenges. |
||||||||
|
|
|||||||
I don't know how much more I can trim down. quote: |
||||||||
|
|
|||||||
Still going... quote: |
||||||||
|
|
|||||||
This is where im at right now: quote: [ 20. December 2002, 17:43: Message edited by: Shawn ] |
||||||||
|
|
|||||||
I read through the rules, but I'm still not sure about something. Are we allowed to change the parameter names of our function. For Example: code: |
||||||||
|
|
|||||||
Yes, you can change the names of the parameters inside your function, thus code:would be valid. You cannot rename the name of the function though as this is fixed in the calling script.function BWTDecode($,$a) |
||||||||
|
|
|||||||
That's what I thought, but I just wanted to make sure. Here's my latest stats. quote: |
||||||||
|
|
|||||||
Broke 400 but still a bit away from Jan ... curious to see what maciep throws at us next though ... code:[edit]KiXtart A curve ball I see ! [ 20. December 2002, 18:40: Message edited by: Shawn ] |
||||||||
|
|
|||||||
Still looking. Here's the last run. quote: |
||||||||
|
|
|||||||
"Hey Rocky - watch me pull a rabbit out of my hat ... (flop) ... hmmm ... think Im going to need a new hat!" -- Bullwinkle Moose |
||||||||
|
|
|||||||
If CaseSensitive is turned on my score stands. |
||||||||
|
|
|||||||
Here's the last one. quote: |
||||||||
|
|
|||||||
Is Kix version 4.20 Alpha 1 ok? quote: |
||||||||
|
|
|||||||
I think we will have to exclude v4.20 alpha 1 as it is not publicly available. However, you will now have several people who would do anything to get their hand on this version just for the fact that you've been able to shave off another 100 keystrokes (Me included!) [ 21. December 2002, 22:31: Message edited by: sealeopard ] |
||||||||
|
|
|||||||
Well, it's not publically available unless you go to the DX21 website. Welcome to the board, Pamb. |
||||||||
|
|
|||||||
I think I still have some room to work. quote: |
||||||||
|
|
|||||||
Ok, being a fair person...it has now been tested in version 4.12. quote: |
||||||||
|
|
|||||||
Now that is MUCH better! That'll make some people real antsy now |
||||||||
|
|
|||||||
Bummer... Have to change my algorithm.... quote: |
||||||||
|
|
|||||||
I'm done with this for today. Don't think I can squeeze anymore out of it anyhow. And I know I'm not going to catch Pamb. quote: |
||||||||
|
|
|||||||
KiXGolf Score = 328 |
||||||||
|
|
|||||||
KiXGolf Score = 298 |
||||||||
|
|
|||||||
KiXGolf Score = 275 |
||||||||
|
|
|||||||
KiXGolf Score = 309 Gotta go do some Christmas shopping. I'll get back to this later. |
||||||||
|
|
|||||||
KiXGolf Score = 267 |
||||||||
|
|
|||||||
c:\data\scripts>C:\Data\Kix2001\KiX2001.412\kix32 golf\bwt\kixgolf_bwt.kix Source string = DRDOBBS String length = 7 Encoded string = OBRSDDB Offset = 5 Decoded string = DRDOBBS Validation = passed (decoded string is identical to encoded string) KiXtart KiXtart Version = 4.12 KiXGolf Script = kixgolf_bwt.kix Computer OS = Windows 2000 Professional CPU = Intel Pentium III Speed = 848 MHz KiXGolf Scoring Engine Scoring Engine = 3.0.3 KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Date & Time = 2002/12/21 16:18:00 KiXGolf Result = passed KiXGolf Score = 239 Thank you for participating in KiXtart Golf! |
||||||||
|
|
|||||||
|
||||||||
|
|
|||||||
Jens, please don't disqualify me. I added a Start time so that I could see how long the program runs on the longer text. No other modification was done in the forbidden zone. I can send you the updated code if you want to see it. quote:If I need a faster sorting algorithm then: quote:String length = 42 for both tests. [ 22. December 2002, 05:17: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Does speed count ? |
||||||||
|
|
|||||||
Only if the "String length = 749" does not finish in time for the end of the competition. [ 22. December 2002, 05:45: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Execution time and memory usage will be added through the extended statistics UDF as soon as I finish writing that UDF. The calling code is already in place. Neither execution speed nor memory usage will be used to create the KiXGolf scores in this round. However, they will be used to experiment with alternative scoring methods to make the challenges more challenging (pun intended ) |
||||||||
|
|
|||||||
Five hours and ten minutes of 99% CPU utilization to execute on the 749 character string. If I shorten my code by 15 characters, my score would be 231 but the execution time would be greatly extended. On a short string the 15 characters buys me a 300% improvement in performance. But on a long string the work content is much greater. I am not sure how long it would run. quote: [ 22. December 2002, 17:00: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Now that is interesting 5 hours? I wonder what the fastest solution is for the 700+ charcter string? I think I really need to get going on the extended stats. |
||||||||
|
|
|||||||
Five hours ??? Using the performance script you sent me Howard, and using the 749 length sting, the algorithm im using takes 7 SECS (the entire running time)!!! KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/22 12:01:21 Finish (Date/Time) = 2002/12/22 12:01:28 KiXGolf Result = passed KiXGolf Score = 267 The actual Decoder UDF itself takes about 441 msecs How come so long ??? [ 22. December 2002, 18:18: Message edited by: Shawn ] |
||||||||
|
|
|||||||
So obviously this is the case of smaller code but huge performance penalty ? |
||||||||
|
|
|||||||
Maybe we used different methodologies to solve the problem. Maybe I'm am just an idiot. Regardless of the reason, I still have a better score. |
||||||||
|
|
|||||||
Found a new approach. KiXGolf Score = 286 |
||||||||
|
|
|||||||
KiXGolf Score = 277 |
||||||||
|
|
|||||||
KiXGolf Score = 271. |
||||||||
|
|
|||||||
Wow, 7 seconds I'm beaten, my minimal length would be 288 |
||||||||
|
|
|||||||
KiXGolf Score = 266 |
||||||||
|
|
|||||||
Nevertheless, Howard still has the lead with a KiXGolf score of 231. Of course, that assumes that his algorithm will actually finish the long string by December 29 |
||||||||
|
|
|||||||
Don't know if I can squeeze out another 20. But I'll give it a whirl. KiXGolf Score = 251 |
||||||||
|
|
|||||||
Still 317... |
||||||||
|
|
|||||||
KiXGolf Score = 243 |
||||||||
|
|
|||||||
Alright, I'm throwing in the towel. I can't trim off anymore code. quote: |
||||||||
|
|
|||||||
I Think that the xmas present from Ruud is improved performance I’m not in contest. My score is 270, and i don’t intend to improve it (cannot) I just took this as a chance to compare the performance of the newer KiX version: String lenght: 218 Time for KiX 4.11 to complete: 1:59 Time for KiX 4.12 to complete: 1:39 Time for KiX 4.20 to complete: 1:01 So if not for other reasons, you should upgrade to the latest KiX version for speed. I believe I’m following the same path as Howard (slow, but the job is done) This was just a great opportunity to compare the different KiX versions for speed. Howard: Score = 231, i’m getting curious Shawn: 7 seconds, i’m getting even more curious -Erik |
||||||||
|
|
|||||||
Just in case somebody thinks about it. As KiXtart 4.20 beta 1 is public you are of course free to use it. |
||||||||
|
|
|||||||
Jens, this is a late call, Are you sure ? This allows two more buildin functions and an improved Join():
-Erik |
||||||||
|
|
|||||||
I didn't expect v4.20 to go public that fast. however, any public KiXtart version is allowed. KiXtat 4.20 alpha 1 was excluded since it was not public (sounded more like it leaked out). Anyway, there more than enough time to work on the code. The private coding phase will end on Sunday, December 29, 3pm EST and the public coding phase will end Sunday, January 5, 3pm EST. |
||||||||
|
|
|||||||
Wow! I just run my code on 4.20B1 and Wow! Execution time on the 749 byte string went from 5 hours 10 minutes to 2 hours 27 minutes. Good job Ruud. quote: |
||||||||
|
|
|||||||
I'm picking the towel back up for now. Execution time is somewhere under a minute KiXGolf Score = 241 |
||||||||
|
|
|||||||
Is that for the 749 byte string? |
||||||||
|
|
|||||||
Yeah. The actual decoding part takes around 25 seconds. That's on a 350(mhz) |
||||||||
|
|
|||||||
Just an update where i am. I've got two algorithms in the works ... a really slow one and a really fast one. The numbers are like follows: slow one: 232 fast one: 267 The fast one does the big string in under half a second. The slow one does the medium string in like 30 minutes or something - can't even bear to wait for it to finish [ 24. December 2002, 07:11: Message edited by: Shawn ] |
||||||||
|
|
|||||||
Sounds like your really stupid one is the same one I am using with a score of 231. I am now working on a super fast one (I hope). Still trying to understand what I am doing but it looks promising. |
||||||||
|
|
|||||||
Ive been staring at this fast one for over two days now - i've found a way to shave a couple more bytes, but I think a kixtart bug is getting in the way. hopefully, once the contest is over we can raise bring this Ruud attention. more importantly, not too sure which script I want to stare at for the next few days ... the smart one or the stupid one. |
||||||||
|
|
|||||||
I think my stupid one is pretty tight at 231. I can't seem to find any way to trim it. The smart method seems have a requirement that necessitates more code than the stupid way. [ 24. December 2002, 06:41: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Well - I finally now understand your comments re: the slow sort vs the fast sort Whats your time for the processing string #2 (len=139) ??? |
||||||||
|
|
|||||||
I can't find any saved data on that one. Sorry. I am currently executing the 749 byte string using the slow sort on 4.20B1 to see how long it takes. |
||||||||
|
|
|||||||
This may sound weird, but I can't remember my CPU FAN ever being on for this length of time - no joking !!! [ 24. December 2002, 06:58: Message edited by: Shawn ] |
||||||||
|
|
|||||||
Yeah, I have never heard my fan stay on for a couple minutes let alone hours like now. At least I am finnally using the potential of the CPU. I new there was some reason I bought a faster computer. [ 24. December 2002, 07:07: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
The 139 byte string took 1336181 msecs on a 500mhz P3 ... think thats about 22 minutes ... i got that right ? |
||||||||
|
|
|||||||
Score = 229 |
||||||||
|
|
|||||||
Arrggghhh!!! Now I have to stop working on the fast one to look at the slow one again. |
||||||||
|
|
|||||||
Start (Date/Time) = 2002/12/24 02:01:47 Finish (Date/Time) = 2002/12/24 02:01:50 KiXGolf Result = passed KiXGolf Score = 229 Damn, that was an obvious fix. Why didn't I see that before. Now you have the lead. Our code must be identical. |
||||||||
|
|
|||||||
I figured you would have went down to 228 because you have (had) a byte edge ... what happened to that ? |
||||||||
|
|
|||||||
See, you're still alert enough to realize that. I am winding down fast. Still looking for the wayward byte. [ 24. December 2002, 08:26: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Score = 226 |
||||||||
|
|
|||||||
quote: |
||||||||
|
|
|||||||
My 226 script just failed on the 139 length string ... so the game is still afoot ! |
||||||||
|
|
|||||||
I am sorry to here that, but |
||||||||
|
|
|||||||
Im re-running it inside the checker itself ... just to double-check ... |
||||||||
|
|
|||||||
Score = 235 For the 749 length string, decoding part takes about 10 seconds (733mhz) |
||||||||
|
|
|||||||
maciep, I can't wait to see your code. Small code + fast Don't get get it too small though |
||||||||
|
|
|||||||
score = 228 My code is barely making sense to me anymore. |
||||||||
|
|
|||||||
Now I'm upset |
||||||||
|
|
|||||||
score = 226 Works for all inputs Sorry Howard [ 24. December 2002, 19:21: Message edited by: maciep ] |
||||||||
|
|
|||||||
I just double-checked my 226 and it ran fine ! Theres no way im running the biggy on this though ... maciep - do you have a slow 226 or a fast 226 ? [edit] re-read the thread - guess that would be a fast 226 - Howard, looks as if both you and I are going to need a new hat [ 24. December 2002, 20:12: Message edited by: Shawn ] |
||||||||
|
|
|||||||
226 fast. |
||||||||
|
|
|||||||
It's back to brain storming... (trial and error) |
||||||||
|
|
|||||||
ok - the gloves are off and sanity is being thrown out the window: StringLength = 139 RunningTime = 1 hour !!!! KixGolfScore = 220 Im just trying to wear you down now ! [ 24. December 2002, 21:47: Message edited by: Shawn ] |
||||||||
|
|
|||||||
My slow method has now been running on the 749 byte string for 18+ hours. 220 My brain has been fried switching back and forth on these two methods. Can I do this in Perl please I haven't given up yet. [ 24. December 2002, 21:55: Message edited by: Howard Bullock ] |
||||||||
|
|
|||||||
Longest string takes 50 minutes... quote: |
||||||||
|
|
|||||||
Im a little confused about how we are going to "validate" a winner. The checker script uses a "random" string ... which one of those strings are we going to use to valid the winner ? If the winner takes two days running time to validate against the biggest string - whats that going to mean ? |
||||||||
|
|
|||||||
Well, it's time to do the holiday thing. I'll jump back into this in a couple of days. Try to keep those scores nice and high for me. Last Run: Score = 223 |
||||||||
|
|
|||||||
Stil not in contest I have implemented the 'hard' way = 'fast' way This brought my score up to 586 (more than double the smallest in contest ) But the time for the executing the long string (749) got down to 4 secs. instead of X hours I noticed a post from maciep: quote:It would be nice to have a third round of golf (Club house discussion ), where the function-/variables-names where discriptive. It would spare us all from trying to understand the brilliant code from the winner. I use a lot of the ideas from the INI-write golf competition, BUT you have to participate to understand the problem/code fully. -Erik |
||||||||
|
|
|||||||
25+ hours and still churning. I cannot fathom how anyone can implement the fast process in less than 260 characters at this time. My fast process is currently around 270 characters. I am sure there are some things that could be improved upon, but the slow method employs less processes and therefore less code. How can the fast process be implemented in 226 characters? I'm still scratching my head how you Shawn got to 220. Still scratching my head. |
||||||||
|
|
|||||||
Well, if its any consolation I don't think I can squeeze any more out of this 220 script - in fact since I really dont want to test it on the 700+ string - it might not even qualify as a valid score. Might have to start looking at yet another algorithm ... Maybe we should have two prizes in this round ... one for the shortest script and one the fastest script ... |
||||||||
|
|
|||||||
45 hours 15 minutes and still churning... the simple slow method is indeed sloowww!!!! |
||||||||
|
|
|||||||
Well, I've tried just about everything I can think of to cut three more stokes off my score, but to no avail. Decoding takes about 5 seconds on the large string input. (ver 4.20 and 730mhz) quote: |
||||||||
|
|
|||||||
You did write your own sorting code, right? |
||||||||
|
|
|||||||
You mean we can't use the provided b-sort function? Just Kidding!! . Yeah, I wrote my own sorting method. It's all in the BWTDecode function. |
||||||||
|
|
|||||||
Can't wait to this code |
||||||||
|
|
|||||||
Still testing the core code on the long string: CPU so far: 64 hours 10 minutes This change occurs after the core processing. Source string = DRDOBBS String length = 7 Encoded string = OBRSDDB Offset = 5 Decoded string = DRDOBBS Validation = passed (decoded string is identical to encoded string) KiXtart KiXtart Version = 4.20 Beta 1 KiXGolf Script = kixgolf_bwt.kix Computer OS = Windows 2000 Professional CPU = Intel Pentium III Speed = 848 MHz KiXGolf Scoring Engine Scoring Engine = 3.0.3 KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/26 16:22:06 Finish (Date/Time) = 2002/12/26 16:22:09 KiXGolf Result = passed KiXGolf Score = 225 |
||||||||
|
|
|||||||
quote:{edit - changed the output file to also include the string length and the elapsed time...} [ 27. December 2002, 13:37: Message edited by: MightyR1 ] |
||||||||
|
|
|||||||
8 to go... quote: |
||||||||
|
|
|||||||
Getting closer: Score = 224... |
||||||||
|
|
|||||||
Nice! Now stop |
||||||||
|
|
|||||||
ANYBODY OUT THERE??? quote: |
||||||||
|
|
|||||||
Alright. I guess I have to study my code a little more. Maybe I can get a couple more chopped off my score. |
||||||||
|
|
|||||||
Let's beat the 220 limit!!! |
||||||||
|
|
|||||||
I'm with you. |
||||||||
|
|
|||||||
DID IT... quote: |
||||||||
|
|
|||||||
You guys have me pulling out what hair is left on my head. I can't seem to find a methodology to get the performance up and shave strokes. |
||||||||
|
|
|||||||
Nice job Patrick. I'm still stuck at 223. |
||||||||
|
|
|||||||
Well done Patrick. |
||||||||
|
|
|||||||
KiXGolf Score = 207 String length = 749 quote: |
||||||||
|
|
|||||||
WOW! Start and finish on the same day. Obviously you found another methodology. |
||||||||
|
|
|||||||
This was the same basic methodology as my 284 script but a light bulb went on after dinner and this is the result. Since this works, I decided to kill my old process which has been consuming 99% of my CPU for 92 hours 20 minutes. |
||||||||
|
|
|||||||
Way to go Howard !!! |
||||||||
|
|
|||||||
KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/27 22:22:38 Finish (Date/Time) = 2002/12/27 22:22:41 KiXGolf Result = passed KiXGolf Score = 206 |
||||||||
|
|
|||||||
KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/27 23:53:40 Finish (Date/Time) = 2002/12/27 23:53:42 KiXGolf Result = passed KiXGolf Score = 203 |
||||||||
|
|
|||||||
Ouch... You've hit me hard Howard!!! Well done Will see if I can take 16 chars off... [ 28. December 2002, 13:54: Message edited by: MightyR1 ] |
||||||||
|
|
|||||||
I don't see me being able to make mine much smaller if at all. Good luck to all. |
||||||||
|
|
|||||||
208... |
||||||||
|
|
|||||||
204... quote: [ 28. December 2002, 18:25: Message edited by: MightyR1 ] |
||||||||
|
|
|||||||
YAHOOOOO quote: |
||||||||
|
|
|||||||
good work, but I guess the ball is back in my court. |
||||||||
|
|
|||||||
Howard, Let your brains squeeek When is the closing of fase 1 --> 2002-12-29;21:00:00 BBS time??? |
||||||||
|
|
|||||||
24 hours from now (notice the time on this post). |
||||||||
|
|
|||||||
OK.... Squeek..Sqiiirt.. Can't get anymore out of my brains... |
||||||||
|
|
|||||||
Still on top KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/28 15:36:16 Finish (Date/Time) = 2002/12/28 15:36:22 KiXGolf Result = passed KiXGolf Score = 201 |
||||||||
|
|
|||||||
Congrats, I think I'll trow in the towel... |
||||||||
|
|
|||||||
I was there a couple days ago. Are you sure that you can't tweak a little more? |
||||||||
|
|
|||||||
Will sleep a night over it (2002-12-29;00:30 over here) 20.5 hrs to go... {edit - noticed BB time is behind... HENRI???} [ 29. December 2002, 00:24: Message edited by: MightyR1 ] |
||||||||
|
|
|||||||
RECLAIM TOWEL... IT'S A TIE... (for now... ) quote: |
||||||||
|
|
|||||||
Can the 200 char barrier be broken??? YES it CAN: score=197 Howard, it's in your hands again... |
||||||||
|
|
|||||||
Patrick, I thought you were going to sleep. Now I have to stop my movie and work on this again. |
||||||||
|
|
|||||||
Yippee KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/28 21:20:18 Finish (Date/Time) = 2002/12/28 21:20:20 KiXGolf Result = passed KiXGolf Score = 195 |
||||||||
|
|
|||||||
KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Start (Date/Time) = 2002/12/28 21:25:32 Finish (Date/Time) = 2002/12/28 21:25:35 KiXGolf Result = passed KiXGolf Score = 193 |
||||||||
|
|
|||||||
|
||||||||
|
|
|||||||
quote: |
||||||||
|
|
|||||||
I think it is all wrung out. It was a pleasure going down to the wire with you. Please don't make think anymore |
||||||||
|
|
|||||||
Congrats from me... I'm stuck at 197 |