Page 3 of 9 <12345>Last »
Topic Options
#99251 - 2003-03-12 12:30 AM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
same here richard.
well, I go out and will see if it's done by evening.

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

download KiXnet

Top
#99252 - 2003-03-12 12:32 AM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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.
_________________________
!

download KiXnet

Top
#99253 - 2003-03-12 12:37 AM Re: KiXtart Golf: CD Sorter
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
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...

Top
#99254 - 2003-03-12 12:41 AM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
well, there is some cd that is a lot longer than the others.

jens, I got my loops to 5.
_________________________
!

download KiXnet

Top
#99255 - 2003-03-12 12:52 AM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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...
_________________________
!

download KiXnet

Top
#99256 - 2003-03-11 02:39 PM Re: KiXtart Golf: CD Sorter
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
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.

Top
#99257 - 2003-03-11 03:26 PM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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!
_________________________
!

download KiXnet

Top
#99258 - 2003-03-11 03:47 PM Re: KiXtart Golf: CD Sorter
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
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.

Top
#99259 - 2003-03-11 04:04 PM Re: KiXtart Golf: CD Sorter
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11163
Loc: Boston, MA, USA
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 ]
_________________________
There are two types of vessels, submarines and targets.

Top
#99260 - 2003-03-11 04:48 PM Re: KiXtart Golf: CD Sorter
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
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???
_________________________
Greetz,
Patrick Rutten

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

Top
#99261 - 2003-03-11 04:48 PM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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.
_________________________
!

download KiXnet

Top
#99262 - 2003-03-11 04:51 PM Re: KiXtart Golf: CD Sorter
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
Agreed, Am going for perfect too. Will use one loop though...
_________________________
Greetz,
Patrick Rutten

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

Top
#99263 - 2003-03-11 04:59 PM Re: KiXtart Golf: CD Sorter
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
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]

Top
#99264 - 2003-03-11 05:10 PM Re: KiXtart Golf: CD Sorter
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11163
Loc: Boston, MA, USA
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 ]
_________________________
There are two types of vessels, submarines and targets.

Top
#99265 - 2003-03-11 05:15 PM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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.
_________________________
!

download KiXnet

Top
#99266 - 2003-03-11 05:19 PM Re: KiXtart Golf: CD Sorter
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
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.

Top
#99267 - 2003-03-11 07:54 PM Re: KiXtart Golf: CD Sorter
maciep Offline
Korg Regular
*****

Registered: 2002-06-14
Posts: 947
Loc: Pittsburgh
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.
_________________________
Eric

Top
#99268 - 2003-03-11 08:13 PM Re: KiXtart Golf: CD Sorter
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11163
Loc: Boston, MA, USA
[Eek!] [Eek!] Wow! [Eek!] [Eek!]

Five optimized CDs, not bad.
_________________________
There are two types of vessels, submarines and targets.

Top
#99269 - 2003-03-11 08:25 PM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
heh.
added one small if statement and the execution time of all 100 loops was just one minute [Razz]

still, no optimized CDs.
_________________________
!

download KiXnet

Top
#99270 - 2003-03-11 09:35 PM Re: KiXtart Golf: CD Sorter
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
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?
_________________________
!

download KiXnet

Top
Page 3 of 9 <12345>Last »


Moderator:  Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 152 anonymous users online.
Newest Members
jtpk2022, Rayvenhaus, Insecurity, KGSOFT, fobrien
17791 Registered Users

Generated in 0.084 seconds in which 0.031 seconds were spent on a total of 12 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org