#99211 - 2003-03-08 09:40 PM
KiXtart Golf: CD Sorter
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
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]](images/icons/grin.gif)
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.
=============
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 ]
_________________________
There are two types of vessels, submarines and targets.
|
|
Top
|
|
|
|
|
#99226 - 2003-03-10 03:38 PM
Re: KiXtart Golf: CD Sorter
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
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
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]](images/icons/wink.gif) Might cut down on keystrokes, though, as you don't need to convert things to floats.
_________________________
There are two types of vessels, submarines and targets.
|
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 370 anonymous users online.
|
|
|
![[Mad]](images/icons/mad.gif){kind=icon}
![[Razz]](images/icons/tongue.gif){kind=icon}
