c:\test>708290-b -LOG=4 -MAX=1e3
Testing buk    with    10 random values in the range 0 .. 1e3 Difference:=     1; took 0.000244 seconds
Testing funky  with    10 random values in the range 0 .. 1e3 Difference:=    65; took 0.000118 seconds
Testing tilly  with    10 random values in the range 0 .. 1e3 Difference:=     1; took 0.004491 seconds
Testing tye    with    10 random values in the range 0 .. 1e3 Difference:=     1; took 0.001024 seconds

Testing buk    with   100 random values in the range 0 .. 1e3 Difference:=     1; took 0.005047 seconds
Testing funky  with   100 random values in the range 0 .. 1e3 Difference:=     1; took 0.000587 seconds
Testing tilly  with   100 random values in the range 0 .. 1e3 Difference:=     1; took 15.174596 seconds
Testing tye    with   100 random values in the range 0 .. 1e3           ******* timed out after 60 seconds

Testing buk    with  1000 random values in the range 0 .. 1e3 Difference:=     1; took 0.015625 seconds
Testing funky  with  1000 random values in the range 0 .. 1e3 Difference:=     1; took 0.007535 seconds
Testing tilly  with  1000 random values in the range 0 .. 1e3           ******* timed out after 60 seconds
Testing tye    with  1000 random values in the range 0 .. 1e3           ******* timed out after 60 seconds

Testing buk    with 10000 random values in the range 0 .. 1e3 Difference:=     1; took 0.075423 seconds
Testing funky  with 10000 random values in the range 0 .. 1e3 Difference:=     1; took 0.190954 seconds
Testing tilly  with 10000 random values in the range 0 .. 1e3           ******* timed out after 60 seconds
Testing tye    with 10000 random values in the range 0 .. 1e3           ******* timed out after 60 seconds

c:\test>708290-b -LOG=4 -MAX=1e4
Testing buk    with    10 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.000326 seconds
Testing funky  with    10 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.000102 seconds
Testing tilly  with    10 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.003578 seconds
Testing tye    with    10 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.001063 seconds

Testing buk    with   100 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.044324 seconds
Testing funky  with   100 random valuesin the range 0 .. 1e4 Difference:=     7; took 0.000601 seconds
Testing tilly  with   100 random valuesin the range 0 .. 1e4 Difference:=     1; took 15.901730 seconds
Testing tye    with   100 random valuesin the range 0 .. 1e4            ******* timed out after 60 seconds

Testing buk    with  1000 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.515625 seconds
Testing funky  with  1000 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.008393 seconds
Testing tilly  with  1000 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.013012 seconds
Testing tye    with  1000 random valuesin the range 0 .. 1e4 Difference:= 92467; took 0.016869 seconds

Testing buk    with 10000 random valuesin the range 0 .. 1e4 Difference:=     0; took 4.654061 seconds
Testing funky  with 10000 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.136925 seconds
Testing tilly  with 10000 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.148673 seconds
Testing tye    with 10000 random valuesin the range 0 .. 1e4 Difference:= 2252553; took 1.632284 seconds

c:\test>708290-b -LOG=4 -MAX=1e4
Testing buk    with    10 random valuesin the range 0 .. 1e4 Difference:=     2; took 0.003548 seconds
Testing funky  with    10 random valuesin the range 0 .. 1e4 Difference:=   198; took 0.000107 seconds
Testing tilly  with    10 random valuesin the range 0 .. 1e4 Difference:=     2; took 0.003799 seconds
Testing tye    with    10 random valuesin the range 0 .. 1e4 Difference:=     2; took 0.001117 seconds

Testing buk    with   100 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.213406 seconds
Testing funky  with   100 random valuesin the range 0 .. 1e4 Difference:=     2; took 0.000587 seconds
Testing tilly  with   100 random valuesin the range 0 .. 1e4 Difference:=     0; took 0.003341 seconds
Testing tye    with   100 random valuesin the range 0 .. 1e4 Difference:=  1282; took 0.001121 seconds

