KiXGolf: Part 3 - And the winners are... (and alternate scoring method) - KiXtart.org

You are not logged in. [Log In] KiXtart.org website » Forums » KiXtart » Lounge » KiXGolf: Part 3 - And the winners are... (and alternate scoring method)

Page 1 of 1

Topic Options

#97469 - 2003-01-06 03:49 AM KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	KiXtart Golf: Burrows-Wheeler-Transform Results The tournament started on December 18, 2002 in this thread KiXGolf: Burrows-Wheeler Transform The tournament package is available at http://people.bu.edu/jenmeyer/kixtart/kixgolf_bwt.zip. Answer for the special recognition challenge was: Charles Dickens as the quote is from the first paragraphs of "A Christmas Carol". Winner for the special recognition challenge is : Shawn, who provided the correct answer some 20 hours after the challenge was posted. First valid KiXGolf Scorer (private coding): maciep with a KiXGolf score of 628 on December 20, about 28 hours into the challenge. Winner of the first round (private coding): Howard Bullock with a KiXGolf score of 193 on December 29. Winner of the second round (public coding): MightyR1 with a KiXGolf score of 191 on December 29, about one hour after Howard posted his code. MightyR1 took advantage of an apparent bug in the way ASC() handles a multi-character string. Special recognition also goes to Howard Bullock who took his CPU beyond the normal usage pattern and had his computer runnign for over 92 hours at 100% CPU usage without damage to his computer However, his final winning code is slightly faster A graph outlining the improvements of the various codes will follow on Monday (KiXGolf Score versus BBS Posting Time for all participants). And now to the third part! Part three is a test for some potential improvements to the KiXGolf scoring. Not only will you have to minimize your keystrokes, but you will also have to take into consideration memory usage and running time. The Extended KiXGolf Score will be a weighted average of those three indicators. An update KiXGolf package including the new measurements is available at http://people.bu.edu/jenmeyer/kixtart/kixgolf_bwt.zip. For easier coding purposes the actual BWTDecode() function has been moved into it's own external UDF file. Additionally the function can be run multiple times inside a loop to measure average performance more precisely. Timing is accurate to the millisecond and memory usage is accurate to the byte. A text file is created automatically which contains computer information and the extended KiXGolf statistics so they can be easily posted on the KiXtart BBS. I would like to ask all of you who participated or who are generally interested in KiXGolf to download the updated package and run it on your computers. Please post back the text file containing the enhanced performance information. You can also give the various other posted solutions a try or post your own BWTDecoder even if it didn't win anything. I am very interested in how the Extended KiXGolf score look like on different computers and with different algorithms. Ultimately the Extended KiXGolf Score will be calculated by testing all submitted solutions on the same computer to create a level playing field. Also, please feel free to comment of the implementation of the extended measurements and the usefulness of them. [ 06. January 2003, 03:57: Message edited by: sealeopard ] _________________________ There are two types of vessels, submarines and targets.
Top

#97470 - 2003-01-06 04:01 AM

Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)

Sealeopard Offline

KiX Master

Registered: 2001-04-25
Posts: 11165
Loc: Boston, MA, USA

My results for the winning code running ten repetitions of the longest 749 character string:

code:

KiXtart
KiXtart Version  = 4.20 Beta 1
KiXGolf Script   = kixgolf_bwt.KIX

Computer
OS               = Windows 2000 Server
CPU              = Intel Pentium III
Speed            = 1000 MHz
Memory           = 511 MB

KiXGolf Scoring Engine
Scoring Engine   = 3.0.3

KiXtart Golf Score
Tournament       = KiXtart Golf: Burrows-Wheeler Transform
Date & Time      = 2003/01/05 22:04:17
KiXGolf Result   = passed
KiXGolf Score    = 191
 
