#!/usr/bin/perl

use strict;
use warnings;

my $num_columns = 4;
my @cat = (15, 15, 10, 10, 15, 15);

my @ans = squish(@cat);
print "@ans\n";

sub squish {
  my @arr = @_;
  my @aoa = (\@arr);
  for ($num_columns..(@arr-1)) {
    my @tmp_aoa;
    push @tmp_aoa, squisher(@$_) for @aoa;
    @aoa = @tmp_aoa;
  }
  my $best_ans;
  my $best_value;
  for my $aref (@aoa) {
    my $max_value;
    for my $value (@$aref) {
      $max_value = $value if !defined $max_value or $value > $max_value;
    }
    $best_ans = $aref, $best_value = $max_value
      if !defined $best_value or $max_value < $best_value;
  }
  @$best_ans;
}

sub squisher {
  my @arr = @_;
  my $min_col;
  my $min_value;
  for (0..$#arr) {
    $min_value = $arr[$_], $min_col = $_
      if !defined $min_value or $arr[$_] < $min_value;
  }
  my @arr1 = ($min_col > 0) ? @arr : ();
  my @arr2 = ($min_col < $#arr) ? @arr : ();
  splice(@arr1, $min_col-1, 2, $arr1[$min_col-1] + $arr1[$min_col])
    if @arr1;
  splice(@arr2, $min_col, 2, $arr2[$min_col] + $arr2[$min_col+1])
    if @arr2;
  return ((@arr1 ? \@arr1 : ()), (@arr2 ? \@arr2 : ()));
}