Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Balance columns

by merlyn (Sage)
on Jul 12, 2002 at 00:02 UTC ( #181180=sourcecode: print w/replies, xml ) Need Help??
Category: Miscellaneous
Author/Contact Info Randal L. Schwartz (merlyn)
Description: Ovid recently posed a puzzle about how to minimize the text in an HTML table. While many solutions had been posed, I kinda like the way I finally solved it while sitting in a recent meeting of the group when I should have been listening to chromatic give his talk.

use List::Util qw(sum max);

use Memoize;

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

my ($maxheight, @cols) = make_cols($cols, @height);

print "max height is $maxheight\n";
print join(" ", map "[@$_]", @cols), "\n";

sub make_cols {
  my ($cols, @height) = @_;
  my $warnmsg = "computing for $cols cols with @height =>";

  ## non-recursive case:
  if ($cols <= 1) {
    warn "$warnmsg returning trivial [@height]\n";
    return sum(@height), [@height] if $cols <= 1;

  ## oops, work to do.  Search for a pivot.
  ## first, get a trial solution:

  my @leftcol = shift @height;
  my ($rightmax, @rightcols) = make_cols($cols-1, @height);
  my @best = (max(sum(@leftcol), $rightmax), [@leftcol], @rightcols);

  ## now iterate until we are producing worse solutions:
  while (@height > $cols - 1) {
    push @leftcol, shift @height;
    my ($rightmax, @rightcols) = make_cols($cols-1, @height);
    my @try = (max(sum(@leftcol), $rightmax), [@leftcol], @rightcols);
    next if $try[0] >= $best[0]; # that's worse
    @best = @try;

  warn "$warnmsg returning", map(" [@$_]", @best[1..$#best]), "\n";
  return @best;
Replies are listed 'Best First'.
Re: Balance columns
by Anonymous Monk on Jul 13, 2002 at 17:11 UTC
    You know that funny feeling you get when you realize that you (and others) have just wasted a tremendous amount of energy on slow, bad solutions when there is an easy but obviously correct way to do this out there?

    You may be about to feel that. I certainly did when I realized the right way to tackle this problem.

    Do you agree that if we but knew the right height, it would be easy to compute the answer? The problem is that we don't know the right height, so we go through huge contortions to calculate it without knowing the height. But what if we just try to find the right height? How? Well just get an upper and lower bound then walk them together. Obvious innit? But this is the kind of problem that isn't seen much outside of algorithms courses we never use again.

    #! /usr/bin/perl -w use strict; my $debug = 1; my $c = shift(@ARGV) || 50; my @s = @ARGV ? @ARGV : 1..150; print "--@$_\n" for group_to_count($c, @s); sub group_to_count { my ($count, @sizes) = @_; print "Trying to find where to start my search\n" if $debug; my $lower_bound = my $upper_bound = max(@sizes); my @best = group_at_height($upper_bound, @sizes); shift(@best); shift(@best); while ($count < @best) { $lower_bound = $upper_bound; $upper_bound += $upper_bound; (my $from, my $to, @best) = group_at_height($upper_bound, @sizes); } print "Trying to narrow in to the best answer\n" if $debug; while ($lower_bound < $upper_bound) { my ($from, $to, @try) = group_at_height(($upper_bound + $lower_bound)/2, @sizes); if ($count < @try) { $lower_bound = $to; } else { @best = @try; $upper_bound = $from; } } # Ovid's spec said all buckets need something. :-( my @fix; while (@fix + @best < $count) { my $elem = shift @best; push @fix, [shift @$elem]; unshift @best, $elem if @$elem; } print "Done\n" if $debug; <STDIN> if 2 == $debug; return @fix, @best; } sub group_at_height { my ($max_h, @sizes) = @_; my @groups = my $cur_group = []; my $from = my $cur_h = 0; my $to = $max_h; for (@sizes) { $cur_h += $_; if ($max_h < $cur_h) { $to = $cur_h if $cur_h < $to or $to == $max_h; $cur_h = $_; $cur_group = [$_]; push @groups, $cur_group; } else { $from = $cur_h if $from < $cur_h; push @$cur_group, $_; } } my $count = @groups; print " Grouping to height $max_h gave $count groups\n" if $debug; print " Would get this grouping for $from to $to\n" if $debug; <STDIN> if 2 == $debug; return $from, $to, @groups; } sub max { my $m = shift; for (@_) { $m = $_ if $m < $_; } return $m; }
    (Ovid's example not used because that is solved on the first iteration so the logic is not demonstrated.)
Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: sourcecode [id://181180]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (4)
As of 2017-05-30 05:54 GMT
Find Nodes?
    Voting Booth?