Extended KiXtart Golf Statistics
Number of Repetitions          = 10
Start Time                     = 2003/01/05 22:03:34.587
Stop Time                      = 2003/01/05 22:04:17.588
Running Time                   = 0000/00/00 00:00:43.001
KernelModeTime [ms]            = 00:00:00.000
Avg. KernelModeTime [ms]       = 00:00:00.000
UserModeTime [ms]              = 00:00:41.920
Avg. UserModeTime [ms]         = 00:00:04.192
Execution Time [ms]            = 00:00:41.920
Avg. Execution Time [ms]       = 00:00:04.192
delta HandleCount              = 0
delta ThreadCount              = 0
delta PeakWorkingSetSize [kB]  = 0
delta WorkingSetSize [kB]      = 184
KiXGolf Score                  = 191
KiXGolf Weighting              = 0.5
Running Time Score [s]         = 4.192
Running Time Weighting         = 0.25
Memory Score [kB]              = 184
Memory Weigthing               = 0.25
Extended KiXGolf Score         = 142.548
 
Thank you for participating in KiXtart Golf!

[ 06. January 2003, 04:03: Message edited by: sealeopard ]

_________________________
There are two types of vessels, submarines and targets.

Top

#97471 - 2003-01-06 04:04 AM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Lonkero Lonkero KiX Master Guru Registered: 2001-06-05 Posts: 22346 Loc: OK	mmm... not sure, but should the memory have so much weight? I would like to reduce it's importance as if it takes much memory, also the speed will decrease. _________________________ ! download KiXnet
Top

#97472 - 2003-01-06 04:08 AM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	That's one of the questions to be solved. How to weight them. It'll need some tweaking so that a faster code that for example uses 10 more characters wins over the slower code. The current weighting is definitely not optimal. It also depends on the ranges for all values. Time has pretty much no influence for small numbers. However, it's currently just a test anyway. _________________________ There are two types of vessels, submarines and targets.
Top

#97473 - 2003-01-06 04:43 AM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Howard Bullock Howard Bullock KiX Supporter Registered: 2000-09-15 Posts: 5809 Loc: Harrisburg, PA USA	Hi Jens, the memory reading seems to be off a little. (Memory = 1245 MB) I only have 512MB unless you are counting the SWAPfile. code: KiXtart KiXtart Version = 4.20 Beta 1 KiXGolf Script = kixgolf_bwt.kix Computer OS = Windows 2000 Professional CPU = Intel Pentium III Speed = 848 MHz Memory = 1245 MB KiXGolf Scoring Engine Scoring Engine = 3.0.3 KiXtart Golf Score Tournament = KiXtart Golf: Burrows-Wheeler Transform Date & Time = 2003/01/05 22:43:25 KiXGolf Result = passed KiXGolf Score = 191 Extended KiXtart Golf Statistics Number of Repetitions = 10 Start Time = 2003/01/05 22:42:33.669 Stop Time = 2003/01/05 22:43:24.985 Running Time = 0000/00/00 00:00:51.316 KernelModeTime [ms] = 00:00:00.010 Avg. KernelModeTime [ms] = 00:00:00.001 UserModeTime [ms] = 00:00:48.389 Avg. UserModeTime [ms] = 00:00:04.838 Execution Time [ms] = 00:00:48.399 Avg. Execution Time [ms] = 00:00:04.839 delta HandleCount = -2 delta ThreadCount = -1 delta PeakWorkingSetSize [kB] = 0 delta WorkingSetSize [kB] = 188 KiXGolf Score = 191 KiXGolf Weighting = 0.5 Running Time Score [s] = 4.839 Running Time Weighting = 0.25 Memory Score [kB] = 188 Memory Weigthing = 0.25 Extended KiXGolf Score = 143.70975 Thank you for participating in KiXtart Golf! Also, not sure why it says ten repetitions and visually displayed two string lengths. quote: C:\Data\Scripts\Golf\bwt>C:\Data\Kix2001\KiX2001.420b1\kix32 kixgolf_bwt.kix Source string = Marley was dead: to begin with. There is no doubt whatever about 'that. The register of his burial was signed by the clergyman, the clerk, the undertaker, and the chief mourner. XXX signed it. And XXX' s name was good upon 'Change, for anything he chose to put his hand to. Old Marley was as dead as a door-nail. Mind! I don't mean to say that I know, of my own knowledge, what there is particularly dead about a door-nail . I might have been inclined, myself, to regard a coffin-nail as the deadest piece of ironmongery in the trade . But the wisdom of our ancestors is in the simile; and my unhallowed hands shall not disturb it, or the Count ry's done for. You will therefore permit me to repeat, emphatically, that Marley was as dead as a door-nail. String length = 749 Encoded string = nt..e!t.dt.....d.dtssrdr;,rddssleosdeeeeaysssetIsaaao,,essdtgftsynfseebdInttIffd,sslre,m,fy setooeoossXey,rdy,snn,ttl:e,endeeydyyyel,tuend yXn rtedwtynkfenrrrtellothrrlde ' . XXXX eeeer ennnntihhcnem hhh gMMMlp ww www hhhehhhhsr aau ien n ilnraaaeeennnoneaa nae s nhvhhhhhnrrcrh hsmhhmhggdldddddmpinwnnlbirrbrs ervtknhhhllpdgdctlllooeoolof enendnieeii rtsn Cttwtwp tt tttTttttTttct cgrt tphmssaaaamws gf Mlh hh wgdm wra illaiiiuOiwccrrrecaiaalrloy a irn e oewiiaioai---- aiAaaaiuaoggiriaou o kkuatnttttto cdpddmrgdddf oooffthnYdC mbbnln e m u euoeoeoooeotuaeeoe eueaaaaeuioeaetaaaaiaaa'aiir'ii daa ioy eieiuaauohui'suabaiiarsai ' yar s nsooc o otbooopBaeo o oolrmabmeeerlgmn Offset = 224 Decoded string = Marley was dead: to begin with. There is no doubt whatever about 'that. The register of his burial was signed by the clergyman, the clerk, the undertaker, and the chief mourner. XXX signed it. And XXX' s name was good upon 'Change, for anything he chose to put his hand to. Old Marley was as dead as a door-nail. Mind! I don't mean to say that I know, of my own knowledge, what there is particularly dead about a door-nail . I might have been inclined, myself, to regard a coffin-nail as the deadest piece of ironmongery in the trade . But the wisdom of our ancestors is in the simile; and my unhallowed hands shall not disturb it, or the Count ry's done for. You will therefore permit me to repeat, emphatically, that Marley was as dead as a door-nail. Validation = passed (decoded string is identical to encoded string) [ 06. January 2003, 04:45: Message edited by: Howard Bullock ] _________________________ Home page: http://www.kixhelp.com/hb/
Top

