Sealeopard
(KiX Master)
2003-03-08 09:40 PM
KiXtart Golf: CD Sorter

Rule Change: Due to some discussion during the tournament the second constraint has been changed. You no longer need to 'minimize' the gap. It is sufficient if the gap is less than 1 minute All documentation has been updated accordingly and the KIXGOLF_CD.ZIP package also reflects this rule change. My apologies.

It's time for another round of KiXGolf!

Todays course will delight all the avid music-listeners under the KiXGolfers as we create custom CDs with your favorite songs. I will also tell you how to turn KiXtart into a CD Burner!. Okay, the last sentence is wrong. [Big Grin]

However, I think you'll find a nice challenge ahead.

Please download the complete KiXGolf "CD Sorter" package at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

This package contains all the files required to run play KiXGolf, including the datasets and scoring engine. Please use the RESULTS.TXT file, that is generated after running the KiXGolf script to post your scores. This will guarantee that you post vaild scores and provide some helpful info to your competitors.

I have one hint for you guys: Whoever has ever heard about the famous gambling state at the Mediterranean knows how to play the KiXGolf course. [Big Grin]

=============
The Challenge
=============

You work for a large record company that markets a line of greatest hits compact discs --- "Super Funk of the 70s", "Partridge Family Unlimited", "3 Tenors in Antarctica, Again!". For each CD, you have a list of possible songs, their lengths, and the CD's maximum length.

You would like each CD to be as close to full as possible, but you have a large catalog of songs to fill, in anticipation of an 80's revival. It's okay to leave a bit of empty space on each CD to get the job done quickly. You have decided to use KiXtart to determine the set of songs for each CD.

Thanks to the folks at The Mathworks who created the original BINPACK challenge on which this KiXGolf challenge is based on.

Download the complete KiXGolf "CD Sorter" package at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

=============
Specification
=============


You will be provided with a list, in comma-delimited string form, of song times, and the length of a CD. Not all the songs will fit on the CD. Your job is to return a single string of comma-delimited indices into that list of the songs you have chosen for this CD.

The sum of the song times that you select should not be greater than the provided media length. You need not use all of the provided songs; there may be more songs than you have space for on a single CD. There were a lot of great disco songs, but you only want to produce a single disco CD. However, you can only use each song once per CD.

In KiXtart syntax, the function header should look like this:
code:
function CD_Sorter(songList, mediaLength) 
endfunction

More precisely, given a comma-delimited list of arbitrary indices, songList, find an array of indices, indexList, such that

  • sum(songList(indexList)) <= mediaLength, with mediaLength=45 minutes and
  • gap = (mediaLength - sum(songList(indexList))) <1 minute.
========
Example
=======
If songList = '10.2,30,14,20.8', with a target time of mediaLength = 45, then a good solution is to pick the elements 30 and 14, since 30 + 14 = 44, which is very close to 45. Therefore, indexList = '2,3', since songList(indexList) = '30,14' and sum(songList(indexList)) = 44, leaving a gap of 1 minute on the CD. Not bad, however, the constraints call for a gap of less than 1 minute. The optimal solution indexList = '1,3,4' leaves a gap of 0.
Remember, that the songs are numbered starting at 1, there is no song 0! Song 1 has length 10.2, Song 2 has length 30, and so on.

=======
Scoring
=======

The optimim media lengths for all CDs have already been calculated. Your results will be compared to this optimized set of CDs to determine how good your algorithm is. You might also be able to develop an algorithm that features an even better optimization.

=============
General rules
=============


  • The program must be written as one or more lines.
  • The program is expected to finish in a reasonable time, e.g. if it gets started when the challenge opens, it's expected to be finished by the time the challenge closes even on a somewhat slow computer. The program has to be valid during the period that the challenge runs.
  • You can submit scores as often as you want to until the deadline, no reason to wait until the last minute. In fact, other people want to see the score to beat. So don't be a spoilsport by hoarding your score. Submit early and often.
  • The program may only use the KiXtart commands/functions/macros, no other code fragments are allowed.
  • The program should be self-contained (except for any I/O mentioned in the challenge). In particular, you may not do things like fetching extra data from a remote site.
  • You may assume ASCII as character set.
  • You are allowed to use additional UDF. However, these UDFs must be included in the KIXGOLF_CD.UDF and will be counted towards your KiXGolf score.
When posting KiXtart Golf Scores, please include the KIXGOLF_CD.TXT file that is created in the script directory. It contains some basic information about the computer that the script is run on.
========
Deadline
========
The game starts March 8, 2003 (3:00pm EST) and ends March 23, 2003 (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 first optimizes all CDs!

================================================================
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 $b=0 to ubound($a)
if $a[$b]>0
$c=$c+1
endif
next

for a score of 45.

Another solution is:
code:
DO
$b=$b+1
if $a[$b]>0
$c=$c+1
endif
UNTIL $b>(UBOUND($a)+1)

for a score of 53.

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)

Here's the KiXGolf code used to score the challange. however, you will need the complete package from http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

code:
; KiXtart Golf
;
; CD Sorter
;

dim $sGolfScoreUDF, $bGolfScore, $sKiXGolfUDF, $sCDSorterData
dim $sTitle, $iRC, $iLoops, $sKiXGolfScrEngVer, $iLoop
dim $asCDs, $iNumCDs, $iCDNum, $iMediaLength, $iRandomCD
dim $dCDLength, $sIndices, $asCDLengths, $sIndex, $bFail
dim $sOutput, $iKixGolfScore, $sResult, $sOutputFile, $dAvgGap, $dAvgMediaLength
dim $sCDResultsData, $sResults, $dOptimumCDLength, $iNumOptCDs, $iNumValidCDs

; set required options
$sTitle='KiXtart Golf: CD Sorter'
$iRC=SETTITLE($sTitle)
$iRC=SETOPTION('Explicit','on')
$iRC=SETOPTION('NoVarsInStrings','on')
$iRC=SETOPTION('WrapAtEOL','on')
$iRC=SETOPTION('CaseSensitivity','on')

cls

; load UDFs
$sKiXGolfUDF=@scriptdir+'\'+left(@scriptname,instrrev(@SCRIPTNAME,'.'))+'udf'
if exist($sKiXGolfUDF)
call $sKiXGolfUDF
else
$iRC=messagebox('Cannot find KiXGolf UDF '+$sKiXGolfUDF,'Cannot find file!',16)
exit 2
endif
$sGolfScoreUDF=@scriptdir+'\'+'kixgolf3.udf'
if exist($sGolfScoreUDF)
call $sGolfScoreUDF
$bGolfScore=1
else
$bGolfScore=0
endif
$sKiXGolfScrEngVer = '3.0.3'

; number of times the challenge will be executed
; in order to post your results, you must run it 100 times
; however, for testing purposes you can choose to set this to 1
$iLoops=100

; lenght of the provided CD media
$iMediaLength=45

; boolean to run the test just once for a randomly choosen CD
; in order to post your results, all CDs must be processed
$iRandomCD=1
$iRC=srnd(@TICKS)

; read a couple of test arrays from a .INI file
; each list of song lengths starts with song 1
$sCDSorterData=@scriptdir+'\'+left(@scriptname,instrrev(@SCRIPTNAME,'.'))+'ini'
$asCDs=split(readprofilestring($sCDSorterData,'',''),chr(10))
$iNumCDs=ubound($asCDs)
dim $asCDTitles[$iNumCDs-1], $asCDSongLenghts[$iNumCDs-1]
dim $asIndices[$iNumCDs-1], $adCDLength[$iNumCDs-1], $adCDGap[$iNumCDs-1], $asCDResults[$iNumCDs-1]
for $iCDNum=1 to $iNumCDs
$asCDTitles[$iCDNum-1]=readprofilestring($sCDSorterData,$asCDs[$iCDNum-1],'Title')
$asCDSongLenghts[$iCDNum-1]=readprofilestring($sCDSorterData,$asCDs[$iCDNum-1],'Songs')
next

; set pre-calculated results to be beaten
$sCDResultsData=@scriptdir+'\kixgolf_cd_results.ini'
for $iCDNum=1 to $iNumCDs
$asCDResults[$iCDNum-1]=readprofilestring($sCDResultsData,$asCDs[$iCDNum-1],'Songs')
next

; this is the main loop that calls the CDSorter UDF and computes the indices for the songlists
for $iLoop=1 to $iLoops
if $iRandomCD
$iCDNum=rnd($iNumCDs-1)
$asIndices[$iCDNum]=CDSorter($asCDSongLenghts[$iCDNum],$iMediaLength)
else
for $iCDNum=1 to $iNumCDs
$asIndices[$iCDNum-1]=CDSorter($asCDSongLenghts[$iCDNum-1],$iMediaLength)
next
endif
next
; this is the end of main loop that calls the CDSorter UDF and computes the indices for the songlists

; now we calculate the media length for each CD and the remaining gap
; we also compare the results to pre-calculated optimum results
; however, the algorithm might beat the optimum results
$dAvgMediaLength=0.0
$dAvgGap=0.0
$iNumOptCDs=0
$iNumValidCDs=0
for $iCDNum=1 to $iNumCDs
$bFail=0
$dCDLength=0.0
$dOptimumCDLength=0.0

if $asIndices[$iCDNum-1]
$sIndices=split($asIndices[$iCDNum-1],',')
$asCDLengths=split($asCDSongLenghts[$iCDNum-1],',')
for each $sIndex in $sIndices
$dCDLength=$dCDLength+cdbl($asCDLengths[val($sIndex)-1])
next
endif
$adCDLength[$iCDNum-1]=$dCDLength
$dAvgMediaLength=$dAvgMediaLength+$adCDLength[$iCDNum-1]
$adCDGap[$iCDNum-1]=cdbl($iMediaLength)-$dCDLength
$dAvgGap=$dAvgGap+$adCDGap[$iCDNum-1]

; now display the results for all CDs
$sOutput=$sOutput+@CRLF+'CD #'+$iCDNum
$sOutput=$sOutput+@CRLF+'Title = '+$asCDTitles[$iCDNum-1]
$sOutput=$sOutput+@CRLF+'Song #s = '+$asIndices[$iCDNum-1]
$sOutput=$sOutput+@CRLF+'CD Length = '+formatnumber($adCDLength[$iCDNum-1],2)
$sOutput=$sOutput+@CRLF+'CD Gap = '+formatnumber($adCDGap[$iCDNum-1],2)
$sOutput=$sOutput+@CRLF+'CD Gap [%] = '+formatnumber(($adCDGap[$iCDNum-1]/$iMediaLength)*100,2)

; compare to pre-calculated optimum results
$sResults=split($asCDResults[$iCDNum-1],',')
$asCDLengths=split($asCDSongLenghts[$iCDNum-1],',')
for each $sResult in $sResults
$dOptimumCDLength=$dOptimumCDLength+cdbl($asCDLengths[val($sResult)-1])
next
$sOutput=$sOutput+@CRLF+'Optimum CD Length = '+formatnumber($dOptimumCDLength,2)
select
case $adCDLength[$iCDNum-1]<$dOptimumCDLength
$sOutput=$sOutput+@CRLF+'CD can be further optimized by '
$sOutput=$sOutput+formatnumber((1.0-($adCDLength[$iCDNum-1]/$dOptimumCDLength))*100,2)+'%'
case $adCDLength[$iCDNum-1]<=$iMediaLength
$sOutput=$sOutput+@CRLF+'CD has been fully optimized'
$iNumOptCDs=$iNumOptCDs+1
endselect

; check validity
select
case $adCDLength[$iCDNum-1]=0
$sOutput=$sOutput+@CRLF+'CD is empty'
$bFail=1
case $adCDLength[$iCDNum-1]>$iMediaLength
$sOutput=$sOutput+@CRLF+'CD exceeds maximum length of '+$iMediaLength
$bFail=1
endselect
$sIndices=split($asIndices[$iCDNum-1],',')
for each $sIndex in $sIndices
if ascan($sIndices,$sIndex)<ubound($sIndices)
if ascan($sIndices,$sIndex,ascan($sIndices,$sIndex)+1)=-1
else
$sOutput=$sOutput+@CRLF+'A song is being used at least twice on this CD'
$bFail=1
endif
endif
next

if not $bFail
$sOutput=$sOutput+@CRLF+'A valid CD has been created'
$iNumValidCDs=$iNumValidCDs+1
endif
$sOutput=$sOutput+@CRLF+''
next
select
case $iNumOptCDs=$iNumCDs
$sResult='Perfect CD Sorter'
case $iNumValidCDs=$iNumCDs
$sResult='Valid CD Sorter (Room For Improvement)'
case 1
$sResult='Invalid CD Sorter'
endselect

; display the average media length and the average gap
$dAvgMediaLength=$dAvgMediaLength/$iNumCDs
$dAvgGap=$dAvgGap/$iNumCDs
$sOutput=$sOutput+@CRLF+'Average CD Length = '+formatnumber($dAvgMediaLength,2)
$sOutput=$sOutput+@CRLF+'Average Gap = '+formatnumber($dAvgGap,2)
$sOutput=$sOutput+@CRLF+'Average Gap [%] = '+formatnumber(($dAvgGap/$iMediaLength)*100,2)

; generate KiXtart Golf Score
if $bGolfScore
$iKiXGolfScore=KixGolf($sKiXGolfUDF)
else
$iKiXGolfScore='Please download the KiXtart Golf package at '
$iKixGolfScore=$iKixGolfScore+'http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip'
endif

