comment on

After collecting lots of MP3 recordings of radio audio-plays, I think it is time to clean up my harddisk and burn them to CD-Rs. Of course, I want to fill each CD as much as possible. Task for the Perl programm is, to tell me which files I have to burn together on one CD-R.

The 'du' command gives me a list of file/directory sizes, which I clean up manually, that is drop subdirectories etc. This list is read into a list called @files, which contains pairs of size and name. I sort this one, for the biggest directories first. Now I call my little subroutine TrySolution, which finds out the combinations of files sums up to the closest value of space available on a CD-R. The solution is thrown out of the @files list and TrySolution is started again for the next solution as long as entries are left in @files.

Sounds easy, but do you remember all those nifty algorithms from your university times and do they fit? I didn't, but this was a nice exercise. The solution is still not optimal, but reasonably fast, e.g. you could stop the recursive call, if you can exclude impossible branches. And it was fun.

But when I finished and was proud about the fantastic combinations found, I suddenly recognized, that I asked the wrong question. I asked for filling each CD to a maximum, I should have asked to fille as little CDs as possible. But that is another question ;-)

Read below for the main parts of my script:

# Global variables
my @files;                    # Array of (Size,Name)
my $nr_entries = 0;           # Anzahl gefundener Dateien
my @opt_solution_sizes;       # sizes of current opt. combination 
my @opt_solution_idx;         # indices of current opt. combination 
my $opt_solution_tot;         # size of current opt. combination 

# Read files and sort biggest first
open F, "<$filename" 
    or die "Cannot open $filename\n$!";
while (my $line = <F>)
{
    chomp $line;
    my ($size, $name) = split /\s+/, $line, 2;
    push @files, [$size, $name];
    $nr_entries++;
}
close F;
@files = sort {$$b[0] <=> $$a[0]} @files;


sub TrySolution
{
    my $stufe          = shift;
    my @solution_sizes = @{ $_[0] };
    my @solution_idx   = @{ $_[1] };
    my $solution_tot   = sum(@solution_sizes);

    if ( $solution_tot > $opt_solution_tot )
    {
        # new Optimum
        @opt_solution_sizes = @solution_sizes;
        @opt_solution_idx   = @solution_idx;
        $opt_solution_tot   = sum(@opt_solution_sizes);
    }

    if ($stufe==$nr_entries)
    {   # last entry
        return;
    }

    # retry, for all entries, that can give possible solutions
    for my $try ( $stufe..($nr_entries-1) )
    {   
        my $try_size = $files[$try]->[0];
        if ( $solution_tot+$try_size < $options{cdsize})
        {
            # If possible, then try with extended set
            TrySolution ( $try+1, 
                      [@solution_sizes, $try_size], 
                      [@solution_idx, $try] );
        }
    }
}


# Main
while (@files)
{
    my @new_set = ();
    @opt_solution_sizes = ();
    @opt_solution_idx   = ();
    $opt_solution_tot  = 0;

    TrySolution (0, [], [] );
    print "Optimal solution is $opt_solution_tot with ", 
           commify_series (@opt_solution_sizes), "\n"; 
    # see Perl Cookbook for commify_series, nice string out of list

    @new_set = ();
    foreach my $idx ( reverse @opt_solution_idx)
    {   # start from end, if array is cut in the middle
        unshift @new_set, splice @files, $idx, 1;
        $nr_entries--;     # global counter, left input list entries
    }
    # Now output result
    print "\nNext Set is:\n", '-' x 10, "\n";
    for (my $i=0; $i < @new_set; $i++) 
    { 
        printf "%2d) [%3d] %s\n", 
               $i, $new_set[$i]->[0], $new_set[$i]->[1]; 
    }
    print "\n";
}
[download]

And it came to pass that in time the Great God Om spake unto Brutha, the Chosen One: "Psst!"
(Terry Pratchett, Small Gods)

In reply to Distribute MP3 recordings optimally to CD-Rs by Brutha

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.


Problems? Is your data what you think it is?
	PerlMonks