### comment on

 Need Help??
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.)

In reply to Re: Balance columns by Anonymous Monk
in thread Balance columns by merlyn

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

• 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.

Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (4)
As of 2023-03-29 19:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (72 votes). Check out past polls.

Notices?