#97474 - 2003-01-06 04:49 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	Take a look at the code, the loop only loops through the decoder itself, not the preliminary stuff. Also, measurements are taken right before and after the loop. With regards to the memory issue. I implemented the KiXtart MEMORYSIZE() function, maybe that one doesn't retrieve it correctly. I can switch it over to WMI as the performance counters require WMI, too. [ 06. January 2003, 16:49: Message edited by: sealeopard ] _________________________ There are two types of vessels, submarines and targets.
Top

#97475 - 2003-01-06 05:18 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Jack Lothian Jack Lothian MM club member Registered: 1999-10-22 Posts: 1169 Loc: Ottawa,Ontario, Canada	Jens, It's your contest but I like the original premise - count the length only. Even when I don’t have time to compete, I like reviewing the winners & it is amazing the tricks I learn. In addition, squeezing out every byte tests KixTart to its limit & your contests have done a lot to reveal Kixtart’s strengths, limits & weaknesses. I suggest leaving the primary objective as it is. I think you muddy the waters by introducing competing criteria of success. Code size, speed, & memory use are all important but they can compete against each other when you try to optimize one. I am not sure there is any linear weighting function will successfully marry the 3 dimensions. To my mind, it like trying to award a prize for the fastest racing car with the best gas mileage. I think leaving the dimensions separate is the way to go. Maybe you should award a secondary prize for the script that runs the fastest. Call it phase III or what ever. _________________________ Jack
Top

