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";
}
And it came to pass that in time the Great God Om spake unto Brutha, the Chosen One: "Psst!"
(Terry Pratchett, Small Gods)
-
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.