[RESOLVED] Dealing with time and filling a certain amount of time.

[sgtpepper]

Hello there,

I have a database of music in a mysql table. One field is for time of the song. Currently I have this set as total seconds but it can be any time format that would work best for what I want to do. Basically, I am looking for a way to use php/mysql to query the database and give me a list of results that would equal a total of 60 minutes.

For example it would read all of time field, calculate each field and place random results in a loop until a full 60 minutes of time has been achieved. It seems I need to place the results in an array but I am not sure how to calculate the time calculations.

Any suggestions on how I can complete this? The goal is the display a list of songs that would equal 60 minutes of listening time based on the seconds.

I appreciate your help.

[Weedpacket]

This is related to the knapsack and bin-packing problems, which in general are NP-hard...; if you want the playlist to be exactly 3600 seconds long, then it's an instance of the subset-sum problem, which is NP-complete (although faster algorithms exist for approximate solutions where you're allowed to have a wee gap at the end).

I don't see a straightforward way of doing it in the database without a stored procedure to implement something that might as well be implemented in PHP.

So, I'd read in all of pairs of songID/duration in the table into an array in PHP to serve as the songlist, and do the work there. Shuffle that songlist array.

Start with a total duration of 0 seconds, and an empty array for the playlist.
While the total duration is less than 3600 seconds, pop a song off the songlist.
If the duration of the song is less than 3600 - total duration, put the songID in the playlist, add its duration to the total duration.
Continue through the loop until you run out of songs in the songlist.

One thing you might do to speed the loop up a bit is to see what the shortest song in the songlist is; you can stop looking as soon as the gap in your one-hour playlist is smaller than that duration.

[sgtpepper]

Thanks for your thoughts on this. I understand the logic of how you would accomplish this but I not sure how to code it. Would you be able to provide a simple example?

Thanks

Weedpacket;11039913 wrote:

This is related to the knapsack and bin-packing problems, which in general are NP-hard...; if you want the playlist to be exactly 3600 seconds long, then it's an instance of the subset-sum problem, which is NP-complete (although faster algorithms exist for approximate solutions where you're allowed to have a wee gap at the end).

I don't see a straightforward way of doing it in the database without a stored procedure to implement something that might as well be implemented in PHP.

So, I'd read in all of pairs of songID/duration in the table into an array in PHP to serve as the songlist, and do the work there. Shuffle that songlist array.

Start with a total duration of 0 seconds, and an empty array for the playlist.
While the total duration is less than 3600 seconds, pop a song off the songlist.
If the duration of the song is less than 3600 - total duration, put the songID in the playlist, add its duration to the total duration.
Continue through the loop until you run out of songs in the songlist.

One thing you might do to speed the loop up a bit is to see what the shortest song in the songlist is; you can stop looking as soon as the gap in your one-hour playlist is smaller than that duration.

[Derokorian]

$aTimes = array(5,4,6,3,11,21,3,8,5);
$iMin = min($aTimes);
$iFill = 25;
$aFinal = array();
$iTotal = 0;
foreach( $aTimes as $iTime )
{
    if( $iTotal + $iTime <= $iFill )
    {
        $iTotal += $iTime;
        $aFinal[] = $iTime;
    }
    if( $iTotal == $iFill || ($iFill - $iTotal) < $iMin )
    {
        break;
    }
}
var_dump($aFinal);

This of course could be optimized because as you may see, you end up with 21/25 filled, however there is a possibility of getting exactly 25 (21 + 4)

[sgtpepper]

Thanks so much. This is working well.