Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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)

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

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others browsing the Monastery: (2)
    As of 2021-02-25 03:07 GMT
    Find Nodes?
      Voting Booth?

      No recent polls found