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 ]
_________________________
Jack