Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

I've wound up with a bit of a tricky and ugly code that I need to make more flexible. The problem: We have a client who displays their products on our Web site. These products are divided into several categories that are displayed in multiple columns. Here are the rules:

  • Six categories distributed across four columns
  • The categories must remain in order
  • No column may be empty
  • A category and its list of products must not span columns
  • The total height of the resulting table must be the lowest possible amount (multiple solutions may satisfy this, but it doesn't matter which is chosen)

For example, let's say I have categories one through six with these respective heights (number of products):

my @height = qw/ 10 15 25 30 10 13 /;

With that, I might have those categories distributed as follows (pretending that the index starts with 1 instead of zero):

  Column 1 Column 2 Column 3 Column 4
Categories: 1 3 4 5
Categories: 2     6
Height: 25 25 30 23

The following code will accurately determine that, noting that I need to sort the actual values in each column. Further, it takes into account that the 1st and 6th category will always be in columns 1 and 4, respectively. Each for loop is iterating over a subsequent category with the indices being the only allowable values for a category (the second category is $a and cannot possibly be in column 3 because that would leave column 2 empty).

#!/usr/bin/perl -w use strict; use Data::Dumper; my @height = qw/ 10 15 25 30 10 13 /; my @columns = ($height[0],0,0,$height[-1]); my $curr_height = 0; # set this unreasonably high to ensure that subsequent # heights will be lower $curr_height += $_ foreach @height; my @distribution = ([1],[],[],[6]); for my $a (0..1) { $columns[$a] += $height[1]; for my $b (0..2) { $columns[$b] += $height[2]; for my $c (1..3) { $columns[$c] += $height[3]; for my $d (2..3) { $columns[$d] += $height[4]; my $this_height = ( sort @columns )[-1]; my $valid_dist; foreach ( @columns ) { $valid_dist = $_; last if ! $valid_dist; } if ( $valid_dist and $this_height < $curr_height ) { $curr_height = $this_height; push @{$distribution[$a]}, 2; push @{$distribution[$b]}, 3; push @{$distribution[$c]}, 4; push @{$distribution[$d]}, 5; } $columns[$d] -= $height[4]; } $columns[$c] -= $height[3]; } $columns[$b] -= $height[2]; } $columns[$a] -= $height[1]; } print Dumper \@distribution;

That code results in 121 iterations. Some possibilities are skipped by last if ! $valid_dist because the for loops that I have written sometimes allow for invalid combinations (if the 5th category ($d) is in the fourth column, the 4th category cannot be in the second column because that would leave the third column empty).

My real problem: the client dictates changes to the Web site faster than a jackrabbit ... uh, never mind ... you get the idea.

Essentially, this used to be two columns. It's now four. It may turn into three columns. We may have another category added or removed. My code snippet works, but if the client changes his mind again, it would be nice to simply have the code work. Any suggestions?

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.


In reply to Puzzle: need a more general algorithm by Ovid

Title:
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!
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            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?
    Username:
    Password:

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

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (14)
    As of 2014-12-19 09:42 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (76 votes), past polls