Testing buk    with  1000 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.007796 seconds
Testing funky  with  1000 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.007606 seconds
Testing tilly  with  1000 random valuesin the range 0 .. 1e4            ******* timed out after 60 seconds
Testing tye    with  1000 random valuesin the range 0 .. 1e4            ******* timed out after 60 seconds

Testing buk    with 10000 random valuesin the range 0 .. 1e4 Difference:=     1; took 4.281250 seconds
Testing funky  with 10000 random valuesin the range 0 .. 1e4 Difference:=     1; took 0.150492 seconds
Testing tilly  with 10000 random valuesin the range 0 .. 1e4            ******* timed out after 60 seconds
Testing tye    with 10000 random valuesin the range 0 .. 1e4            ******* timed out after 60 seconds


##</code><code>##

#! perl -slw
use strict;
use List::Util qw[ shuffle sum ];
use List::MoreUtils qw(first_index);
use Time::HiRes qw[ time ];

our $MAX    ||= 1e4;    ## Maximum random values
our $V      ||= 0;      ## Causes the partitions to be printed
our $LOG    ||= 4;      ## No of logarithmic steps;
                        ## 4 means 10, 100, 100, 10000

my %tests = (
    buk     => sub { return buk( 20 * @{ $_[0] }, $_[0] ); },
    funky   => sub { return FunkyMonk( $_[ 0 ] ); },
    tilly   => sub { return tilly( @{ $_[ 0 ] } ); },
    tye     => sub {
        my @part1 = tye( @{ $_[ 0 ] } );

        my %seen; $seen{ $_ }++ for @part1;
        my @part2 = grep !$seen{ $_ }--, @{ $_[ 0 ] };

        return( \@part1, \@part2 );
     },
);

for my $n ( map 0+"1e$_", 1 .. $LOG ) {
    my @data = map int( rand 1e3 ), 1 .. $n;
    for my $test ( sort keys %tests ) {
        printf "Testing %-6s with %5d random values"
              . "in the range 0 .. $MAX ",
            $test, $n;
        my( $part1, $part2 );
        my( $start, $stop );
        eval {
            $SIG{ALRM} = sub{ die };
            alarm( 60 );
            $start = time();
            ( $part1, $part2 ) = $tests{ $test }->( \@data );
            $stop = time();
            alarm( 0 )
        };
        print "\t\t******* timed out after 60 seconds"
            and next if $@;
        my $t1 = sum @$part1;
        my $t2 = sum @$part2;

        print "\n[@$part1] := $t1" if $V;
        print "[@$part2] := $t2" if $V;
        printf "Difference:= %5d; took %f seconds\n",
            abs( $t1 - $t2 ), $stop - $start;
    }
    print '';
}

sub FunkyMonk {
    my @numbers = reverse sort { $a <=> $b } @{+shift};
    my $target = sum(@numbers) / 2;

    my @b;
    while ( 1 ) {
        my $index = first_index { $_ <= $target } @numbers;
        last if $index < 0;
        $target -= $numbers[$index];
        push @b, splice @numbers, $index, 1;
    }
    return \@b, \@numbers;
}

sub tye {
    my @weights= sort { $b <=> $a } @_;
    my $dist= 0;
    $dist += $_ for @weights;
    $dist /= 2;
    my $best= $dist;
    my @sol;
    my @idx= ( 0 );
    while( 1 ) {
        $dist -= $weights[$idx[-1]];
        for( abs($dist) ) {
            if( $_ < $best ) {
                $best= $_;
                @sol= @idx;
                return @weights[ @sol ]
                    if( 0 == $_ );
            }
        }
        if( 0 < $dist ) {
            push @idx, 1 + $idx[-1]
        } else {
            $dist += $weights[ $idx[-1]++ ];
        }
        while( @weights <= $idx[-1] ) {
            pop @idx;
            return @weights[ @sol ]
                if( 1 == @idx );
            $dist += $weights[ $idx[-1]++ ];
        }
    }
}

