The stupid question is the question not asked PerlMonks

### Comment on

 Need Help??

I was sent the following answer to the puzzle with the following challenge:

• Why does this work
• How efficient is is. i.e., how fast it calculates group_cats(50, 1..150) -- with the caveat that it might not be that efficient in memory.

If you think you know who sent this, please do not speculate! I will neither confirm nor deny ...

```  use strict;
use Carp;
use Data::Dumper;
\$Data::Dumper::Indent = 1;
print Dumper [group_cats(3, 1..7)];

{
my @sizes;
my %ans;
sub group_cats {
(my \$num, @sizes) = @_;
%ans = ();
my (\$size, @partition) = _group_cats(\$num, 0, \$#sizes);
return @partition;
}

sub _group_cats {
my \$key = join ":", @_;
my (\$num, \$start, \$end) = @_;
if (not exists \$ans{\$key}) {
if (\$num < 1) {
\$ans{\$key} = [0];
}
elsif (1 == \$num) {
my @part = map \$sizes[\$_], \$start..\$end;
\$ans{\$key} = [sum(@part), \@part];
}
else {
my \$num_a = int(\$num/2);
my \$num_b = \$num - \$num_a;

my \$min_mid = \$start + \$num_a - 1;
my \$max_mid = \$end - \$num_b;
my \$mid = int((\$min_mid + \$max_mid)/2);
my (\$last_a, @part_a) = _group_cats(\$num_a, \$start, \$mid);
my (\$last_b, @part_b) = _group_cats(\$num_b, \$mid + 1, \$end);
my \$best = max(\$last_a, \$last_b);
my @best_part = (@part_a, @part_b);
while (\$min_mid < \$max_mid) {
if (\$last_a <= \$last_b) {
if (\$min_mid < \$mid) {
\$min_mid = \$mid;
}
else {
\$min_mid = \$mid + 1;
}
}
else {
\$max_mid = \$mid;
}
\$mid = int((\$min_mid + \$max_mid)/2);
(\$last_a, @part_a) = _group_cats(\$num_a, \$start, \$mid);
(\$last_b, @part_b) = _group_cats(\$num_b, \$mid + 1, \$end);
if (max(\$last_a, \$last_b) < \$best) {
\$best = max(\$last_a, \$last_b);
@best_part = (@part_a, @part_b);
}
}
\$ans{\$key} = [\$best, @best_part];
}
}
return @{\$ans{\$key}};
}
}

sub max {
my \$max = shift;
for (@_) {
\$max = \$_ if \$max < \$_;
}
\$max;
}

sub sum {
my \$sum = 0;
\$sum += \$_ for @_;
return \$sum;
}

Cheers,
Ovid

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

In reply to Puzzle for the puzzle: Re: Puzzle... by Ovid
in thread 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!
• 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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2018-01-22 03:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (231 votes). Check out past polls.

Notices?