#!/usr/bin/perl
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

# Compute the partition function P(n,k) using the recurrence
# relation:  P(n,k) = P(n-1,k-1) + P(n-k,k)
# Use this to solve the challenge Q(667,10).
# Q(667,10) = P(667 - 45, 10)
# Note: The 45 comes from (k)(k-1)/2, the sum of (0..k-1).

my $kmax = 10;
my $nmax = 667 - 45;

# Final results for unique partitions would be created by
# adding (0..9) to the plain partition results, so restrict
# my maximum extry to 91.
my $entrymax = 100 - 9;

my ($n, $k, %triangle);

sub shiftpdl {
    my ($pdl_a) = @_;
    my $pdl_b = rotate($pdl_a,1)->copy;
    $pdl_b(0) .= 0;
    return $pdl_b;
}

# Initialize corner of the triangle.
my $p1 = zeroes $entrymax;
$p1(0) .= 1;   # Single item with a max entry of one.
$triangle{1,1} = $p1;

# Use the recurrence relation to populate the triangle,
# but accumulate for each maximum number separately so
# we can shift off and eliminate cases that would take
# our maximum entry over 100.
for $n (2..$nmax) {
    for $k (1..$kmax) {
        my $psum = zeroes $entrymax;
        if (exists $triangle{$n-1,$k-1}) {
            # New entries for this case are created by tacking
            # on a one to each result, so the maximum is unchanged.
            $psum += $triangle{$n-1,$k-1};
        }
        if (exists $triangle{$n-$k, $k}) {
            # New entries for this case are created by adding
            # a one to each entry, so shift all counts up one place.
            $psum += shiftpdl($triangle{$n-$k, $k});
        }
        $triangle{$n,$k} = $psum;
    }
}

my $sum = sumover $triangle{$nmax,$kmax};
print "Total unique partitions C(677,10) on {1..100} is ",$sum,"\n";