use strict;
use warnings;
use experimental qw{ say postderef signatures state };

use Benchmark qw/ timeit :hireswallclock /;
use POSIX qw/ floor ceil log10 /;
use File::Spec::Functions 'catfile';
use File::Basename 'dirname';

use List::Util qw{ min max };
use Math::Combinatorics;

use Term::Table;
use Chart::Gnuplot;

my $GP = catfile dirname( $^X ), '../../c/bin/gnuplot.exe';
die unless -x $GP;              # assume Strawberry Perl

say '
*******************************
*** Math::Combinatorics *******
*******************************
';
benchmark( \&group_hero_dave_jacoby, [ 10 .. 18 ], 'logscale' );
say '
*******************************
*** Combinatorics (manual) ****
*******************************
';
benchmark( \&group_hero_e_choroba, [ 13 .. 21 ], 'logscale' );
say '
*******************************
*** Min-max (quadratic) *******
*******************************
';
benchmark( \&group_hero_jo_37, [ map $_ * 20, 1 .. 9 ], '' );
say '
*******************************
*** Faster (linear?) **********
*******************************
';
benchmark( \&group_hero_mine, [ map $_ * 400, 2 .. 10 ], '' );

sub benchmark( $coderef, $x, $logscale ) {
    my @xdata = @$x;
    my @ydata;
    for my $size ( @xdata ) {
        my $t = timeit 3, sub { $coderef-> ( 1 .. $size ) };
        push @ydata, $t-> [ 1 ] / $t-> [ -1 ];
    }

    my $table = Term::Table-> new(
        header => [ 'Array size', 'Time, sec.' ],
        rows   => [ 
            map [ $xdata[ $_ ], sprintf '%.3f', $ydata[ $_ ]], 
                0 .. $#xdata
        ],
    );
    say for $table-> render;

    my $chart = Chart::Gnuplot-> new( 
        gnuplot  => $GP,
        terminal => 'dumb size 70, 35',
    );
    my $dataset = Chart::Gnuplot::DataSet-> new(
        xdata => \@xdata,
        ydata => \@ydata,
        style => 'impulses',
    );
    my $dx = .1 * ( max( @xdata ) - min( @xdata ));
    my $dy = .1 * ( max( @ydata ) - min( @ydata ));
    $chart-> set( 
        xrange => [ -$dx + min( @xdata ), $dx + max( @xdata )],
        yrange => [ -$dy + min( @ydata ), $dy + max( @ydata )],
    );
    if ( $logscale ) {
        $chart-> set( 
            logscale => 'y', 
            yrange   => [ 
                10 ** ( -.2 + floor log10 min( @ydata )),
                10 ** (  .2 + ceil  log10 max( @ydata ))
            ],
        )
    }
    $chart-> plot2d( $dataset )
}

sub group_hero_dave_jacoby (@input) {
    my $output = 0;
    for my $c ( 1 .. scalar @input ) {
        my $comb = Math::Combinatorics->new( count => $c, data => [@input], );
        while ( my @combo = $comb->next_combination ) {
            my $min = min @combo;
            my $max = max @combo;
            my $str = $max**2 * $min;
            $output += $str;
        }
    }
    return $output;
}

sub group_hero_e_choroba(@nums) {
    my @indicator = (0) x @nums;
    $indicator[-1] = 1;
    my $sum = 0;
    while (1) {
        my @group = @nums[grep $indicator[$_], 0 .. $#nums];
        $sum += max(@group) ** 2 * min(@group);

        my $i = $#indicator;
        $indicator[$i--] = 0 while $indicator[$i];
        ++$indicator[$i];
        last if $i < 0;
    }
    return $sum
}

sub group_hero_jo_37 {
    use bigint;
    
    my @s = sort {$a <=> $b} @_;
    my $power;
    while (defined (my $min = $s[0])) {
        while (my ($offs, $max) = each @s) {
            $power += $min * $max**2 * ($offs ? 2**($offs - 1) : 1);
        }
    } continue {
        shift @s;
    }

    $power;
}

sub group_hero_mine {
    use bigint;
    
    my @nums = sort { $a <=> $b } @_;
    
    my $big = 0;
    for my $i ( 0 .. $#nums - 1 ) {
        $big += $nums[ $i ] * 2 ** ( $#nums - $i- 1 )
    }
    my $sum = 0;
    for my $i ( reverse 0 .. $#nums ) {
        $sum += ( $big + $nums[ $i ]) * $nums[ $i ] ** 2;
        $big -= $nums[ $i - 1 ];
        $big /= 2
    }
    return $sum
}