use warnings FATAL => 'all';
use strict;
use Getopt::Long                qw(GetOptions);
use Pod::Usage                  qw(pod2usage);
use List::Util                  qw(sum uniq reduce max);
use List::MoreUtils             qw(frequency);
use Math::Factor::XS            qw(factors);
use Algorithm::Combinatorics    qw(combinations_with_repetition);

my @combos;
my %opt;
parse_args();

print <<"EOF";

Grid size: $opt{grid}
Cage size: $opt{cage}
Operator : $opt{operator}
Number   : $opt{num}
Reject   : $opt{reject}

EOF

   if ($opt{operator} eq 'a') { addition        (); }
elsif ($opt{operator} eq 's') { subtraction     (); }
elsif ($opt{operator} eq 'm') { multiplication  (); }
elsif ($opt{operator} eq 'd') { division        (); }

show_results();
exit;


sub subtraction {
    die "ERROR: Number must be less than grid size.\n" if $opt{num} >= $opt{grid};
    die "ERROR: Number must be greater than 0.\n" if $opt{num} < 1;
    for my $i (($opt{num}+1) .. $opt{grid}) {
        push @combos, [$i, ($i - $opt{num})];
    }
}

sub division {
    die "ERROR: Number must be <= grid size.\n" if $opt{num} > $opt{grid};
    die "ERROR: Number must be greater than 1.\n" if $opt{num} < 2;
    for my $i (1 .. $opt{grid}) {
        my $mult = $i * $opt{num};
        last if $mult > $opt{grid};
        push @combos, [$mult, $i];
    }
}

sub addition {
    die "ERROR: Number must be greater than 2.\n" if $opt{num} < 3;
    my @nums = 1 .. $opt{grid};
    for my $aref (combinations_with_repetition(\@nums, $opt{cage})) {
        my @nums = @{ $aref };
        if (sum(@nums) == $opt{num}) {
            push @combos, [@nums];
        }
    }
}

sub multiplication {
    die "ERROR: Number must be greater than 1.\n" if $opt{num} < 2;
    my @factors = grep { $_ <= $opt{grid} } (1, factors($opt{num}), $opt{num});
    for my $aref (combinations_with_repetition(\@factors, $opt{cage})) {
        my @nums = @{ $aref };
        my $prod = reduce { $a * $b } @nums;
        if ($prod == $opt{num}) {
            push @combos, [@nums];
        }
    }
}

sub show_results {
    my %char = (a => '+', m => 'x', s => '-', d => '/');
    my $oper = $char{$opt{operator}};
    my $cnt = 0;
    for my $aref (@combos) {
        my @nums = @{ $aref };
        if (uniq(@nums) > 1) { # Make sure all numbers are not the same
            my %freq = frequency(@nums);
            my $max  = max(values %freq);
            if ($max < $opt{reject}) {
                print "$opt{num}$oper = ", join(" $oper ", @nums), "\n";
                $cnt++;
            }
        }
    }
    if ($cnt) {
        print "\nCombinations = $cnt\n\n";
    }
    else {
        die "ERROR: No combinations found.\n";
    }
}

sub parse_args {
    %opt = (
        operator    => 'a',
        grid        => 9,
        cage        => 2,
        num         => 8,
        reject      => 9,
    );

    GetOptions(\%opt, qw(
        help
        operator=s
        grid=i
        cage=i
        num=i
        reject=i
    )) or pod2usage();

    $opt{operator} = lc substr $opt{operator}, 0, 1;

    die "ERROR: operator must be one of [amsd]\n"  unless $opt{operator} =~ /[asmd]/;
    die "ERROR: grid must be in range 3-9\n" if ($opt{grid} < 3) or ($opt{grid} > 9);
    die "ERROR: cage size must be greater than 1\n" if $opt{cage} < 2;
    die "ERROR: cage size must be less than 10\n" if $opt{cage} > 9;
    die "ERROR: reject must be greater than 1\n" if $opt{reject} < 2;
    die "ERROR: unsupported args: @ARGV\n" if @ARGV;

    # Force cage size to 2 for subtraction/division
    $opt{cage} = 2 if $opt{operator} =~ /[sd]/;

    pod2usage(-verbose => 2) if $opt{help};
}


=head1 NAME

B<kenken> - Helper for KenKen puzzle

=head1 SYNOPSIS

kenken [options]

    Options:
    -help               Verbose help
    -operator   str     Operator [asmd] (default=a)
    -grid       int     Size of grid [3-9] (default=9): 9 means 9x9
    -cage       int     Size of cage (default=2)
    -num        int     Number shown in cage next to the operator (default=8)
    -reject     int     Reject duplicate numbers

=head1 DESCRIPTION

Helper for KenKen puzzle.  Find all possible combinations of numbers which
could be in a single cage.  This does not account for the shape of the cage;
therefore, some combinations might not be legal.

=head1 OPTIONS

All options can be abbreviated.

=over 4

=item B<-operator>

The operator must be one of the following:

    a for addition
    s for subtraction
    m for multiplication
    d for division

By default, the operator is "a" for addition. To choose a different
operator, such as multiplication, use the C<-operator> option.

    kenken -operator m

=item B<-grid>

By default, the grid is assumed to be 9x9.  Supported grid sizes are 3x3 to 9x9.
To choose another grid size, use the C<-grid> option.

    kenken -grid 3

=item B<-cage>

By default, the cage size is assumed to be 2.
To choose another cage size, use the C<-cage> option.

    kenken -cage 4

=item B<-num>

By default, the number shown in the cage next to the operator is 8
To choose another number, use the C<-num> option.

    kenken -num 25

=item B<-reject>

By default, any amount of duplicate numbers are allowed within a cage.
To control the maximum number of duplicates within a cage,
use the C<-reject> option.
For example, if a cage has 5 cells, reject all combinations which have
the same number at least 3 times:

    kenken -reject 3

=item B<-help>

Show verbose usage information.

=back

=head1 EXAMPLES

8x8 grid, 3 cells in a cage, multiplication operator, number=24,
only show unique numbers in cells:

    kenken -grid 8 -cage 3 -operator m -num 24 -reject 2

Use all defaults: 9x9 grid, 2 cells in a cage, addition operator, number=8:

    kenken

=head1 SEE ALSO

L<https://en.wikipedia.org/wiki/KenKen>

=cut