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

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


No such thing as a small change
	PerlMonks