C++, timetabling data, bin picking algorithm

[f0rd]

I am trying to create C++ application that takes information from a text file (mainly a csv file from excel), performs some basic math, then sorts the data, puts it into a list, to a a text file again.

What I am having problems with is the sorting the data into a list.

The detail; the text file contains information on sound files such as their title, duration (in seconds), minium total time to be played (in minutes).

So they text file looks like:

Sound1, 120, 10
Sound2, 30, 6
Sound3, 60, 20
Sound3, 15, 8

And so on...

Take 'Sound1' for example, the length of each sample is 120 seconds and the minimum time to be played is 10 minutes, so basic maths 10*60/120 gives the number of instances the song is to be played, in this case 5. For 'Sound'2 the number of instances is 12, for 'Sound3' 20, get the picture?

Heres where I having problem:

The running list I need to create is a exactly 60 minutes, with each sample played the by the minimum number of instances, but spread out equally from each other; so there will never be a period where for example Sound2 is played twice in a row.

Secondly, if the minium instances of each song has been used, and there is still time with in the 60 min, how is it possible to tell it to go back and fill the time by selecting each sound and including it till the 60 min is filled, I imagine using some sort of loop and count function, but I wouldn't know how to do it with the list.

I can include source of what I have, although it isn't much, mainly just reading from the csv file and scanning with a formatted string.

Any ideas? I'd imagine this is pretty simple if you know what you are doing.

[weaknessforcats]

This doesn't look that hard. Probably becuse I don't fully understand. But it looks like you can fill your list and from that to have the total time. Say 50 minutes.

I would guess you could calculate 60 - 50 and come up with 10 minutes of slack time.

Next, loop through your list. If the song is 120 seconds, I would guess you could add one repetition and reduce your slack time by 2 minutes, leaving you with 8. Advancve ot the next element in the list and do the same.When the slack time goes to 0 you are done. If you make through the entire list and there is still slack time, the start the array loop over.

[f0rd]

You mean something like:

bool Flag;
int Total_Time, 

do {
if (Count<Sound1_MinimumInstance)
{ "Sound";
Total_time=Total_time+Time_of_Sound1;
Flag=True;
} 
else if (Count<Sound1_MinimumInstance)
{
"Sound 2"
Total_time=Total_time+Time_of_Sound2;
Flag=True;
}

//etc 

Count++;
if (Flag==false)
Count=0;

Flag=false; 
}while (Total_Time<3600)

However it seems like a pain in the ass hard coding each instance.

Just for the sake of ease give the sample letters and the number is that of frequency.

So:

A - 7
B - 4
C - 5

No I would imagine the need to be put into a linear array and make sure sparsely placed as possible.

So place them into an array:

step 1 : A A A A A A A

Then place the second highest frequency in between the A's so:

step 2 : A C A C A C A C A C A A

However there is two adjacent As at then end.

So the Bs need to be placed in between the adjacent As

A C A C A C A C A C A B A

And then distribute the Bs equally

B A C A B C A C A B C A C A B A

All well and good in theory, but I'm not sure how to implement it, ideas?

[whodgson]

There seems to be a error in the logic in as much as the time available is a non negotiable 3600 seconds. Therefore the sum of the playing times must == this.
The reminder of the list (unpublished) therefor must sum to a further 16 minutes
Or are you saying that the sum of the list playing time exceed this and and you want the program to pick from the list to respect required playing time and therefore designated play frequency to exactly achieve the 60 minutes?

[jkmyoung]

With your current algorithm, you play:
Sound1, 5 times
Sound2, 12 times
Sound3, 20 times
Sound4, 32 times.
Your total time is 50 minutes.

If you don't have to end exactly on 60 minutes, you could just start replay of the first 50 minutes over again (assuming you don't start and end on the same sound; set it up this way). Or, even if you do have to end exactly on 60 minutes, you could check to see if there is a break after the first 10 mins of the 50 minute list.

Do you want the relative frequency of the songs to stay the same? It would be easier just to add Sound1 5 more times, to even out the frequencies.

[jkmyoung]

Let's use
Sound1, 10 times
Sound2, 12 times
Sound3, 20 times
Sound4, 32 times.

Suggestion for an approximate algorithm.
For each sound, take # of occurrences, n.
Divide by total time T = 3600.
So for sound 1, T/n = 3600/10 = 360. This sound occurs approximately once every 360 seconds.
Divide in half to get the approximate first starting time.
T/n/2 = 180.
Then add T/n to get the rest of it's approximate start times.
Sound1, 180 540 900 1260 1620 1980 2340 2700 3060 3420

Do this for the other sounds.
Create a sorted array, based on these numbers.
Step through the array, (sort of like a bubble sort) to make sure that 2 of the same elements are not next to each other. (will only be the highest frequency elements, sound4) If there are, say at indexes i, i+1, then first check elements i-1, and i-2. If they are both not sound4, then swap the sound4 and index i, with the other sound at i-1.

So we originally have:
DCBDACDDBCDADCD BCDADCBDCDADBCD DCADBCDDCBDACDD BCDADCDBCDADCBD CDADBCDDCADBCD
(5 doubles)
And after shifting, we get:
DCBDADCDBCDADCD BCDADCBDCDADBDC DCADBDCDCBDADCD BCDADCDBCDADCBD CDADBDCDCADBCD