; generating official KiXGolf Score
$sOutput=$sOutput+@CRLF+'KiXtart'
$sOutput=$sOutput+@CRLF+'KiXtart Version = '+@KIX
$sOutput=$sOutput+@CRLF+'KiXGolf Script = '+@SCRIPTNAME
$sOutput=$sOutput+@CRLF+''
$sOutput=$sOutput+@CRLF+'Computer'
$sOutput=$sOutput+@CRLF+'OS = '+@PRODUCTTYPE
$sOutput=$sOutput+@CRLF+'CPU = '+@CPU
$sOutput=$sOutput+@CRLF+'Speed = '+@MHZ+' MHz'
$sOutput=$sOutput+@CRLF+'Memory = '+MEMORYSIZE()+' MB'
$sOutput=$sOutput+@CRLF+''
$sOutput=$sOutput+@CRLF+'KiXGolf Scoring Engine'
$sOutput=$sOutput+@CRLF+'Scoring Engine = '+$sKiXGolfScrEngVer
$sOutput=$sOutput+@CRLF+''
$sOutput=$sOutput+@CRLF+'KiXtart Golf Score'
$sOutput=$sOutput+@CRLF+'Tournament = '+$sTitle
$sOutput=$sOutput+@CRLF+'Date & Time = '+@DATE+' '+@TIME
$sOutput=$sOutput+@CRLF+'# Loops = '+$iLoops
$sOutput=$sOutput+@CRLF+'# Processed CDs = '+$iNumCDs
$sOutput=$sOutput+@CRLF+'# Valid CDs = '+$iNumValidCDs
$sOutput=$sOutput+@CRLF+'# Optimized CDs = '+$iNumOptCDs
$sOutput=$sOutput+@CRLF+'KiXGolf Result = '+$sResult
$sOutput=$sOutput+@CRLF+'KiXGolf Score = '+$iKiXGolfScore
$sOutput=$sOutput+@CRLF+' '
$sOutput=$sOutput+@CRLF+'Thank you for participating in KiXtart Golf!'

; saving and displaying official KiXtart Golf Score
$sOutputFile=@scriptdir+'\'+left(@scriptname,instrrev(@scriptname,'.'))+'txt'
$iRC=redirectoutput($sOutputFile,1)
? '
code:
'+$sOutput+@CRLF+'

'
$iRC=redirectoutput('')
? $sOutput

exit 0

; any modifications below this line will result in immediate disqualification



[ 13. March 2003, 00:24: Message edited by: sealeopard ]


MightyR1
(MM club member)
2003-03-08 10:27 PM
Re: KiXtart Golf: CD Sorter

Looks nice...

One day too early???

{edit - ignore second line, was confused by title in Announcement: New KiXGolf on 3-9-03 }

[ 08. March 2003, 22:31: Message edited by: MightyR1 ]


Sealeopard
(KiX Master)
2003-03-08 10:55 PM
Re: KiXtart Golf: CD Sorter

Oops, that must have been a typo. I meant the Saturday. I usually start the tournaments on Saturdays. I'm going to correct this.

[ 12. March 2003, 22:59: Message edited by: sealeopard ]


MightyR1
(MM club member)
2003-03-08 10:57 PM
Re: KiXtart Golf: CD Sorter

Me Oops too...

the post actually tells it's on saturday [Big Grin]


Sealeopard
(KiX Master)
2003-03-09 12:40 AM
Re: KiXtart Golf: CD Sorter

Corrected a bug in the script. Running just one randomly chosen CD would't have worked, this has bene corrected. ZIP package has been updated and can be downloaded at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

MightyR1
(MM club member)
2003-03-09 08:35 PM
Re: KiXtart Golf: CD Sorter

Jens,

How can I accomplish running just 1 CD??

code:
; boolean to run the test just once for a randomly choosen CD
; in order to post your results, all CDs must be processed
$iRandomCD=1
$iRC=SRND(@TICKS)

If I try this, I get an error in line 75:
code:
ERROR : array reference out of bounds!
Script: D:\KiX\kixgolf_cd\kixgolf_cd.kix
Line : 75



Sealeopard
(KiX Master)
2003-03-09 08:45 PM
Re: KiXtart Golf: CD Sorter

Patrick:

Sorry for that. Please see the correct lines 74-75 for the main loop below. I have also uploaded a corrected ZIP package under http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

code:
    $iCDNum=rnd($iNumCDs-1)
$asIndices[$iCDNum]=CDSorter($asCDSongLenghts[$iCDNum],$iMediaLength)



MightyR1
(MM club member)
2003-03-09 08:58 PM
Re: KiXtart Golf: CD Sorter

Sorry Jens, still no go...

if I make $iLoops=1 and $iRandomCD=1 I get this (do not count this as a score!!!):

code:
KiXtart
KiXtart Version = 4.20 Beta 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 696 MHz
Memory = 127 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Date & Time = 2003/03/09 21:01:59
# Loops = 1
# Processed CDs = 12
# Valid CDs = 0
# Optimized CDs = 0
KiXGolf Result = Invalid CD Sorter
KiXGolf Score = 46

Thank you for participating in KiXtart Golf!



Sealeopard
(KiX Master)
2003-03-10 12:20 AM
Re: KiXtart Golf: CD Sorter

That is actually the default result for the empty CD Sorter UDF as it returns an empty string.

The reason why the checking algorithm says it processed 12 CDs even though you run only one CD though the sorter UDF is that all CDs are checked for valid lists of indices. If you wish, I can update the code that if you run only one CD through the CD sorter, that only that one CD is checked for validity.

I have updated the code and all console output is now also included in the RESULTS.TXT file. You will see the results for each of the CDs separately in addition to the aggregate results.

Do you already have an idea how to solve it?

[ 10. March 2003, 00:25: Message edited by: sealeopard ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 08:48 AM
Re: KiXtart Golf: CD Sorter

are all songtimes assumed to be given in floating point form or do we need to translate them?

MightyR1
(MM club member)
2003-03-10 09:53 AM
Re: KiXtart Golf: CD Sorter

Will take a look at the new code.

And Yes, got an idea... Want to check every possible solution (will take long time on CD12 I know). Not just a guess like your "hint" says...


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 11:44 AM
Re: KiXtart Golf: CD Sorter

so, don't want to scan the entries...

jens, do you have a list of songs times where multiple songs have exactly same time?


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 02:11 PM
Re: KiXtart Golf: CD Sorter

jens did real killer for us.
freaking [Mad]

it takes zillion minutes to execute...


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 02:53 PM
Re: KiXtart Golf: CD Sorter

yeah, with only 9 songs, one list takes to scan without any calculations over an hour!

I give up.


MightyR1
(MM club member)
2003-03-10 02:55 PM
Re: KiXtart Golf: CD Sorter

Don't give up...

Take a look at Jens' Hint.

Jens may I say what gambling area you're referring too???


Sealeopard
(KiX Master)
2003-03-10 03:38 PM
Re: KiXtart Golf: CD Sorter

Re: Hint
I'm referring to that gambling area that is also a popular spot for e.g. artists, royalties, non-tax-payers, and people we sometimes want to be.

Re: Hint (again)
Yes, potential solutions to the hint I provided can be posted, though this might lead to the resurfacing of unwanted memories of long time past when you were back in high-school or college [Big Grin]

As usual, I do not take any responsibility with the effects of participating in KiXGolf.

Re: Songtimes
All song times are floating point numbers with four digits of precision. However, you can use any numbering type internally as only the song numbers are required as output. For example, multiplying each song length by 10000 (and the media length of 45, too) will result in all integer numbers. However, whether that provides any advantage over using floats remains to be seen [Wink] Might cut down on keystrokes, though, as you don't need to convert things to floats.


Sealeopard
(KiX Master)
2003-03-10 04:25 PM
Re: KiXtart Golf: CD Sorter

Jooel: Can you elaborate on
quote:
one list takes to scan without any calculations
What do you mean with scan? What is it scanning that takes an hour?


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 07:35 PM
Re: KiXtart Golf: CD Sorter

jens, I wont tell [Razz]

anyway, even though my alghorithm is pretty slow I'm almost there... just some trouble with floating point units and to be able to post my results, I need to install some software on my firewall (the machine I write on now)...


Sealeopard
(KiX Master)
2003-03-10 07:53 PM
Re: KiXtart Golf: CD Sorter

Joeel has brought to my attention a potential problem with the datasets. The datasets are comma-delimited floating point numbers of the songlengths. This means that e.g. 1.2345 (1 2345/1000 seconds) in the American English localization is 1,2345 in most European localizations.

MightyR1
(MM club member)
2003-03-10 08:33 PM
Re: KiXtart Golf: CD Sorter

Not perfect... Optimization needed...

code:
Average CD Length = 37.35
Average Gap = 7.65
Average Gap [%] = 17.00
KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 696 MHz
Memory = 127 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Date & Time = 2003/03/10 20:37:35
# Loops = 100
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 0
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 416

Thank you for participating in KiXtart Golf!



LonkeroAdministrator
(KiX Master Guru)
2003-03-10 08:38 PM
Re: KiXtart Golf: CD Sorter

you bastard!

damn, I made myself a quicker engine and realized that it skipped a lot of stuff.

jens, I think we could include the execution time in the engine to compare...


Sealeopard
(KiX Master)
2003-03-10 08:43 PM
Re: KiXtart Golf: CD Sorter

Execution time varies based on hardware used and also the specific algorithm. There are three distinct algorithms that can be used to solve this particular problem. One can use each of the algorithms by itself or combine them to achieve greater accuracy.

Anyway, I'll make a modification to the scoring screen to include both the start and stop time of the runs instead of just date/time. However, take those times with a grain of salt. I will post an updated package later today once I'm back home as I have all the material at home.

Finally, though Patrick posted the first working version, the algorithm can still be improved. I'm waiting for the person to completely optimize all CDs [Big Grin]

[ 10. March 2003, 20:56: Message edited by: sealeopard ]


MightyR1
(MM club member)
2003-03-10 08:49 PM
Re: KiXtart Golf: CD Sorter

Mine wasn't a real algorithm...

Since much of improvement, I'm going for 'Perfect CD Sorter'...


Sealeopard
(KiX Master)
2003-03-10 08:57 PM
Re: KiXtart Golf: CD Sorter

Patrick:

A) Your routine worked!
B) You beat Joeel!

What else can you ask for? [Smile]


MightyR1
(MM club member)
2003-03-10 08:58 PM
Re: KiXtart Golf: CD Sorter

2b "perfect"

LonkeroAdministrator
(KiX Master Guru)
2003-03-10 09:30 PM
Re: KiXtart Golf: CD Sorter

