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)