#97476 - 2003-01-06 08:35 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
kholm kholm Korg Regular Registered: 2000-06-19 Posts: 714 Loc: Randers, Denmark	Jens, Shawns code is about 850 times as fast as the winning code Eventhough Shawns code is way faster and uses less memory it still loose in the Extended KiXGolf Score I don’t belive it is possible to make a weighted score, so maybe you should omit the Extended KiXGolf Score I like the other stat’s, but i agrre with Jack, the only thing we can compare during the competition is the size. To check Shawn’s very fast script, change kixgolf_bwt.udf to: code: ; begin Burrows-Wheeler Transfrom Decoder SHAWNS CODE ;! Function bwtdecode($s, $x) Dim $,$j,$k,$n $n = Len($s) - 1 Dim $t[$n],$l[$n],$c[255] For $ = 0 To $n $l[$] = Asc(SubStr($s,$ + 1,1)) $j = $l[$] $t[$] = $c[$j] $c[$j] = $c[$j] + 1 Next For $ = 0 To 126 $k = $k + $c[$] $c[$] = $k - $c[$] Next For $ = 0 To $n $x = $t[$x] + $c[$l[$x]] $bwtdecode = Chr($l[$x]) + $bwtdecode Next EndFunction ;! ;! -Erik
Top

#97477 - 2003-01-06 08:49 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	Maybe I should say it again. It's an experiment right now to see whether the other two variables could be used. The weighting is absolutely arbitrary right now. So far, the consensus is to only use the keystrokes for scoring. _________________________ There are two types of vessels, submarines and targets.
Top

#97478 - 2003-01-06 09:10 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Jack Lothian Jack Lothian MM club member Registered: 1999-10-22 Posts: 1169 Loc: Ottawa,Ontario, Canada	Jens, Thanks for preparing the contests. I enjoy them tremendously & they add a new dimension to the board. _________________________ Jack
Top

#97479 - 2003-01-06 09:45 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
BrianTX BrianTX Korg Regular Registered: 2002-04-01 Posts: 895	My 2 cents -- I believe that there is just as much value (perhaps more) in shortening the execution time as there is in shortening the code. In a logon script, for example, there is the time it takes to execute the script as well as the time it takes to download the script. In most cases, the execution time becomes a much greater factor, especially on slow machines. I think we would do well to focus on execution time and memory usage in addition to code length. It is easy to measure shorter code, but it is NOT easy to measure execution time because this varies on each computer. Thus, a bit of extra emphasis on this area is worthwhile. However, I do not necessarily believe that an "Extended Golf Score" that is a composite of multiple variables would be beneficial. To the contrary, a separate score could contain the execution time, and yet another could contain memory usage, if necessary. Optimization for each separate metric would be beneficial and could exist separately from each of the others. I believe that the only way a composite score would be beneficial is if it was tailored to each KiXgolf competition. For example, a competition could be to sort a given multi-dimensional array with these criteria: 1. Finish in under 100 ticks on a reference PC. 2. Be shorter than 100 keystrokes. Seperate winners would exist in each category. Unfortunately, it would be difficult to tell your progress if your PC differs from the reference PC. This brings me to another point: the benefit of creating a table that shows measurements of different KiXtart operations on different PC configurations.... Essentially, this would be a benchmark test. Perhaps, a benchmarking test would be worthwhile as the next KiXgolf coding challenge, though probably a little large in scope for a competition of that nature. Brian
Top

#97480 - 2003-01-06 10:36 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	The weighting would be tailored to each KiXGolf task. The extended score would be performed by submitting the UDF to a webserver which then runs the script locally. This way, all UDFs are automatically tested on the same 'reference' PC. _________________________ There are two types of vessels, submarines and targets.
Top

#97481 - 2003-01-06 10:37 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
kholm kholm Korg Regular Registered: 2000-06-19 Posts: 714 Loc: Randers, Denmark	Jens, I know your scoring method is experimental Why not let size and time be equally important! Then the Extended KiXGolf Score could be then be calculated like this: code: $dExtScore=$dGolfScore*$dTimeScore Scores: Shawn : Extended KiXGolf Score = 12,282 Howard: Extended KiXGolf Score = 533,279 How do we compare in the ‘secret’ part one of the competition? The next competition could be making a fair scoring UDF for extended KiXGolf score Should the result be multiplied by CPU speed ?
Top

#97482 - 2003-01-06 10:45 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Lonkero Lonkero KiX Master Guru Registered: 2001-06-05 Posts: 22346 Loc: OK	mmm... now this server would need to have multiple versions of kixtart... or the rules need to changed. anyway, I still don't get it... what is the value of memory usage? if memory usage is more, mostlikely the code is longer or then the execution time is longer. so, I go to my first question: why it should be an factor? _________________________ ! download KiXnet
Top