me goes for routing soft so can really test (don't have the real package here...)

LonkeroAdministrator
(KiX Master Guru)
2003-03-10 09:48 PM
Re: KiXtart Golf: CD Sorter

damn, have to get this box masquarate...

LonkeroAdministrator
(KiX Master Guru)
2003-03-10 10:34 PM
Re: KiXtart Golf: CD Sorter

eh, uuh...
can't realize what is wrong...
it just says incorrect UDF... or something.

how should the output be?


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 10:37 PM
Re: KiXtart Golf: CD Sorter

k,sorry for my stupidity.
forgot that jens does not like arrays...


Sealeopard
(KiX Master)
2003-03-10 10:37 PM
Re: KiXtart Golf: CD Sorter

Did you download the ZIP Package? That one contains a ready-to-run script and UDF. The UDF output, as specified in the README, is a comma-delimited string of the song numbers, e.g. '1,2,3' if your are using songs 1, 2, and 3 of a particular CD.

LonkeroAdministrator
(KiX Master Guru)
2003-03-10 10:42 PM
Re: KiXtart Golf: CD Sorter

yeah...

I'm just running the script.
about 6mins and still counting...

some output from the main script could be nice...


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 11:23 PM
Re: KiXtart Golf: CD Sorter

ehe...
46mins of processor time...
highest mem usage this far noticed 70M!

good golf!


MightyR1
(MM club member)
2003-03-10 11:31 PM
Re: KiXtart Golf: CD Sorter

[Frown] Bummer, "FIX" is integer based...

LonkeroAdministrator
(KiX Master Guru)
2003-03-10 11:34 PM
Re: KiXtart Golf: CD Sorter

what fix?

MightyR1
(MM club member)
2003-03-10 11:36 PM
Re: KiXtart Golf: CD Sorter

Fix( )

Action: Removes the fractional part of a number and returns the resulting integer value.

Syntax: Fix (expression)

Parameters: Expression

Any valid numeric expression.

Returns: Variant of subtype Integer.

Remarks: If the number is negative, Fix( ) returns the first negative integer greater than or equal to the number. For example, Fix( ) converts -6.3 to -6.

See Also: Abs( ), Int( )

Example:


LonkeroAdministrator
(KiX Master Guru)
2003-03-10 11:42 PM
Re: KiXtart Golf: CD Sorter

oh...
damn, if I would have known that the run time of the script is this long, I would have done some improving of the code before executing it...

already been running about 1,5hours...
think I'll go to bed and post the result once it finishes... hopefully tomorrow.


MightyR1
(MM club member)
2003-03-11 09:25 AM
Re: KiXtart Golf: CD Sorter

Going for "Perfect" really eats up my servers CPU [Wink]

First CD took about 10 mins with a total cd time of 44.9999

Talking about optimization...


Richard H.Administrator
(KiX Supporter)
2003-03-11 10:05 AM
Re: KiXtart Golf: CD Sorter

Is there any reason that the sort is called 100 times?

Is it to deter brute force solutions?


MightyR1
(MM club member)
2003-03-11 10:07 AM
Re: KiXtart Golf: CD Sorter

I think so... Bummer [Frown]

Richard H.Administrator
(KiX Supporter)
2003-03-11 10:14 AM
Re: KiXtart Golf: CD Sorter

Yeah bummer indeed.

I was expecting the script to have finished this morning based on the time it took to resolve CD 1, and was surprised that it wasn't. Then I spotted the 100 iterations.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:30 AM
Re: KiXtart Golf: CD Sorter

same here richard.
well, I go out and will see if it's done by evening.

if not, I'll come back tomorrow...


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:32 AM
Re: KiXtart Golf: CD Sorter

ah btw.
jens, as your script already opens the console on wkix32.exe without printing anything.

damn, there should be something coming out saying how many times it has ran and how many times more to come.


Richard H.Administrator
(KiX Supporter)
2003-03-12 12:37 AM
Re: KiXtart Golf: CD Sorter

I got fed up with the blank screen so I stopped it and added some diagnostic messages to the main script.

So far I've got this:
code:
Loop #1 @ 09:29:59
CD #1 @ 09:29:59
CD #2 @ 09:31:37
CD #3 @ 09:31:39
CD #4 @ 09:31:43
CD #5 @ 09:31:46

It is now 11:42 local time, so CD#5 has taken 2 over 2 hours and hasn't finished wherase the rest of them took no more than a few minutes.
Hmmm. very odd. Best have another look at that code...


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:41 AM
Re: KiXtart Golf: CD Sorter

well, there is some cd that is a lot longer than the others.

jens, I got my loops to 5.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:52 AM
Re: KiXtart Golf: CD Sorter

woah!
what is this:
quote:

; number of times the challenge will be executed
; in order to post your results, you must run it 100 times

what is the use in this and w00t!
wicked.

if ones script runs the whole week, he has no change to improve his code while it takes all reserves from the machine...

re checked your code...
it could indeed be less than 100 without harming anybody...


Richard H.Administrator
(KiX Supporter)
2003-03-11 02:39 PM
Re: KiXtart Golf: CD Sorter

Urk!?

I think I've found part of the problem that CD#5 is taking so long. From a debug message:
quote:
Disk #5 Iteration #4 GAP=1.52655665885959E-015 LIST=....
Now, I've got a line which should exit the routine when the gap is less than 0.0001, but this very small value doesn't seem to trigger it.

Hmmm.


LonkeroAdministrator
(KiX Master Guru)
2003-03-11 03:26 PM
Re: KiXtart Golf: CD Sorter

richard...
lol.

yeah, you can do it work faster, but isn't this golf?
golf thus far has been about as little strokes as possible, not as quick as possible.

jens, are the goals changed?

I made the script run just once and my code had run about 2 hours when I left home.

and I'm sure, I can't return results before the private coding phase is over.
even though the code works, it's results can't be announced as it takes more than just one week to run the check script!


Richard H.Administrator
(KiX Supporter)
2003-03-11 03:47 PM
Re: KiXtart Golf: CD Sorter

The reason for the extra code to reduce the run time is that I have exactly the same problem you have. It will take too long to run at the moment.

Once I am happy that the solutions are correct I can remove the time saving code to save bytes and get a better golf score, but until then I need to leave it in.


Sealeopard
(KiX Master)
2003-03-11 04:04 PM
Re: KiXtart Golf: CD Sorter

I have posted an updated KiXGolf package at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

The change is that it now saves the results for each CD to both the screen and the results file. An example results file is part of the package. I also added some calculations that will display the time the script needed to run. I willnot show the start date/time, the end date/time and the duration as part of the scoring part.

The goal of the KiXGolf tournament has not changed. It is still about optimizing for least keystrokes.

The only reason I put the 'loop 100 times' into the code is to deter the use of a brute-force approach. Though the 'brute-force approach' is defimitely a valid one, I don't see it as a challenge to just create a couple of FOR loops. be creative!

I already gave one hint for a potentially powerful algorithm for this type of problem. If eerybody wished, I could spell out the method(s) that could be used. However, you would still have to code it.

So far, I've already seen one solution posted which fulfills the requirements, namely it produced a list of song indices for each CD with each CD having a total length of <45 and it did finish in time. And Patrick did't even use the fastest computer for this [Wink]

I would also recommend to run your tests with just one loop and/or just one CD.

[ 11. March 2003, 16:12: Message edited by: sealeopard ]


MightyR1
(MM club member)
2003-03-11 04:48 PM
Re: KiXtart Golf: CD Sorter

Jens,

Brute force will search for "Perfect"... Really nice to get the best score out of 1,267,650,600,228,229,401,496,703,205,376 possible solutions (CD12)

I know which algorithm type your talking about, but can't determine the three methods of approach you mean.

Others,

Does anyone else have a clue what Jens is talking about???


LonkeroAdministrator
(KiX Master Guru)
2003-03-11 04:48 PM
Re: KiXtart Golf: CD Sorter

jens, I did your recommendation but as you have so many songs, the calc takes still time.
the increase in time is awesome as say 5 songs calc in 3-4 seconds.
6 songs takes already a approx minute.

what comes to having a sorter with less than the media total.
sure, I had such sorter and the code was sorter than current.

also it's execution time was damn fast.

but I think we have to disagree still with the goals.

you accept code that does somewhat correct thing.
I see patricks code as unacceptable as it does not calc the perfect values and as such is not acceptable.

sure, I could do for each cd to include only 1 song and with your current ruling, that would also be acceptable [Mad]

some rules would be good.


MightyR1
(MM club member)
2003-03-11 04:51 PM
Re: KiXtart Golf: CD Sorter

Agreed, Am going for perfect too. Will use one loop though...

Richard H.Administrator
(KiX Supporter)
2003-03-11 04:59 PM
Re: KiXtart Golf: CD Sorter

quote:
Others,

Does anyone else have a clue what Jens is talking about???

Nope, haven't got a clue.

Two nations separated by a common language [Confused]


Sealeopard
(KiX Master)
2003-03-11 05:10 PM
Re: KiXtart Golf: CD Sorter

There are three (as I know of) methods to solve this problem:
1) Brute-force
2) Limited search
3) Monte-Carlo Method
or a combination of the above.

Limited Search:
A limited search would start with one song (e.g. the longest one), then choose a second one. If the second one fits, you choose a third one, and so on...

Monte-Carlo Method:
This method create random permutations of songlists. It then checks each songlist whether it is below the length limit and chooses the best fit.

A combination would be to e.g. first do a Monte-Carlo, then search the leftover songs for a potential better fit of one of the already used songs.

One thing that couldbe used is a sorted list of entries.