sub buk {
    my( $limit, $aRef ) = @_;
    my @in = sort{ $a <=> $b } @$aRef;
    my $target = sum( @in ) >> 1;
    my( $best, @best ) = 9e99;
    my $soFar = 0;
    my @half;
    for( 1 .. $limit ) {
        #print "$soFar : [@half] [@in] [@best]"; <>;
        $soFar += $in[ 0 ], push @half, shift @in
            while $soFar < $target;
        return( \@half, \@in ) if $soFar == $target;

        my $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        $soFar -= $half[ 0 ], push @in, shift @half
            while $soFar > $target;
        return( \@half, \@in ) if $soFar == $target;

        $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        @in = shuffle @in;
    }
    my %seen; $seen{ $_ }++ for @best;
    return \@best, [ grep !$seen{ $_ }--, @$aRef ];
}

sub tilly {
  my @numbers = sort {abs($b) <=> abs($a) or $a <=> $b} @_;

  # First we're going to find a "pretty good" partition.
  # If we can, we'll look for a partition that finishes off
  # like this one does.  That can short-cut the full
  # algorithm.
  my @in_partition;
  my $current_remaining = 0;
  for my $n (@numbers) {
    if ($current_remaining < 0) {
      if ($n > 0) {
        push @in_partition, 1;
        $current_remaining += $n;
      }
      else {
        push @in_partition, 0;
        $current_remaining -= $n;
      }
    }
    else {
      if ($n > 0) {
        push @in_partition, 0;
        $current_remaining -= $n;
      }
      else {
        push @in_partition, 1;
        $current_remaining += $n;
      }
    }
  }

  my $known_solution = $current_remaining;

  # Cheat, we're going to find out the extremes.
  my @max_sum_of_previous = 0;
  my $sum = 0;
  for my $n (@numbers) {
    $sum += abs($n);
    push @max_sum_of_previous, $sum;
  }

  # We're going to try to find partitions that add up to
  # each possible number that can be added up to.
  my $old;
  my $new = {0 => [[], []]};

  my $i = -1;
  my $answer;
N:  for my $n (@numbers) {
    $old = $new;
    $new = {};
    $i++;

    while (my ($key, $value) = each %$old) {
      if ($key == -$current_remaining) {
        # We've found our match!
        $answer = $value;
        last N;
      }

      if (
        abs($key)
          > $sum - $max_sum_of_previous[$i] + abs($known_solution)
      ) {
        # We're too far away from 0 to possibly beat the
        # "pretty good" partition.  So skip.
        next;
      }

      my ($p1, $p2) = @$value;
      $new->{$key + $n} ||= [[$n, $p1], $p2];
      $new->{$key - $n} ||= [$p1, [$n, $p2]];
    }

    # Adjust $current_remaining for the fact we're skipping
    # the $i'th element.
    if ($in_partition[$i]) {
      $current_remaining -= $n;
    }
    else {
      $current_remaining += $n;
    }
  }

  if (not $answer) {
    $i++; # We need to not append the tail!
    my $best = each %$new;

    while (my $difference = each %$new) {
      if (abs($difference) < abs($best)) {
        $best = $difference;
      }
    }

    $answer = $new->{$best};
  }

  # We need to flatten our nested arrays and add the tail.
  my ($p1, $p2) = @$answer;

  my @part_1;
  while (@$p1) {
    push @part_1, $p1->[0];
    $p1 = $p1->[1];
  }
  push @part_1
    , map {
        $in_partition[$_] ? $numbers[$_] : ()
      } $i..$#numbers;

  my @part_2;
  while (@$p2) {
    push @part_2, $p2->[0];
    $p2 = $p2->[1];
  }
  push @part_2
    , map {
        $in_partition[$_] ? () : $numbers[$_]
      } $i..$#numbers;

  return (\@part_1, \@part_2);
}