#97483 - 2003-01-06 11:01 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	The memory usage would differ if different algorithms are used. In the current KiXGolf it would most likely make a difference when comparing the sorting and the non-sorting algorithm. I will test the different posted UDFs at home to get a comparison. [ 06. January 2003, 23:02: Message edited by: sealeopard ] _________________________ There are two types of vessels, submarines and targets.
Top

#97484 - 2003-01-06 11:45 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
MightyR1 MightyR1 MM club member Registered: 1999-09-09 Posts: 1264 Loc: The Netherlands	Jens, any reason why in the latest package, the bwt udf does not contain the winning code? Erik/Jens, notice the for 0 to 126 loop... Not all ascii char's are used or the loop should end to 255... _________________________ Greetz, Patrick Rutten - We'll either find a way or make one... - Knowledge is power; knowing how to find it is more powerful... - Problems don't exist; they are challenges...
Top

#97485 - 2003-01-06 11:47 PM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Sealeopard Sealeopard KiX Master Registered: 2001-04-25 Posts: 11165 Loc: Boston, MA, USA	I thought it does contain the winning UDF (Score 191)? _________________________ There are two types of vessels, submarines and targets.
Top

#97486 - 2003-01-07 12:26 AM Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)
Howard Bullock Howard Bullock KiX Supporter Registered: 2000-09-15 Posts: 5809 Loc: Harrisburg, PA USA	nope. _________________________ Home page: http://www.kixhelp.com/hb/
Top

#97487 - 2003-01-07 09:15 AM

Re: KiXGolf: Part 3 - And the winners are... (and alternate scoring method)

MightyR1 Offline

MM club member

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands

Winning code:

code:

function BWTDecode($s, $)
   dim $b,$c,$d
   for $c=1 to 255
      for $b=1 to len($s)
         if $c=asc(substr($s,$b))
            $d=$d+" "+$b
         endif
      next
   next
   $=$+1
   for $c=2 to $b
      $BWTDecode=$BWTDecode+substr($s,$,1)
      $=split($d)[$]
   next
endfunction

code:

KiXtart
KiXtart Version  = 4.12
KiXGolf Script   = kixgolf_bwt.kix

Computer
OS               = Windows 2000 Professional
CPU              = Intel Pentium III
Speed            = 730 MHz
Memory           = 382 MB

KiXGolf Scoring Engine
Scoring Engine   = 3.0.3

KiXtart Golf Score
Tournament       = KiXtart Golf: Burrows-Wheeler Transform
Date & Time      = 2003/01/07 09:16:46
KiXGolf Result   = passed
KiXGolf Score    = 191
 
Extended KiXtart Golf Statistics
Number of Repetitions          = 10
Start Time                     = 2003/01/07 09:14:41.152
Stop Time                      = 2003/01/07 09:16:45.884
Running Time                   = 0000/00/00 00:02:04.732
KernelModeTime [ms]            = 00:00:00.015
Avg. KernelModeTime [ms]       = 00:00:00.001
UserModeTime [ms]              = 00:02:01.671
Avg. UserModeTime [ms]         = 00:00:12.167
Execution Time [ms]            = 00:02:01.687
Avg. Execution Time [ms]       = 00:00:12.168
delta HandleCount              = 5
delta ThreadCount              = 1
delta PeakWorkingSetSize [kB]  = 0
delta WorkingSetSize [kB]      = 204
KiXGolf Score                  = 191
KiXGolf Weighting              = 0.5
Running Time Score [s]         = 12.168
Running Time Weighting         = 0.25
Memory Score [kB]              = 204
Memory Weigthing               = 0.25
Extended KiXGolf Score         = 149.542
 
Thank you for participating in KiXtart Golf!

Strange... Running this at home gives me an extended Golf score of 138.??? (WinXP, PII 400Mhz, 192 MB)

_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top

Page 1 of 1

Previous Topic View All Topics

Index Next Topic

Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart

Hop to:

Shout Box

Search the board with:
superb Board Search
or try with google:

	Web kixtart.org