[ 11. March 2003, 17:50: Message edited by: sealeopard ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-11 05:15 PM
Re: KiXtart Golf: CD Sorter

dunno.
my monte-carlo takes up hours for one cd and if I use limited it is fast but it indeed is not even close to perfect.

for using combined... mm, it could be little faster but also a lot longer.


Richard H.Administrator
(KiX Supporter)
2003-03-11 05:19 PM
Re: KiXtart Golf: CD Sorter

Ahh. Thanks for that.

I'm taking option one, but limiting it to one loop and a little recursion to make it all a little more aesthetically pleasing.

5 minutes for disks 1-8, but disk 9 is really pushing the envelope, it's taken 15 minutes to get the gap down to 0.000299999999987977.

Maybe I should set a higher limit for the gap - it might catch all the "perfect" solutions.


maciep
(Korg Regular)
2003-03-11 07:54 PM
Re: KiXtart Golf: CD Sorter

quote:

Average CD Length = 44.8012916666667
Average Gap = 0.198708333333334
Average Gap [%] = 0.441574074074075

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/11 13:43:41.815
Processing End = 2003/03/11 13:48:23.832
Duration = 0000/00/00 00:04:42.017
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 5
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 396

Thank you for participating in KiXtart Golf!

formatnumber() keeps bombing out on me, so I just got rid of all occurences. Anyway, need to get all cd's optimized now. Then I'll worry about my golf score.


Sealeopard
(KiX Master)
2003-03-11 08:13 PM
Re: KiXtart Golf: CD Sorter

[Eek!] [Eek!] Wow! [Eek!] [Eek!]

Five optimized CDs, not bad.


LonkeroAdministrator
(KiX Master Guru)
2003-03-11 08:25 PM
Re: KiXtart Golf: CD Sorter

heh.
added one small if statement and the execution time of all 100 loops was just one minute [Razz]

still, no optimized CDs.


LonkeroAdministrator
(KiX Master Guru)
2003-03-11 09:35 PM
Re: KiXtart Golf: CD Sorter

jens, I must admit that I got mad to you for thing not so big.

as we know, the full-scan of possibilities takes zillion hours time (like my UDF) there can be some reliefe.
either degrease the media time or song count or even loosen up the rules, like we have done now.

what is the time on cd to be accepted?
50% gap?


Sealeopard
(KiX Master)
2003-03-11 10:37 PM
Re: KiXtart Golf: CD Sorter

You got mad? Where? I didn't see anything [Big Grin]

Based on the task description, I would say that a lower gap takes precedence over a lower Golf score. Thus , a lower average gap win if the KiXGolf score is the same.

However, then we would move away from the KiXGolf idea of "less keystrokes is better".

Damn, I hate that I didn't seem to fully thought about this.


Jack Lothian
(MM club member)
2003-03-11 11:16 PM
Re: KiXtart Golf: CD Sorter

Jens,

This is the first chance I have had to read this. Are you demanding the optimal solution here or will any solution do?

If the optimal solution is desired then it seems to me that recasting the problem as a linear programming problem might be the best approach in terms of computational time efficiency but in terms of key strokes the brute force method would be the best approach & possibly only solution.

Your suggestion of using limited or monte-carlo searches suggests that non optimal solutions are permitted. Is this true? If so how are you balancing optimal against key stroke concerns?

I am sorry for leaping in several days into the contest but I am trying to understand what is happening & I am a bit confused.

[ 11. March 2003, 23:35: Message edited by: Jack Lothian ]


Sealeopard
(KiX Master)
2003-03-11 11:46 PM
Re: KiXtart Golf: CD Sorter

Jack:

I'm interested in the optimum CD fill with the least CD gap with the lowest KiXtart score. Granted, these conditions can be contradictory as you can lower your KiXGolf score by increasing the average gaps.

This also means that two approaches could result in different CD fills and different KiXGolf scores. In this case, the approach with the lower gap (as measured/displayed by the average gap) would win. If two approaches result in the same average gap, then the lower KiXGolf score wins.

This will actually only affect the outcome of the first part of the KiXGolf challenge. As the UDFs will be public for the second part you can still be able to further optimize somebody elses approach.

This way, we are still true to the goal of the KiXGolf Tournament, namely keep the keystrokes as low as possible.

BTW, the algorithm used to create the 'Gold Standard' for the optimized CDs is a combination of Monte-Carlo-Method and Limited Search. As far as I can tell this is actually the 'perfect' solution for the provided datasets.

The only constraint that I tried to create was the prohibition of the brute-force approach as I don't see that approach as programmatically challenging.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:03 AM
Re: KiXtart Golf: CD Sorter

back at here...
been doing some tests and still must wonder, why 100?
it already tests all the CDs...
why not 10 or 20?

it takes a lot of time to run 100 times...
or why not 1000?


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:13 AM
Re: KiXtart Golf: CD Sorter

w00t!

I ran your code jens [Mad]

it ran all the loops (100) and after that just crashed.
no data written to file.

why crashed, there is at the end a "get $sOutput" to catch the end window and it never gets there.
it never shows me any errors nor there is any kix error.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:30 AM
Re: KiXtart Golf: CD Sorter

damn
jens, aren't you american?
wonder why no reply...

does anyone have the older versions of kixgolf_cd test-suite?


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:38 AM
Re: KiXtart Golf: CD Sorter

update.
jens, I tested your code with 4.12, 4.20 and 4.21-rc1 and all of them quit "abnormally"

in english, there is no screen output, kix does not error etc etc.

so have you built in some sort of check if my syntax is better than yours, you skip it?


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 12:46 AM
Re: KiXtart Golf: CD Sorter

more to it.
if I add more songs (like add new dummy ",") at the end of list, your code will die with kixtart error array reference out of bounds.

if I then remove one element from the outcoming list, your script executes.
ofcourse then the cd's are not optimized.

so, PLEASE, could you check your code.

[edit]
even more, updated your files again and even downloaded kix32.exe to test from console.
full output is:
quote:

Running loop #1
Processing CD #1
Processing CD #2
Processing CD #3
Processing CD #4
Processing CD #5
Processing CD #6
Processing CD #7
Processing CD #8
Processing CD #9
Processing CD #10
Processing CD #11
Processing CD #12

C:\Documents and Settings\niemjo\Desktop\golf>

now, I keep on waiting until you fix it.
until that my current by myself validated code is 245 strokes.

[ 12. March 2003, 00:55: Message edited by: Lonkero ]


maciep
(Korg Regular)
2003-03-12 01:34 AM
Re: KiXtart Golf: CD Sorter

I had the same problem. I think it quit on this line.
code:
  
$sOutput=$sOutput+@CRLF+'CD Gap = '+formatnumber($adCDGap[$iCDNum-1],2)

It also quit on more lines farther down in the script if i commented that line out. Everytime line the script quit on was using the formatnumber() function.

I just removed all references to formatnumber(). For example, I changed the above line to

code:
  
$sOutput=$sOutput+@CRLF+'CD Gap = '+$adCDGap[$iCDNum-1]

That seems to have fixed it for me.


Sealeopard
(KiX Master)
2003-03-12 02:03 AM
Re: KiXtart Golf: CD Sorter

Okay, guys, I can reproduce the problem. I'll work on a fix. I haven't seen that before when I was using arbitry lists of indices to test the validation routine.

Sealeopard
(KiX Master)
2003-03-12 02:51 AM
Re: KiXtart Golf: CD Sorter

I think I've found the problem. It look to me like a bug in the FORMATNUMBER function that only surface if you try to format the number to x decimal places and this resulting number would result in being effectively '0'
See the code for an example
code:
$a=0.1
? 'a='+$a
? 'formatnumber(a)='+formatnumber($a,1)
$a=0.11
? 'a='+$a
? 'formatnumber(a)='+formatnumber($a,1)
$a=0.01
? 'a='+$a
? 'formatnumber(a)='+formatnumber($a,1)

I have already corrected the code and uploaded an updated KIXGOLF_CD.ZIP at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip

The buggy FORMATNUMBER() function has been replaced by a homegrown NumberFormat() UDF which should also correctly set either a '.' or ',' decimal indicator based on the users locale settings.

I will also post a report in the BETA forum as Ruud post about the already mentioned FORMATNUMBER() problem with '0' does not address this particular problem.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 04:55 AM
Re: KiXtart Golf: CD Sorter

now we are talking!

jens, don't remember to add that even though it's buggy it does not produce any error, it just crashes kix.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 05:14 AM
Re: KiXtart Golf: CD Sorter

k, thanks jens...
here is the results for the code I tried to approve yesterday:

quote:


CD #1
Title = 70's Super Funk
Song #s = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,17
CD Length = 44.99
CD Gap = 0.01
CD Gap [%] = 0.02
Opt. Length = 45.00
CD can be further optimized by 0.01%
A valid CD has been created

CD #2
Title = Partridge Family Unlimited
Song #s = 1,2,3,4,6,7,8,10
CD Length = 44.93
CD Gap = 0.07
CD Gap [%] = 0.16
Opt. Length = 44.94
CD can be further optimized by 0.02%
A valid CD has been created

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 1,2,3,4,5,6,7,9,10,14
CD Length = 44.81
CD Gap = 0.19
CD Gap [%] = 0.42
Opt. Length = 44.96
CD can be further optimized by 0.33%
A valid CD has been created

CD #4
Title = Support Your Local KiXGolfer
Song #s = 1,37
CD Length = 44.20
CD Gap = 0.80
CD Gap [%] = 1.78
Opt. Length = 44.70
CD can be further optimized by 1.12%
A valid CD has been created

CD #5
Title = ABBA Bubba!
Song #s = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,27
CD Length = 44.97
CD Gap = 0.03
CD Gap [%] = 0.06
Opt. Length = 44.96
CD has been fully optimized
A valid CD has been created

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 1,2,4,5,7,8
CD Length = 44.60
CD Gap = 0.40
CD Gap [%] = 0.89
Opt. Length = 44.50
CD has been fully optimized
A valid CD has been created

CD #7
Title = Moon Rocks!
Song #s = 1,2,3,4,5,6,7,9,10,12,13,14,16,17,27
CD Length = 44.99
CD Gap = 0.01
CD Gap [%] = 0.01
Opt. Length = 45.00
CD can be further optimized by 0.01%
A valid CD has been created

CD #8
Title = Ruud's Favs
Song #s = 1,2,3,4,5,6,7,8,9,10,11,12,13,14
CD Length = 42.29
CD Gap = 2.71
CD Gap [%] = 6.02
Opt. Length = 44.58
CD can be further optimized by 5.15%
A valid CD has been created

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,21,22,23,24,25,26,27,28,30,31,32,33,35,46
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD can be further optimized by 0%
A valid CD has been created

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 25
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 1,51,52,53,54
CD Length = 44.25
CD Gap = 0.75
CD Gap [%] = 1.67
Opt. Length = 44.25
CD can be further optimized by 0%
A valid CD has been created

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 1,2,3,4,5,6,7,8,9,88
CD Length = 44.99
CD Gap = 0.01
CD Gap [%] = 0.02
Opt. Length = 45.00
CD can be further optimized by 0.02%
A valid CD has been created

Average CD Length = 44.59
Average Gap = 0.41
Average Gap [%] = 0.92

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/12 06:02:11.312
Processing End = 2003/03/12 06:17:33.659
Duration = 0000/00/00 00:15:22.346
# Loops = 100
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 3
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 245

Thank you for participating in KiXtart Golf!



LonkeroAdministrator
(KiX Master Guru)
2003-03-12 05:54 AM
Re: KiXtart Golf: CD Sorter

jens, I still get array reference out of bounds.
kixgolf_cd.kix line 115.
last thing in console:
quote:

CD #2
Title = Partridge Family Unlimited
Song #s = 1,2,3,4,6,7,8,10
CD Length = 44.93
CD Gap = 0.07
CD Gap [%] = 0.16
Opt. Length = 44.94
CD can be further optimized by 0.02%
A valid CD has been created

that error comes due my test code that has added "0" song.
should it still crash?
could the console say something?

{edit}
also, what is this:
code:
CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 1,51,52,53,54
CD Length = 44.25
CD Gap = 0.75
CD Gap [%] = 1.67
Opt. Length = 44.25
CD can be further optimized by 0%
A valid CD has been created

eh?
how much is 0%?
should I read it that I should make my collection better than yours to be approved as optimized?

[ 12. March 2003, 07:29: Message edited by: Lonkero ]


Richard H.Administrator
(KiX Supporter)
2003-03-12 10:53 AM
Re: KiXtart Golf: CD Sorter

Nuts.

Ran to completion and then no output. Removed the formatnumber and restarted.

May not going to get an opportunity to optimise at this rate [Frown]


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 10:55 AM
Re: KiXtart Golf: CD Sorter

richard, do you still run with brute force?
I used that approach and it took t000 much time so made some cuts.

now one cd takes about 3-5 seconds at most.


Richard H.Administrator
(KiX Supporter)
2003-03-12 11:15 AM
Re: KiXtart Golf: CD Sorter

Yep, still using brute force with some speed up techniques.

If I pre-sort the arrays I can make massive improvements in speed, but with a huge overhead in code.

If I convert to integer I can probably make similar improvements, again with code overhead.

At the moment I just want it to run to completion so I can check that the algorithm is OK before optimising.

Run times aren't too bad. Latest run (still active) is:
code:
Loop #1 started @ 09:00:28
CD #1 @ 09:00:28
CD #2 @ 09:02:18
CD #3 @ 09:02:20
CD #4 @ 09:02:25
CD #5 @ 09:02:34
CD #6 @ 09:02:37
CD #7 @ 09:02:37
CD #8 @ 09:02:44
CD #9 @ 09:05:32
CD #10 @ 10:07:56
CD #11 @ 10:08:01

CD#9 is the hardest so far at just over the hour.

I think I may be having rounding problems with the floating point which are causing some comparison problems. For instance, one of my checks halts processing down a tree when the gap become negative (too many tracks).

This is a problem when the values get buggered up internally, so instead of "1" you have "0.99999976234". Substract "1" from it and you will get a negative value which will cause the sequence to be deemed invalid.

Maybe I will have to switch to integer sooner rather than later...


Richard H.Administrator
(KiX Supporter)
2003-03-12 11:35 AM
Re: KiXtart Golf: CD Sorter

Completed and the mainn script crashed.

Will d/l the latest package and try again


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 11:48 AM
Re: KiXtart Golf: CD Sorter

well, making them integer with say 3 decimal points should make it faster.
but indeed it will also cause a lot of extra code.

well, you boys can be developing now.
my code is fully compressed now and it can't even be optimized any less without increasing of the code size dramatically.

so, if someone goes under 240 strokes with good CD times, I give up.

good luck to ya.


LonkeroAdministrator
(KiX Master Guru)
2003-03-13 12:10 AM
Re: KiXtart Golf: CD Sorter

well, as could not get my hands on the older versions can't say for sure but AFAIK the problem is the bug.

get the newist version and if there is still problems, we might get to report new bug [Big Grin]


Richard H.Administrator
(KiX Supporter)
2003-03-13 12:42 AM
Re: KiXtart Golf: CD Sorter

Well, a trial run (first 5 CDs) optimised all of them.

Full run in progress now.


Richard H.Administrator
(KiX Supporter)
2003-03-12 01:46 PM
Re: KiXtart Golf: CD Sorter

At last! A full run.

Optimised 11 CDs - the one that is not optimised can be optimised by a further "0%" apparently.

How do I do that then?

Here's the results. The golf score is not interesting as the UDF is still full of long variable names and debug code.

quote:
CD #1
Title = 70's Super Funk
Song #s = 20,19,16,15,13,7,6,5
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

CD #2
Title = Partridge Family Unlimited
Song #s = 19,9,8,4,3,1
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 44.94
CD has been fully optimized
A valid CD has been created

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 15,14,13,12,11,10,8,6,5,4,2,1
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.01
Opt. Length = 44.96
CD has been fully optimized
A valid CD has been created

CD #4
Title = Support Your Local KiXGolfer
Song #s = 40,39,38,37,36,35,34,25
CD Length = 44.80
CD Gap = 0.20
CD Gap [%] = 0.44
Opt. Length = 44.70
CD has been fully optimized
A valid CD has been created

CD #5
Title = ABBA Bubba!
Song #s = 30,29,28,27,26,25,24,23,22,21,20,19,16,12,11,9,8,6,4
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 44.96
CD has been fully optimized
A valid CD has been created

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 8,7,5,4,2,1
CD Length = 44.60
CD Gap = 0.40
CD Gap [%] = 0.89
Opt. Length = 44.50
CD has been fully optimized
A valid CD has been created

CD #7
Title = Moon Rocks!
Song #s = 40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,18,
13,11,9,6,3,2
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

CD #8
Title = Ruud's Favs
Song #s = 20,19,18,17,16,15,10,9,8,7,6,5,4,3,2
CD Length = 44.58
CD Gap = 0.42
CD Gap [%] = 0.92
Opt. Length = 44.58
CD can be further optimized by 0%
A valid CD has been created

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,
28,27,25,22,21,20,19,16,13,5
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,
28,27,26,24,23,22,21,20,19,16,15,14,13,8,7,6,4
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 70,69,68,67,50
CD Length = 44.25
CD Gap = 0.75
CD Gap [%] = 1.67
Opt. Length = 44.25
CD has been fully optimized
A valid CD has been created

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 100,99,98,97,96,95,94,93,85,62,41
CD Length = 45.00
CD Gap = 0.00
CD Gap [%] = 0.00
Opt. Length = 45.00
CD has been fully optimized
A valid CD has been created

Average CD Length = 44.85
Average Gap = 0.15
Average Gap [%] = 0.33

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel(R) Pentium(R) 4 CPU 2.00GHz
Speed = 2000 MHz
Memory = 247 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/12 11:10:55.056
Processing End = 2003/03/12 12:47:29.431
Duration = 0000/00/00 01:36:34.375
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 11
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 549

Thank you for participating in KiXtart Golf!

So, the question is what does the "0%" mean? Can this disk be optimised further or not?
The optimal length is 44.58 and the created cd is 44.58 (CD#8)

Looks to me like is should be 12 optimised CDs.

[ 12. March 2003, 13:48: Message edited by: Richard H. ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 01:50 PM
Re: KiXtart Golf: CD Sorter

same question I had...
have to look up


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 01:55 PM
Re: KiXtart Golf: CD Sorter

optimal results with cd8:
Songs=3,20,2,11,7,6,19,10,1,5,8,13,14,9,17

would need to calc those values but I think it's all about floating point overflow.
it can also be that jens is only calculating for say 0.001 and your code is 0.0000001 better or worse in time...


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 02:01 PM
Re: KiXtart Golf: CD Sorter

now as I think of it.
yeah.
the screen only displays the seconds but he most likely has a $optimal>$UDFprovided switch which does calc with floats.


Richard H.Administrator
(KiX Supporter)
2003-03-12 02:26 PM
Re: KiXtart Golf: CD Sorter

CD#8 only takes 3 mins to calculate so I ran again.

CD size generated is 44.5842, so my result is .0042 better than the optimal [Eek!]


MightyR1
(MM club member)
2003-03-12 02:37 PM
Re: KiXtart Golf: CD Sorter

Lonk / Rich,

You guys are running like crazy...

I'm a bit stuck [Frown]
Will start thinking of new algorithm!


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 02:52 PM
Re: KiXtart Golf: CD Sorter

richard, did you calc also what is the actual time for the optimal?
it can be also something like 44.5847


Richard H.Administrator
(KiX Supporter)
2003-03-12 03:01 PM
Re: KiXtart Golf: CD Sorter

Ok, I'm in a bit of a quandry now.

I've got a solution that fully optimises all CDs.

It takes about 1 hour 40 minutes on a machine that I use for work, so I'm not really interested in running it 100 times to generate exactly the same results. Just take the result and multiply by 100 for a worst case run time.

Now, do I start cutting the code to get a lower byte count, or do I start adding code to get a faster executing script?

Do I change the algorithm for one which produces a less accurate result with a smaller script or faster run time?


Richard H.Administrator
(KiX Supporter)
2003-03-12 03:02 PM
Re: KiXtart Golf: CD Sorter

quote:
richard, did you calc also what is the actual time for the optimal?
it can be also something like 44.5847

No, fair point. I'll do that now.


Richard H.Administrator
(KiX Supporter)
2003-03-12 03:19 PM
Re: KiXtart Golf: CD Sorter

This is England calling...

The result in reverse order for CD#8 is...
code:
CD #8
Title = Ruud's Favs
Song #s = 20,19,18,17,16,15,10,9,8,7,6,5,4,3,2
CD Length = 44.58
CD Length = 44.5842
CD Gap = 0.42
CD Gap [%] = 0.92
Opt. Length = 44.58
Opt. Length = 44.5842
CD can be further optimized by 0%
A valid CD has been created

The lengths are printed twice - the second length is unformatted.

So they appear to be the same, although the script insists that it can be further optimised.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 03:38 PM
Re: KiXtart Golf: CD Sorter

so, it's bug in jens' code.

what comes to the task and competition...
I think we have no competition possible anymore or if we do, we need to do 3 different goals:
-fastest
-most accurate
-smallest

my current code combines these all but we can't compare our scripts in any way if there is no one clear goal. which we don't have now... I quess.

or was it that to do a script that executes 100 loops before next sunday and does that in accepted way and is smallest.

I have already created my current golf code.
if we go for valid and small, this should be unbeatable:

[edit, removed shitty stuff as proven my point]

hehee!
I'm good [Big Grin]

[ 12. March 2003, 18:20: Message edited by: Lonkero ]


Sealeopard
(KiX Master)
2003-03-12 04:14 PM
Re: KiXtart Golf: CD Sorter

Joeel: Your code won't stand up to the competition as everybody else has better optimized code, which is part of the requirements.

I've also got word back from Ruud, he confirmed that there's a bug in the FORMATNUMBER() function. He has already provided me with a private build that should eliminate the bug. However, I will have to test this first and report back to Ruud.

With regards to the 'loop 100 times' issue: The 'run time' display will show whether your code can run within the allotted time, so I'm flexible on that one. I choose '100' as an relatively arbitrary number which would translate to about 2 hours per loop. Two hours seemed very reasonable to me.

I will beef up the reporting part a little bit so that the processing time will also be reported on a per-CD basis.

I'm also going to investigate the 'Can be optimized by 0.00%' issue. However, I believe it's just a display problem, as the length calculations are accurate to four digits but I'm only displaying two digits. I will modify the code accordingly.

The determination whether there's room for improvement is water-tight, however, I will double-check this, too.

[ 12. March 2003, 16:41: Message edited by: sealeopard ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 04:19 PM
Re: KiXtart Golf: CD Sorter

eh?
it does not stand?
so new rule we got here... I see.

the code has to be 100% optimized and shortest to be the winner.
ok, re-doing my codes...


Sealeopard
(KiX Master)
2003-03-12 04:24 PM
Re: KiXtart Golf: CD Sorter

It does not have to be 100% optimized, however the rules do state
quote:
More precisely, given a comma-delimited list of arbitrary indices, songList, find an array of indices, indexList, such that
  • sum(songList(indexList)) <= mediaLength, and
  • gap = (mediaLength - sum(songList(indexList))) / mediaLength is minimized.

Without this requirement I could just return one song per CD and achieve a low KiXGolf score. [Wink]


Richard H.Administrator
(KiX Supporter)
2003-03-12 04:35 PM
Re: KiXtart Golf: CD Sorter

quote:
I'm also going to investigate the 'Can be optimized by 0.00%' issue. However, I believe it's just a display problem, as the length calculatiosn are accurate to foru digits but I'm only displaying two digits. I will modify the code accordingly.

The determination whether there's room for improvement is water-tight, however, I will double-check this, too.

Eh? How do you mean?

If you look ate the result I posted above (CD#8) the optimal value and the value I calculated are the same to 4 decimal places, but I still get a "could be optimised further". This gives me a "room for improvement", as it is the only CD in the 12 which reports a problem.


Sealeopard
(KiX Master)
2003-03-12 04:42 PM
Re: KiXtart Golf: CD Sorter

Richard: I'll look into this.

Sealeopard
(KiX Master)
2003-03-12 05:31 PM
Re: KiXtart Golf: CD Sorter

Richard: I've rechecked your results and...
You've created a perfect CD Sorter!

The solution you've provided fully optimizes all CDs based on the 'Gold Standard' that was provided as a comparison. Interestingly, your song lists are not identical to the 'Gold Standard', especially if you look at the reuslts for CD 10. The 'Gold Standard' chooses to use only song 25.

However, you managed to improve the reference solution on a total of 10 CDs!

I have updated the output generator of the KIXGOLF_CD.KIX script. It will now give more detailed feedback about the number of optimized CDs, and whether you've beaten the gold Standard or completely filled the CD. It will also print the duration needed to compute each Cd optimization.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 06:18 PM
Re: KiXtart Golf: CD Sorter

jens, indeed... my last ironic example was doing a match against any non-zero value and returned that.
anyway, I'm still not clear with the ruling.
this far richard has the gold as what comes to filling the cd.
on the other hand I have the shortest code which compromises the disc usage in benefit of better score.

as I come to this, my shortest code gets to:
code:
Average CD Length = 44.59
Average Gap = 0.41
Average Gap [%] = 0.92

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/12 07:09:05.224
Processing End = 2003/03/12 07:24:12.879
Duration = 0000/00/00 00:15:07.655
# Loops = 100
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 3
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 243

Thank you for participating in KiXtart Golf!



Sealeopard
(KiX Master)
2003-03-12 06:42 PM
Re: KiXtart Golf: CD Sorter

However, Richard has a lower average gap, thus he minimized the gap better than you did.

If your average gap would be as good as Richards, then the KiXGolf score would be the deciding factor.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 06:51 PM
Re: KiXtart Golf: CD Sorter

ok, now you have new rule once again.
well, I just keep coding, maybe you can decide what really is golfed here before sunday.
if you can, I thank you before hand.


Jack Lothian
(MM club member)
2003-03-12 06:58 PM
Re: KiXtart Golf: CD Sorter

Jens,

I am lost. Reading the thread a second time, I have no idea what is going on.

If I read the objective of the competition correctly, then the final winner must create a program that generates a list that truly minimizes the possible 'dead time' on the CD. Any program that doesn’t generate this optimum result can not win no matter how few keystrokes that it may contain. Also, the solution must work in general, not just with your examples.

The more I think about it in this light, the more convinced that I become that this is a classical linear programming (LP) problem & the objective of the contest is to program something like the Simplex algorithm using the least number of key strokes. Because the problem is very simple (i.e. all the unknown x values can only take on values of 0 or 1) suggests one might be able to develop a specialized LP algorithm that significantly reduces the complexity & the number of keystrokes. My instinct is that this problem is more a serious math challenge than a programming challenge.

I don't believe that doing a large number of random pulls of samples from a play list can always guarantee an optimal solution. (Is this what you mean by Monte-Carlo Jens?) By varying the seeds for the random pulls & increasing the number of pulls, you could get all the correct specific solutions given by your “gold method” but I don’t see how this would work in general. Of course, all LP methods could be construed as constrained random walks that eventually converge to an optimal solution. Thus in a generic sense these methods might be referred to as Monte-Carlo solution methods. (Or is this what you mean by Monte-Carlo Jens?)

Also, any pulled sample based upon size ranking within the list can't guarantee an optimal solution. In fact starting with the longest songs would tend to generate semi-optimal solutions that minimized the number of songs on a CD. But again, your description of a Limited Search could be construed as a simplified explanation of an LP algorithm.

Another point is that an LP formulism implies that multiple optimal solutions are possible because the solution matrix is underspecified. Thus one could get 2 or more optimal solutions with the same gap but different selections lists. On the other hand, if you get 2 “optimal” solutions with different gaps then this implies that your algorithm is not correct.

If Richard is using the brute force method than his solution is equivalent to an LP solution & it is indeed a perfect solution.

Another thought is maybe this “Gold standard” that you refer to uses the combined limited & Monte-Carlo approach with a different objective in mind. Maybe minimizing "dead time" on a CD is a secondary objective. If you wanted to generate a set of CD that had a balanced mix but didn't leave too much dead time, then a random pull followed by a ranking followed by a straight count off method might work very well.

PS: Got to go for lunch now but I will look in after.

[ 12. March 2003, 19:04: Message edited by: Jack Lothian ]


Sealeopard
(KiX Master)
2003-03-12 07:33 PM
Re: KiXtart Golf: CD Sorter

Jack:

This 'Gold Standard' was calculated using a Monte-Carlo-Method followed by a Limited Search. However, as Richard already proved, there might be better solutions that actually fill the CD completely.

OTOH, there might not be a combination of songs for a given CD that actually fill the complete CD without gap. Thus, the rules specify that the gap has to be minimized without exceeding the media length.

I think that those two statements in the rules are pretty clear. It does not matter what the actual song indices are. As some of the song lists contain songs with the same length, one algorithm might choose song 17, whereas the other algorithm chooses song 18, if both songs have the same length. This is not a deciding factor.

Now, if you would like to go the LP way, yes, that is entirely possible. I think that both the MC and LS methods, however, might speed up the execution time compared to LP as you are seeding potential solutions. There are definitely different ways to solve the problem.

The solution should work in general, though the provided CD sets are a good cross-section.

Also, there cannot be two 'optimal' solutions with different gaps, as in that case one solution did not minimize the gap. Thus, you end up with just one 'optimal' solution.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 08:06 PM
Re: KiXtart Golf: CD Sorter

so once again, is the ruling now that the winner is the code with the optimal average length and if there is multiple of those, the one with best golf score?

as for now, the testcode says I have valid code and it's score is lowest, so I post that too:
quote:
Average CD Length = 44.59
Average Gap = 0.41
Average Gap [%] = 0.92

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/12 20:51:02.969
Processing End = 2003/03/12 21:05:41.212
Duration = 0000/00/00 00:14:38.243
# Loops = 100
# Processed CDs = 12
# Valid CDs = 12
# G.S. Matched CDs = 2
# G.S. Exceeded CDs = 2
KiXGolf Result = Valid CD Sorter (Room For Improvement)
KiXGolf Score = 238



Sealeopard
(KiX Master)
2003-03-12 08:14 PM
Re: KiXtart Golf: CD Sorter

Jooel:

Richards results:
quote:
Average CD Length = 44.85
Average Gap = 0.15
Average Gap [%] = 0.33

I think he's slightly better.


Jack Lothian
(MM club member)
2003-03-12 08:18 PM
Re: KiXtart Golf: CD Sorter

The point I was making was I think that only the LP & brute force methods generate optimal results consistently. Maybe the MC & LS methods might be faster or maybe even take less key strokes but that is irrelevant if they don't generate optimal results all the time.

If I am reading the thread correctly, Richard has shown that the brute force method generates at least one solution more "optimal" than the Gold Standard. If this is so,it is proof that this strategey doesn't consistently generate optimal results.

Also, what exactly do you mean by Monte-Carlo? Is this just a simple random selection process or is it something more complicated?

PS: I not sure that I understand your reference to seeding in LP solution. If you wanted to minimize key strokes, I suggest you could seed the first iteration with x(1)=x(2)=..=X(n)=0 but if your playlist were always small you could seed it with the first m elements whose sum fits below the threshold. This would converge very fast in the examples given. Maybe with less than 10 iterations in the cases shown.

[ 12. March 2003, 20:41: Message edited by: Jack Lothian ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 08:19 PM
Re: KiXtart Golf: CD Sorter

yeah, in the means of gap.
do you see my question in previous post?
or should I take this as you compare the results and then decide which is better?


Sealeopard
(KiX Master)
2003-03-12 08:38 PM
Re: KiXtart Golf: CD Sorter

As far as I understand it the Monte Carlo method creates a random subset of all potential outcomes based on specific constraints. In our case, you have for example 3 songs. Thus, you have the following potential outcomes
code:
1
2
3
12
13
23
123

The Monte-Carlo Method would create a subset of e.g. three potential outcomes that it generates randomly, e.g.
code:
1
12
23

or
code:
12
23
123

Then, only this subset is tested whether it fulfills the constraint of sum of all song lenghs smaller than media length and gap is minimized.

However, this apporach inplies that you might miss the 'perfect solution'. Thus,a limited search is appended, which checks if you can either add songs or substitute songs in order to minimize the gap further. Nevertheless, even this approach might miss the 'perfect' solution.

So, if you want the perfect solution all the time, either BF or LP will always give it to you. However, you might not finish running the script within the allotted time.


Jack Lothian
(MM club member)
2003-03-12 08:54 PM
Re: KiXtart Golf: CD Sorter

In the examples given, I believe that any LP algorithm would be very fast but the number of keystrokes used would be very high.

Because the constraint matrix is really 2 joined identity matices, I suspect that somewhere in the literature a specialized solution has been developed for this problem that significantly reduces the complexity of the problem. Find this & you may have a winner.


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 10:04 PM
Re: KiXtart Golf: CD Sorter

jens, the problem your task has is that you don't say what is approved as optimal.

you just say better.
this leaves all the judging not to rules but to you per code.

if we go for optimal, we should do a script that does full scan for all possibilities and see the perfect results and then say those are the optimal scores.

now, there is nothing to hang on.

just like jack pointed in side note, this looks like not golf but mathematical course.


maciep
(Korg Regular)
2003-03-12 10:51 PM
Re: KiXtart Golf: CD Sorter

Here's my last run. Some of the code chooses randomly, so don't know when or if I can repeat this.

quote:

CD #1
Title = 70's Super Funk
Song #s = 12,13,14,2,15,4,16,11
CD Length = 44.9975
CD Gap = 0.00250000000000483
CD Gap [%] = 0.00555555555556629
Opt. Length = 44.996
CD has been fully optimized
A valid CD has been created

CD #2
Title = Partridge Family Unlimited
Song #s = 16,2,20,6
CD Length = 44.9926
CD Gap = 0.00739999999999696
CD Gap [%] = 0.0164444444444377
Opt. Length = 44.9363
CD has been fully optimized
A valid CD has been created

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 10,12,14,13,6,15,1,5,2,8,11,4
CD Length = 44.9971
CD Gap = 0.0029000000000039
CD Gap [%] = 0.00644444444445311
Opt. Length = 44.9581
CD has been fully optimized
A valid CD has been created

CD #4
Title = Support Your Local KiXGolfer
Song #s = 32,33,34,35,36,37,38,39
CD Length = 44.8
CD Gap = 0.199999999999996
CD Gap [%] = 0.444444444444435
Opt. Length = 44.7
CD has been fully optimized
A valid CD has been created

CD #5
Title = ABBA Bubba!
Song #s = 12,15,16,17,18,19,20,21,22,23,24,25,26,27,28
CD Length = 44.9914
CD Gap = 0.00860000000000838
CD Gap [%] = 0.0191111111111297
Opt. Length = 44.9574
CD has been fully optimized
A valid CD has been created

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 8,4,5,1,2,7
CD Length = 44.6
CD Gap = 0.399999999999991
CD Gap [%] = 0.88888888888887
Opt. Length = 44.5
CD has been fully optimized
A valid CD has been created

CD #7
Title = Moon Rocks!
Song #s = 9,10,23,28,27,7,12,32,36,20,19,14,24,39,25,2,26,13,34,5,18,31,21,17,35,37,40,4
CD Length = 45
CD Gap = 0
CD Gap [%] = 0
Opt. Length = 44.9992
CD has been fully optimized
A valid CD has been created

CD #8
Title = Ruud's Favs
Song #s = 1,3,4,5,6,7,8,9,10,11,12,13,14,15,16
CD Length = 44.5842
CD Gap = 0.415800000000004
CD Gap [%] = 0.92400000000001
Opt. Length = 44.5842
CD has been fully optimized
A valid CD has been created

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 31,21,19,35,45,11,43,7,15,44,18,29,24,28,9,26,6,3,37,1,23
CD Length = 45
CD Gap = 0
CD Gap [%] = 0
Opt. Length = 44.9995
CD has been fully optimized
A valid CD has been created

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 25
CD Length = 44.999
CD Gap = 0.000999999999997669
CD Gap [%] = 0.00222222222221704
Opt. Length = 44.999
CD has been fully optimized
A valid CD has been created

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 60,69,57,68,27
CD Length = 44.25
CD Gap = 0.75
CD Gap [%] = 1.66666666666667
Opt. Length = 44.25
CD has been fully optimized
A valid CD has been created

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 66,76,77,78,79,80,81,82,83,84
CD Length = 44.9999
CD Gap = 9.99999999962142E-005
CD Gap [%] = 0.000222222222213809
Opt. Length = 44.9987
CD has been fully optimized
A valid CD has been created

Average CD Length = 44.850975
Average Gap = 0.149025
Average Gap [%] = 0.331166666666667

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/12 16:40:27.97
Processing End = 2003/03/12 16:48:39.419
Duration = 0000/00/00 00:08:12.322
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Optimized CDs = 12
KiXGolf Result = Perfect CD Sorter
KiXGolf Score = 737

Thank you for participating in KiXtart Golf!



Sealeopard
(KiX Master)
2003-03-12 11:23 PM
Re: KiXtart Golf: CD Sorter

First of all, I'd like to apologize for the confusion creted by the ambiguous rules.

If everybody agrees that this would be a fair change, then I would like to change the two rules/constraints for the CD Sorter algorithm as follows:
  • sum(songList(indexList)) <= mediaLength, with mediaLength=45 minutes, thus sum<45
  • gap = (mediaLength - sum(songList(indexList))) is smaller than 1 minute, thus gap<1
As long as you have a total song lengh of <=45 and a gap of <1 your code is valid and will compete solely on the merits of it's KiXGolf score.

[ 12. March 2003, 23:39: Message edited by: sealeopard ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-12 11:36 PM
Re: KiXtart Golf: CD Sorter

oh, that is better.
but, I thought the media was minutes [Razz]

so, sure I have pieces in this light to improve.


Sealeopard
(KiX Master)
2003-03-12 11:43 PM
Re: KiXtart Golf: CD Sorter

I'll be around for another 20 minutes. If nobody objects I will update the scripts accordingly and restate the tasks, rules, and constraints.

[ 13. March 2003, 00:21: Message edited by: sealeopard ]


Sealeopard
(KiX Master)
2003-03-13 12:26 AM
Re: KiXtart Golf: CD Sorter

Update:

Rule Change: Due to some discussion during the tournament the second constraint has been changed. You no longer need to 'minimize' the gap. It is sufficient if the gap is less than 1 minute.
All documentation has been updated accordingly and the KIXGOLF_CD.ZIP package at http://people.bu.edu/jenmeyer/kixtart/kixgolf_cd.zip also reflects this rule change. My apologies.

Constraints:
  • sum(songList(indexList)) <= mediaLength, with mediaLength = 45 minutes and
  • gap = (mediaLength - sum(songList(indexList))) <1 minute
All results submitted so far fulfill these constraints.

[ 13. March 2003, 00:29: Message edited by: sealeopard ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-13 12:37 AM
Re: KiXtart Golf: CD Sorter

sorry to ask once more [Wink]
I understand by your stating that "all are qualified this far" that you are not talking about individual cd-gaps but the average?


Sealeopard
(KiX Master)
2003-03-13 04:05 AM
Re: KiXtart Golf: CD Sorter

Jooel:

The gap of each CD has to be less than one minute.

Richard submitted a valid run at http://www.kixtart.org/board/ultimatebb.php?ubb=get_topic;f=14;t=000491;p=4#000082

Maciep submitted a valid run at http://www.kixtart.org/board/ultimatebb.php?ubb=get_topic;f=14;t=000491;p=5#000111

Jooel, your submission at http://www.kixtart.org/board/ultimatebb.php?ubb=get_topic;f=14;t=000491;p=3#000073 seems to have a problem with CD8 as the gap is larger than one minute.


Richard H.Administrator
(KiX Supporter)
2003-03-13 01:21 PM
Re: KiXtart Golf: CD Sorter

Two results.

Result 1 is "best fit".

Result 2 is "less than one minute gap".

Result 2 is 5 bytes shorter ("1" instead of "0.0001" [Smile] ) and is much, much quicker.

As before, this is a linear approach so the results will be identical each time - there is no gain in running the process 100 times.

I made a speed-up change to the best fit which has brought the run time down from 1:40:00 to 1:10:00, but I may have lost some accuracy, so will try with the speed-up backed out.

RESULT 1 : BEST FIT
code:
CD #1
Title = 70's Super Funk
Song #s = 20,19,16,15,13,7,6,5
CD Length = 44.9999
CD Gap = 0.0001
CD Gap [%] = 0.0002
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:54:49.775
Processing End = 2003/03/13 10:56:06.681
Duration = 0000/00/00 00:01:16.905

CD #2
Title = Partridge Family Unlimited
Song #s = 17,10,9,5,4
CD Length = 44.9984
CD Gap = 0.0016
CD Gap [%] = 0.0036
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:06.681
Processing End = 2003/03/13 10:56:07.916
Duration = 0000/00/00 00:00:01.235

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 15,13,12,11,10,9,8,6,5,4,3
CD Length = 44.9947
CD Gap = 0.0053
CD Gap [%] = 0.0118
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:07.916
Processing End = 2003/03/13 10:56:11.385
Duration = 0000/00/00 00:00:03.469

CD #4
Title = Support Your Local KiXGolfer
Song #s = 40,39,38,37,36,35,34,25
CD Length = 44.8000
CD Gap = 0.2000
CD Gap [%] = 0.4444
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:11.385
Processing End = 2003/03/13 10:56:19.135
Duration = 0000/00/00 00:00:07.750

CD #5
Title = ABBA Bubba!
Song #s = 30,29,28,27,26,25,24,23,22,21,20,19,16,12,11,9,8,6,4
CD Length = 45.0000
CD Gap = 0.0000
CD Gap [%] = 0.0000
Req. CD Length = 44.0000
Result = CD has been filled completely
Processing Start = 2003/03/13 10:56:19.135
Processing End = 2003/03/13 10:56:20.885
Duration = 0000/00/00 00:00:01.750

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 8,7,5,4,3
CD Length = 44.5000
CD Gap = 0.5000
CD Gap [%] = 1.1111
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:20.900
Processing End = 2003/03/13 10:56:20.916
Duration = 0000/00/00 00:00:00.015

CD #7
Title = Moon Rocks!
Song #s = 40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,2
0,18,13,11,9,6,3,2
CD Length = 44.9999
CD Gap = 0.0001
CD Gap [%] = 0.0002
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:20.916
Processing End = 2003/03/13 10:56:25.510
Duration = 0000/00/00 00:00:04.594

CD #8
Title = Ruud's Favs
Song #s = 20,19,18,17,16,15,10,9,8,7,6,5,4,3,2
CD Length = 44.5842
CD Gap = 0.4158
CD Gap [%] = 0.9240
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:56:25.510
Processing End = 2003/03/13 10:58:23.760
Duration = 0000/00/00 00:01:58.250

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,3
0,29,28,27,25,22,21,20,19,16,13,5
CD Length = 44.9999
CD Gap = 0.0001
CD Gap [%] = 0.0002
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 10:58:23.760
Processing End = 2003/03/13 11:42:21.900
Duration = 0000/00/00 00:43:58.140

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,3
0,29,28,27,26,24,23,22,21,20,19,16,15,14,13,8,7,6,4
CD Length = 44.9999
CD Gap = 0.0001
CD Gap [%] = 0.0002
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 11:42:21.900
Processing End = 2003/03/13 11:42:25.322
Duration = 0000/00/00 00:00:03.421

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 70,69,68,67,50
CD Length = 44.2500
CD Gap = 0.7500
CD Gap [%] = 1.6667
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 11:42:25.322
Processing End = 2003/03/13 12:05:58.963
Duration = 0000/00/00 00:23:33.641

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 100,99,98,97,96,95,94,93,85,62,41
CD Length = 45.0000
CD Gap = 0.0000
CD Gap [%] = 0.0000
Req. CD Length = 44.0000
Result = CD has been filled completely
Processing Start = 2003/03/13 12:05:58.963
Processing End = 2003/03/13 12:06:03.244
Duration = 0000/00/00 00:00:04.280

Average CD Length = 44.84
Average Gap = 0.16
Average Gap [%] = 0.35

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel(R) Pentium(R) 4 CPU 2.00GHz
Speed = 2000 MHz
Memory = 247 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 10:54:49.775
Processing End = 2003/03/13 12:06:03.244
Duration = 0000/00/00 01:11:13.469
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 288

RESULT 2 : GAP SMALLER THAN 1 MINUTE
code:
CD #1
Title = 70's Super Funk
Song #s = 20,19,18,17,16,15,14,13
CD Length = 44.5116
CD Gap = 0.4884
CD Gap [%] = 1.0853
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.822
Processing End = 2003/03/13 12:09:32.822
Duration = 0000/00/00 00:00:00.000

CD #2
Title = Partridge Family Unlimited
Song #s = 20,19,6
CD Length = 44.6494
CD Gap = 0.3506
CD Gap [%] = 0.7791
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.822
Processing End = 2003/03/13 12:09:32.838
Duration = 0000/00/00 00:00:00.016

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 15,14,13,12,11,10,9,8,7,6,4
CD Length = 44.5929
CD Gap = 0.4071
CD Gap [%] = 0.9047
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.838
Processing End = 2003/03/13 12:09:32.838
Duration = 0000/00/00 00:00:00.000

CD #4
Title = Support Your Local KiXGolfer
Song #s = 40,39,38,37,36,35,34,25
CD Length = 44.8000
CD Gap = 0.2000
CD Gap [%] = 0.4444
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.838
Processing End = 2003/03/13 12:09:32.838
Duration = 0000/00/00 00:00:00.000

CD #5
Title = ABBA Bubba!
Song #s = 30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15
CD Length = 44.8775
CD Gap = 0.1225
CD Gap [%] = 0.2722
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.838
Processing End = 2003/03/13 12:09:32.838
Duration = 0000/00/00 00:00:00.000

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 9,6,3
CD Length = 44.3000
CD Gap = 0.7000
CD Gap [%] = 1.5556
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.838
Processing End = 2003/03/13 12:09:32.853
Duration = 0000/00/00 00:00:00.014

CD #7
Title = Moon Rocks!
Song #s = 40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,2
0,19,18,17,15,14,13
CD Length = 44.9722
CD Gap = 0.0278
CD Gap [%] = 0.0618
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.853
Processing End = 2003/03/13 12:09:32.853
Duration = 0000/00/00 00:00:00.000

CD #8
Title = Ruud's Favs
Song #s = 20,19,18,17,16,15,14,10,9,8,7,6,5,4,3
CD Length = 44.1609
CD Gap = 0.8391
CD Gap [%] = 1.8647
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:32.853
Processing End = 2003/03/13 12:09:33.541
Duration = 0000/00/00 00:00:00.687

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,3
0,29,28,27,26,25,23,22,21
CD Length = 44.9664
CD Gap = 0.0336
CD Gap [%] = 0.0747
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:09:33.541
Processing End = 2003/03/13 12:16:53.635
Duration = 0000/00/00 00:07:20.094

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,3
0,29,28,27,26,24,23,22,21,20,19,17,16,15,14,13,12,11,10,8
CD Length = 44.9014
CD Gap = 0.0986
CD Gap [%] = 0.2191
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:16:53.635
Processing End = 2003/03/13 12:16:53.650
Duration = 0000/00/00 00:00:00.014

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 70,69,68,67,50
CD Length = 44.2500
CD Gap = 0.7500
CD Gap [%] = 1.6667
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:16:53.650
Processing End = 2003/03/13 12:18:09.353
Duration = 0000/00/00 00:01:15.703

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 100,99,98,97,96,95,94,93,92,91,87
CD Length = 44.5786
CD Gap = 0.4214
CD Gap [%] = 0.9364
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 12:18:09.353
Processing End = 2003/03/13 12:18:09.353
Duration = 0000/00/00 00:00:00.000

Average CD Length = 44.63
Average Gap = 0.37
Average Gap [%] = 0.82

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel(R) Pentium(R) 4 CPU 2.00GHz
Speed = 2000 MHz
Memory = 247 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 12:09:32.822
Processing End = 2003/03/13 12:18:09.353
Duration = 0000/00/00 00:08:36.531
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 283



LonkeroAdministrator
(KiX Master Guru)
2003-03-13 01:28 PM
Re: KiXtart Golf: CD Sorter

damn!
that's nice.
even though it's not the fastest avail but it's faster than fast as you think of the accuracy it has.


maciep
(Korg Regular)
2003-03-13 02:44 PM
Re: KiXtart Golf: CD Sorter

quote:

CD #1
Title = 70's Super Funk
Song #s = 16,1,7,6,14,18,10,17,2
CD Length = 44.9315
CD Gap = 0.0685
CD Gap [%] = 0.1522
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:23.816
Processing End = 2003/03/13 08:39:27.519
Duration = 0000/00/00 00:00:03.703

CD #2
Title = Partridge Family Unlimited
Song #s = 16,12,6,2,8
CD Length = 44.5697
CD Gap = 0.4303
CD Gap [%] = 0.9562
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:27.519
Processing End = 2003/03/13 08:39:28.878
Duration = 0000/00/00 00:00:01.359

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 6,5,13,4,10,8,15,1,2,11,12,14
CD Length = 44.9971
CD Gap = 0.0029
CD Gap [%] = 0.0064
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:28.878
Processing End = 2003/03/13 08:39:32.065
Duration = 0000/00/00 00:00:03.186

CD #4
Title = Support Your Local KiXGolfer
Song #s = 20,36,23
CD Length = 44.3000
CD Gap = 0.7000
CD Gap [%] = 1.5556
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:32.065
Processing End = 2003/03/13 08:39:33.862
Duration = 0000/00/00 00:00:01.797

CD #5
Title = ABBA Bubba!
Song #s = 6,3,12,2,14,20,26,27,1,13,17,4,24,30,22,21,16,25
CD Length = 44.9923
CD Gap = 0.0077
CD Gap [%] = 0.0171
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:33.862
Processing End = 2003/03/13 08:39:43.159
Duration = 0000/00/00 00:00:09.296

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 7,4,5,1,2,8
CD Length = 44.6000
CD Gap = 0.4000
CD Gap [%] = 0.8889
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:43.159
Processing End = 2003/03/13 08:39:43.737
Duration = 0000/00/00 00:00:00.578

CD #7
Title = Moon Rocks!
Song #s = 37,21,17,11,29,12,22,7,34,25,33,39,4,31,40,23,20,2,3,24,28,5,32,30,19,1,15,10,14
CD Length = 44.9983
CD Gap = 0.0017
CD Gap [%] = 0.0038
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:39:43.737
Processing End = 2003/03/13 08:40:00.034
Duration = 0000/00/00 00:00:16.296

CD #8
Title = Ruud's Favs
Song #s = 13,3,18,1,4,9,8,7,19,5,15,14,2,10,20
CD Length = 44.5842
CD Gap = 0.4158
CD Gap [%] = 0.9240
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:40:00.034
Processing End = 2003/03/13 08:40:04.659
Duration = 0000/00/00 00:00:04.625

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 36,37,13,5,17,44,24,15,50,42,26,18,27,47,19,12,32,28,48,41,16,10,21,14,35,45
CD Length = 44.9919
CD Gap = 0.0081
CD Gap [%] = 0.0180
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:40:04.659
Processing End = 2003/03/13 08:40:39.533
Duration = 0000/00/00 00:00:34.873

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 25
CD Length = 44.9990
CD Gap = 0.0010
CD Gap [%] = 0.0022
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:40:39.533
Processing End = 2003/03/13 08:41:00.595
Duration = 0000/00/00 00:00:21.062

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 62,55,54,23,61
CD Length = 44.2500
CD Gap = 0.7500
CD Gap [%] = 1.6667
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 08:41:00.611
Processing End = 2003/03/13 08:41:03.298
Duration = 0000/00/00 00:00:02.686

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 50,45,66,8,60,32,86,96,87,39
CD Length = 45.0000
CD Gap = 0.0000
CD Gap [%] = 0.0000
Req. CD Length = 44.0000
Result = CD has been filled completely
Processing Start = 2003/03/13 08:41:03.298
Processing End = 2003/03/13 08:41:20.516
Duration = 0000/00/00 00:00:17.218

Average CD Length = 44.77
Average Gap = 0.23
Average Gap [%] = 0.52

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 08:39:23.816
Processing End = 2003/03/13 08:41:20.516
Duration = 0000/00/00 00:01:56.700
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 1
KiXGolf Result = Valid CD Filling
KiXGolf Score = 367

Thank you for participating in KiXtart Golf!



maciep
(Korg Regular)
2003-03-13 04:34 PM
Re: KiXtart Golf: CD Sorter

quote:

Average CD Length = 44.52
Average Gap = 0.48
Average Gap [%] = 1.07

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 10:39:00.931
Processing End = 2003/03/13 10:39:05.727
Duration = 0000/00/00 00:00:04.796
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 297

Thank you for participating in KiXtart Golf!



Richard H.Administrator
(KiX Supporter)
2003-03-13 04:38 PM
Re: KiXtart Golf: CD Sorter

Stole another byte.

287 Best fit score (accuracy)
282 Under 1 minute gap score (speed/size)

It's now completely unreadable, which I guess means I probably can't make it any smaller [Wink]


maciep
(Korg Regular)
2003-03-13 05:16 PM
Re: KiXtart Golf: CD Sorter

quote:

Average CD Length = 44.44
Average Gap = 0.56
Average Gap [%] = 1.24

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 11:20:48.606
Processing End = 2003/03/13 11:20:52.122
Duration = 0000/00/00 00:00:03.516
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 278

Thank you for participating in KiXtart Golf!



Sealeopard
(KiX Master)
2003-03-13 06:18 PM
Re: KiXtart Golf: CD Sorter

Nice results, everybody! [Big Grin]

LonkeroAdministrator
(KiX Master Guru)
2003-03-13 06:31 PM
Re: KiXtart Golf: CD Sorter

doh, I could not get with my syntax from current av.gap of 0.91 under 0.89 and that is not enough.

and I'm even running out of time.


LonkeroAdministrator
(KiX Master Guru)
2003-03-13 10:27 PM
Re: KiXtart Golf: CD Sorter

k, hence the new ruling, was able to make it fit with some additional strokes... exactly 40 more.
and the time, from previous 9secs per total loop, this lasts now 38mins!
anyway:

code:
CD #1
Title = 70's Super Funk
Song #s = 1,2,3,4,5,6,7,8,9,11,13,15,17,18
CD Length = 44.9963
CD Gap = 0.0037
CD Gap [%] = 0.0082
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:00.336
Processing End = 2003/03/13 22:51:00.837
Duration = 0000/00/00 00:00:00.501

CD #2
Title = Partridge Family Unlimited
Song #s = 2,4,5,6,7,8,12
CD Length = 44.9882
CD Gap = 0.0118
CD Gap [%] = 0.0262
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:00.837
Processing End = 2003/03/13 22:51:02.369
Duration = 0000/00/00 00:00:01.532

CD #3
Title = Three Tenors in Antarctica, Again!
Song #s = 1,2,3,4,5,6,9,10,11,15
CD Length = 44.9964
CD Gap = 0.0036
CD Gap [%] = 0.0080
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:02.369
Processing End = 2003/03/13 22:51:02.549
Duration = 0000/00/00 00:00:00.179

CD #4
Title = Support Your Local KiXGolfer
Song #s = 19,30,35,38,39
CD Length = 44.5000
CD Gap = 0.5000
CD Gap [%] = 1.1111
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:02.549
Processing End = 2003/03/13 22:51:02.990
Duration = 0000/00/00 00:00:00.441

CD #5
Title = ABBA Bubba!
Song #s = 1,2,3,5,6,7,8,10,12,15,16,20,29
CD Length = 44.9997
CD Gap = 0.0003
CD Gap [%] = 0.0007
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:02.990
Processing End = 2003/03/13 22:51:16.209
Duration = 0000/00/00 00:00:13.218

CD #6
Title = Songs You Never Wanted Your Teenage Daughter To Know About
Song #s = 1,2,4,5,7,8
CD Length = 44.6000
CD Gap = 0.4000
CD Gap [%] = 0.8889
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:16.209
Processing End = 2003/03/13 22:51:16.249
Duration = 0000/00/00 00:00:00.039

CD #7
Title = Moon Rocks!
Song #s = 1,2,3,4,5,6,7,8,10,12,13,14,16,17,26,36,39
CD Length = 44.9999
CD Gap = 0.0001
CD Gap [%] = 0.0002
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:51:16.249
Processing End = 2003/03/13 22:52:00.973
Duration = 0000/00/00 00:00:44.724

CD #8
Title = Ruud's Favs
Song #s = 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16
CD Length = 44.5842
CD Gap = 0.4158
CD Gap [%] = 0.9240
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:52:00.973
Processing End = 2003/03/13 22:52:01.444
Duration = 0000/00/00 00:00:00.471

CD #9
Title = MTV Presents: KiXtart Rulez!
Song #s = 1,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,21,22,23,24,26,27,28,30,35,39,48
CD Length = 45.0000
CD Gap = 0.0000
CD Gap [%] = 0.0000
Req. CD Length = 44.0000
Result = CD has been filled completely
Processing Start = 2003/03/13 22:52:01.444
Processing End = 2003/03/13 22:56:32.413
Duration = 0000/00/00 00:04:30.968

CD #10
Title = Songs From the Programmer's Abyss
Song #s = 1,2,3,4,5,6,7,8,9,11,12,13,14,15,18,21,26,28,29
CD Length = 45.0000
CD Gap = 0.0000
CD Gap [%] = 0.0000
Req. CD Length = 44.0000
Result = CD has been filled completely
Processing Start = 2003/03/13 22:56:32.413
Processing End = 2003/03/13 22:57:27.012
Duration = 0000/00/00 00:00:54.599

CD #11
Title = Just Noise (100% Pure White Noise)
Song #s = 1,51,52,53,54
CD Length = 44.2500
CD Gap = 0.7500
CD Gap [%] = 1.6667
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 22:57:27.012
Processing End = 2003/03/13 23:27:55.942
Duration = 0000/00/00 00:30:28.929

CD #12
Title = Cazy Jens And the KIXGolfers
Song #s = 1,2,3,4,6,7,8,9,22,24
CD Length = 44.9997
CD Gap = 0.0003
CD Gap [%] = 0.0007
Req. CD Length = 44.0000
Result = CD has been filled
Processing Start = 2003/03/13 23:27:55.942
Processing End = 2003/03/13 23:29:04.861
Duration = 0000/00/00 00:01:08.919

Average CD Length = 44.83
Average Gap = 0.17
Average Gap [%] = 0.39

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 22:51:00.336
Processing End = 2003/03/13 23:29:04.861
Duration = 0000/00/00 00:38:04.525
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 278

Thank you for participating in KiXtart Golf!



maciep
(Korg Regular)
2003-03-13 10:30 PM
Re: KiXtart Golf: CD Sorter

quote:

Average CD Length = 44.48
Average Gap = 0.52
Average Gap [%] = 1.16

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 16:34:42.397
Processing End = 2003/03/13 16:34:44.241
Duration = 0000/00/00 00:00:01.844
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 249

Thank you for participating in KiXtart Golf!



LonkeroAdministrator
(KiX Master Guru)
2003-03-13 10:44 PM
Re: KiXtart Golf: CD Sorter

this is not fair!
you have so fast code and all!


LonkeroAdministrator
(KiX Master Guru)
2003-03-13 11:17 PM
Re: KiXtart Golf: CD Sorter

Average CD Length = 44.83
Average Gap = 0.17
Average Gap [%] = 0.39

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/13 23:42:46.052
Processing End = 2003/03/14 00:22:28.758
Duration = 0000/00/01 -1
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 256

Thank you for participating in KiXtart Golf!


LonkeroAdministrator
(KiX Master Guru)
2003-03-13 11:43 PM
Re: KiXtart Golf: CD Sorter

still, nice to see how my changes do affect to the speed.
even though small difference in resulting gap, the time increases dramatically.

but only in some special songlist types.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 12:24 AM
Re: KiXtart Golf: CD Sorter


Average CD Length = 44.83
Average Gap = 0.17
Average Gap [%] = 0.39

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 00:48:32.627
Processing End = 2003/03/14 01:27:49.666
Duration = 0000/00/00 00:39:17.039
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 248

Thank you for participating in KiXtart Golf!


Richard H.Administrator
(KiX Supporter)
2003-03-14 10:31 AM
Re: KiXtart Golf: CD Sorter

Whoa! Way to go Jooel!

Removed some speed-up code, which in a general solution would be relevant, but doesn't appear to have much effect on this particular data set, so the best fit code is now:
code:
Average CD Length = 44.84
Average Gap = 0.16
Average Gap [%] = 0.35

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel(R) Pentium(R) 4 CPU 2.00GHz
Speed = 2000 MHz
Memory = 247 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 08:23:54.322
Processing End = 2003/03/14 09:33:08.463
Duration = 0000/00/00 01:09:14.141
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 279

There is another bit of speed related code that I can chop to save about 15 characters, but the run times may get huge.

Will start it now and see what happens...


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 10:41 AM
Re: KiXtart Golf: CD Sorter

I was first thinking that I and maciep had same codes as the stroke count is so similar but as I see his gaps and full cd amount, I see also that our codes must be a lot different.

maciep, btw...
what is your gap on cd 8?
I had to make my code sooo slow to keep that cd above 44mins...


maciep
(Korg Regular)
2003-03-14 01:19 PM
Re: KiXtart Golf: CD Sorter

Jooel,

It's different everytime. But it's always more than 44 minutes and I didn't have to do anything special for that CD or any others [Wink] .

But, in general, my gaps are pretty high compared to yours.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 01:22 PM
Re: KiXtart Golf: CD Sorter

oh, you have randomizer!
nice.
and it's even quick.

good, I want to see that even though it might not be winner. awesome...

but I hope you don't give up now.
just try to find those 2 strokes to make you #1

my code has been so compressed for long time now, that if I remove 1 stroke, I have to add 20-30 first to make it work again and start removing again.
and that is challenge I like!


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 01:31 PM
Re: KiXtart Golf: CD Sorter

richard, you are so close now that I must ask you too not to give up...

maciep, btw...
I think that after sunday the code I will try to compress is yours.
so, please post it right away once round 2 start, so I can get to tweaking of it [Big Grin]


MightyR1
(MM club member)
2003-03-14 01:55 PM
Re: KiXtart Golf: CD Sorter

I stopped running in phase 1, can't get it to work [Frown]

Going on holliday next week... But me too will print and tweak after public phase will be started...


Richard H.Administrator
(KiX Supporter)
2003-03-14 02:15 PM
Re: KiXtart Golf: CD Sorter

It's taken 3 hours for disk #5 and still not finished, so I don't think that's going to work [Roll Eyes]

I'm not going to be able to squeeze any more out because of the underlying design (you'll see what I mean), so I've posted my last version off to Jens for posting as I'm not about this weekend.


maciep
(Korg Regular)
2003-03-14 02:45 PM
Re: KiXtart Golf: CD Sorter

Jooel,

I have 7 more strokes that I can definitely take off right now. But it slows it down to about a minute. So, I'm going to try to find all of the other little cuts before I do that. [Smile]

So basically right now my score is 242.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 03:16 PM
Re: KiXtart Golf: CD Sorter

now, that is not fair [Frown]

maciep
(Korg Regular)
2003-03-14 03:32 PM
Re: KiXtart Golf: CD Sorter

quote:

Average CD Length = 44.57
Average Gap = 0.43
Average Gap [%] = 0.97

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 09:36:34.537
Processing End = 2003/03/14 09:37:19.350
Duration = 0000/00/00 00:00:44.813
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 239

Thank you for participating in KiXtart Golf!



LonkeroAdministrator
(KiX Master Guru)
2003-03-14 03:37 PM
Re: KiXtart Golf: CD Sorter

maciep, I want to know...
how generic is your code?
like, if the songlist has only 2 five-minute songs, does it work?
or is it specific for this task?
just want to know [Wink]


maciep
(Korg Regular)
2003-03-14 04:01 PM
Re: KiXtart Golf: CD Sorter

Jooel,

It is specific for this task in that if the given gap of one minute is not attainable, the function would fail.

So, if there were only two five-minute songs in a list, then the function would not work. But if there were only two 27-minute songs in a list, it would work.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 04:04 PM
Re: KiXtart Golf: CD Sorter

yeah, just like I quessed.
no wonder I have hard time competing [Big Grin]

well, I try to keep up but I have great suspicion will I get any strokes of this without loosing the generic nature.
well, will try to improve the crypting.


Sealeopard
(KiX Master)
2003-03-14 04:08 PM
Re: KiXtart Golf: CD Sorter

So, If I would test it with gap=2, your function would fail? What happens if I change the media length?

Hmm, the whole gap-business could have lead to the introduction of a third calling parameter CD_Sorter(SongList, MediaLength, Gap) but that's too late now.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 04:11 PM
Re: KiXtart Golf: CD Sorter

jens, the gap thingie could have been with percent ruling.
but what comes to medialength, wonder why you wanted to use the same.

could have collected the info together from multiple loops with multiple media-lengths...

well, think that it's too late for this also.


Sealeopard
(KiX Master)
2003-03-14 04:17 PM
Re: KiXtart Golf: CD Sorter

Yes, I know, two loops, one for media lengths between e.g. 0 and max(sum(Songlist)), the other one for a gap of 0.05%-20% of media length.

But, as you said, this is too late now. Unless we modify the goal of the second (public) coding round. I'm not going to make any changes to the current setup.


maciep
(Korg Regular)
2003-03-14 04:29 PM
Re: KiXtart Golf: CD Sorter

Guys,

Media length is not a factor in my function. If it's changed, the function will still work.

Personally, I agree that CDSorter() should have a third parameter for the gap. Right now, I have it hardcoded as 1 minute.

Anyway,

quote:

Average CD Length = 44.47
Average Gap = 0.53
Average Gap [%] = 1.18

KiXtart
KiXtart Version = 4.20
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows XP Professional
CPU = Intel Pentium III
Speed = 730 MHz
Memory = 126 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 10:27:32.231
Processing End = 2003/03/14 10:27:43.074
Duration = 0000/00/00 00:00:10.843
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 230

Thank you for participating in KiXtart Golf!



[ 14. March 2003, 16:30: Message edited by: maciep ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 04:31 PM
Re: KiXtart Golf: CD Sorter

not saying that medialength is a factor but it would bring up real-world usage example.

that is the reason the parameter was added in first place.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 06:53 PM
Re: KiXtart Golf: CD Sorter

btw, jens...

think that we could make a cycle counter for next golf tournament.
purely kix-solution and not perfect I have in mind but anyway.


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 07:33 PM
Re: KiXtart Golf: CD Sorter


Average CD Length = 44.83
Average Gap = 0.17
Average Gap [%] = 0.39

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 19:58:48.046
Processing End = 2003/03/14 20:38:02.722
Duration = 0000/00/00 00:39:14.675
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 245

Thank you for participating in KiXtart Golf!


LonkeroAdministrator
(KiX Master Guru)
2003-03-14 08:12 PM
Re: KiXtart Golf: CD Sorter

I don't actually like the Idea of gap as arg.

it's then no more real-life situation.
who knows before hand the best solution without testing?
and who needs to know anything anymore when he knows the ideal?

that is stupid in that way.
but the gap could have been percent of the media length IF POSSIBLE or little lower etc.

this way the task would have double harder too.


maciep
(Korg Regular)
2003-03-14 08:26 PM
Re: KiXtart Golf: CD Sorter

I understand what you're saying, but I still like the gap. It gives us a set of rules. I mean after all, this is a golf tournament. So with no rules, whose the winner? Would it be lowest score, smallest gap or fastest function?

Gap % would work too, but it would just add strokes to my score, it wouldn't change my algorithm at all.

And as far as real world goes, I don't think a function that takes 40 minutes to fill 12 CD's with songs would be very acceptable.


Jack Lothian
(MM club member)
2003-03-15 12:42 AM
Re: KiXtart Golf: CD Sorter

I am not sure about the gap being the key variable. Rounding is raising its ugly head in all my tests. Several of Jens' examples can give multiple answers that differ in the 3rd or 4th decimal. For example, I have derived 2 very different answers for CD1 that give lengths of 44.9998 & 44.9999 for an improvement of 0.0001 in the gap. Small changes in logic can drastically change the derived results.

Rounding & data conversion in kixtart can be bizarre & unpredictable.


Sealeopard
(KiX Master)
2003-03-15 02:34 AM
Re: KiXtart Golf: CD Sorter

Theoretically, you wouldn't have any rounding issues as all datasets have foru decimal places and simple add/subtract operations won't change the number of significant decimal places.

However, since the numbers are displayed in binary fashion, you incur +/- EPS in precision for each number. EPS is the smallest number that can be expressed in the number format used. EPS for integers is e.g. 1. So, even add/subtract introduce very small round-off errors whcih should be in the order of maybe 1E-16. I would not expect to see round-off errors in the fourth digit.


LonkeroAdministrator
(KiX Master Guru)
2003-03-15 03:39 AM
Re: KiXtart Golf: CD Sorter

Average CD Length = 44.83
Average Gap = 0.17
Average Gap [%] = 0.39

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 797 MHz
Memory = 375 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/14 20:46:06.287
Processing End = 2003/03/14 21:25:02.276
Duration = 0000/00/00 00:38:55.989
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 2
KiXGolf Result = Valid CD Filling
KiXGolf Score = 244

Thank you for participating in KiXtart Golf!


Howard Bullock
(KiX Supporter)
2003-03-15 09:45 AM
Re: KiXtart Golf: CD Sorter

Trying to track this down:

On the 12th CD:
quote:

CDSorter = 3,6,26,33,39,40,46,50,88,92

ERROR : array reference out of bounds!
Script: C:\Data\Scripts\Golf\kixgolf_cd\kixgolf_cd.kix
Line : 127

Not sure what's up.


Howard Bullock
(KiX Supporter)
2003-03-15 10:38 AM
Re: KiXtart Golf: CD Sorter

My first good code. Why are you guys NOT looping 100x?

code:
Average CD Length = 44.39
Average Gap = 0.61
Average Gap [%] = 1.36

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 848 MHz
Memory = 511 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/15 04:06:35.974
Processing End = 2003/03/15 04:42:04.287
Duration = 0000/00/00 00:35:28.313
# Loops = 100
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 360

Thank you for participating in KiXtart Golf!



[ 15. March 2003, 11:09: Message edited by: Howard Bullock ]


Howard Bullock
(KiX Supporter)
2003-03-15 11:12 AM
Re: KiXtart Golf: CD Sorter

Yahoo! [Big Grin] Was 244 the best so far?

code:
Average CD Length = 44.38
Average Gap = 0.62
Average Gap [%] = 1.37

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 848 MHz
Memory = 511 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/15 05:14:08.576
Processing End = 2003/03/15 05:14:21.365
Duration = 0000/00/00 00:00:12.789
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 222

Thank you for participating in KiXtart Golf!



Howard Bullock
(KiX Supporter)
2003-03-15 11:25 AM
Re: KiXtart Golf: CD Sorter

code:
Average CD Length = 44.39
Average Gap = 0.61
Average Gap [%] = 1.36

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 848 MHz
Memory = 511 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/15 05:53:43.338
Processing End = 2003/03/15 05:53:54.075
Duration = 0000/00/00 00:00:10.737
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 214

Thank you for participating in KiXtart Golf!



[ 15. March 2003, 11:48: Message edited by: Howard Bullock ]


LonkeroAdministrator
(KiX Master Guru)
2003-03-16 12:27 AM
Re: KiXtart Golf: CD Sorter

no, it wasn't, but that doesn't matter anymore...
quess I need to make myself totally new code...


Jack Lothian
(MM club member)
2003-03-15 05:06 PM
Re: KiXtart Golf: CD Sorter

I believe data conversion is my main problem. I just can't seem to find a way to force Kixtart to treat the gap variable as a double precision number throughout my routine. It seems that during function calls, kixtart does its own internal data format conversions & this conversion is not fixed but rather based upon the actual values in the arrays.

Howard Bullock
(KiX Supporter)
2003-03-15 05:40 PM
Re: KiXtart Golf: CD Sorter

[Cool] [Razz]
It's getting harder to reduce the size. Still looking though [Wink]

code:
Average CD Length = 44.58
Average Gap = 0.42
Average Gap [%] = 0.93

KiXtart
KiXtart Version = 4.21 Release Candidate 1
KiXGolf Script = kixgolf_cd.kix

Computer
OS = Windows 2000 Professional
CPU = Intel Pentium III
Speed = 848 MHz
Memory = 511 MB

KiXGolf Scoring Engine
Scoring Engine = 3.0.3

KiXtart Golf Score
Tournament = KiXtart Golf: CD Sorter
Processing Start = 2003/03/15 11:43:56.249
Processing End = 2003/03/15 11:44:05.463
Duration = 0000/00/00 00:00:09.213
# Loops = 1
# Processed CDs = 12
# Valid CDs = 12
# Full CDs = 0
KiXGolf Result = Valid CD Filling
KiXGolf Score = 207

Thank you for participating in KiXtart Golf!



Sealeopard
(KiX Master)
2003-03-15 08:17 PM
Re: KiXtart Golf: CD Sorter

Is anybody using plain old integers? Just remove the dots in the numbers and you don't have to worry about conversions
code:
$a='1.234'
$a=val(join(split($a,'.')))

As you only need to return the index numbers it's not really important whether you wourk with doubels or integers.

[ 15. March 2003, 20:18: Message edited by: sealeopard ]


Howard Bullock
(KiX Supporter)
2003-03-15 08:41 PM
Re: KiXtart Golf: CD Sorter

Jens, should we post the result file of 100 loops with the code for Phase #2?

Sealeopard
(KiX Master)
2003-03-15 08:43 PM
Re: KiXtart Golf: CD Sorter

Howard, it's not really necessary as the processing times will indicate how long a 100-loop run would take.

Sealeopard
(KiX Master)
2003-03-16 12:38 AM
Re: KiXtart Golf: CD Sorter

Results of the first round of KiXGolf - CD Sorter:

Best published score: 207 by Howard Bullock

Scoring Timeline (top line is most recent post):
207 = Howard
214 = Howard
360 = Howard
244 = Lonkero
245 = Lonkero
230 = Maciep
239 = Maciep
279 = Richard
248 = Lonkero
256 = Lonkero
249 = Maciep
278 = Lonkero
278 = Maciep
297 = Maciep
367 = Maciep
283 = Richard
737 = Maciep