#! /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;
}