#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{first sum};
use Test::More;
use Time::HiRes qw{time};
use Getopt::Long;

my %opt = (
    test_more   => 1,
    time_hires  => 1,
    volume_tests        => 0,
    volume_power_max    => 3,
    array_limit => 3,
);

GetOptions(map {
    join('|' => @{[join '' => /(?>^|_)([a-z])/gi]}, $_) . ':i' => \$opt{$_}
} keys %opt);

my $test_equal_subsets = [
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [8, 4, 4, 7, 6, 3],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
    [ (1) x 100 ],
    [ 1 .. 1000 ],
];

my $test_unequal_subsets = [
    [1, 6, 2],
    [7, 5, 3, 3],
    [1, 2 ,3, 7],
    [0, 1],
    [1, 2],
    [1],
    [2],
    [8, 1, 2, 3],
    [ 1 .. 10 ],
    [ 1 .. 100 ],
];

if ($opt{volume_tests}) {
    for (1 .. $opt{volume_power_max}) {
        my @volume = map { (($_), ($_)) } 1 .. 8**$_ / 2;
        push @$test_equal_subsets, [@volume];
        push @$test_unequal_subsets, [@volume, 8**(2 * $_)];
    }
}

if ($opt{test_more}) {
    plan tests => scalar @$test_equal_subsets + scalar @$test_unequal_subsets;
}

my @expectations = ('Not expecting equal subsets.', 'Expecting equal subsets.');
my @subsets_data = ([$test_unequal_subsets, 0, 0], [$test_equal_subsets, 1, 1]);

for (@subsets_data) {
    my ($subsets, $expect_code, $expect_name_index) = @$_;
    my $expect_name = $expectations[$expect_name_index];

    for (@$subsets) {
        my $start = time if $opt{time_hires};

        if ($opt{test_more}) {
            is(check_arrays($_), $expect_code, $expect_name);
        }
        else {
            check_arrays($_);
        }

        printf "Took %f seconds\n", time() - $start if $opt{time_hires};
    }
}

sub check_arrays {
    my $full_array = shift;

    print 'Checking: (', array_string($full_array), ')';

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", array_string($full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) {
        print "\tSubsets not equal: sum of starting array is odd ($full_sum).";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my @sorted_array = sort { $b % 2 <=> $a % 2 || $b <=> $a } @$full_array;

    if (my $big = first { $_ > $half_sum } @sorted_array) {
        print "\tSubsets not equal: element ($big) larger than sum of rest.";
        return 0;
    }

    my (@a1, @a2);
    my $total = 0;

    while (@sorted_array) {
        push @a1, shift @sorted_array;
        $total += $a1[$#a1];

        @sorted_array = map { $total + $_ <= $half_sum
            ? do { push @a1, $_; $total += $_; () } : $_
        } @sorted_array;

        if ($total == $half_sum) {
            (@a2, @sorted_array) = (@a2, @sorted_array);
        }
        else {
            push @a2, pop @a1 if @a1;
        }
    }

    if ($total == $half_sum) {
        print "\tSubsets: (", array_string([sort { $a <=> $b } @a1]), ')';
        print "\t     and (", array_string([sort { $a <=> $b } @a2]), ')';
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal: no solution found.";
        return 0
    }
}

sub array_string {
    my $array = shift;

    return join(', ' => @$array > 3 * $opt{array_limit}
        ? ( @$array[0 .. $opt{array_limit} - 1],
            " ... [snip: @{[@$array - 2 * $opt{array_limit}]} elements] ...",
            @$array[@$array - $opt{array_limit} .. $#$array] )
        : @$array);
}