Robbie Hatley's Perl Solutions To The Weekly Challenge #201

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle, usually with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

This week (2023-01-22 through 2023-01-28) is weekly challenge #201.

For a change, I was the "submitted by" person for challenge #2 (M. Anwar submitted #1).

Challenge #1 is: "Given an array of unique integers, write a script to find out all missing integers in the range 0..$n where $n is the array size." This is simple, but quirky, because the results may not quite be what one expects. For example, given the sequence (14, 15, 18, 19) -- or, for that matter, (18, 14, 19, 15) -- one might expect the "missing numbers" to be (16, 17). But nope, they'll be (0, 1, 2, 3). A more-useful script might be to find all missing integers in the range $min..$max rather than 0..$size. So I wrote a script to do both, the main body of which looks like this:

my $size = scalar @ARGV;
my @missing_zer_siz = ();
my @missing_min_max = ();
my $min = $ARGV[0]; for (@ARGV) {$min = $_ if $_<$min}
my $max = $ARGV[0]; for (@ARGV) {$max = $_ if $_>$max}
for (0..$size){
   push @missing_zer_siz, $_ if !is_in(\@ARGV, $_)}
for ($min..$max){
   push @missing_min_max, $_ if !is_in(\@ARGV, $_)}
say "missing integers in zero-to-size range:";
say "(@missing_zer_siz)";
say "missing integers in min-to-max range:";
say "(@missing_min_max)";

Challenge #2 is this: "Given an integer, $n > 0, write a script to determine the number of ways of putting $n pennies in a row of piles of ascending heights from left to right." This sounds easy, but is anything but! For more than a dozen or so pennies, the ways to stack them quickly bloat to first the millions, then the septillions, then the vigintillions.

This problem is essentially a re-wording of "What is the number of ways of partitioning a non-negative integer n into positive integers?". There is no closed-form solution. There are, however, ways of solving this, including several recursion relations available on Wikipedia, Wolfram Alpha, and elsewhere; just search for "partitioning integers" or "partition function". I already solved this problem and implemented a program in C about 5 years ago; I ported it to Perl a few days ago. The key for loop that adds elements to a "table of numbers of partitions of integers" looks like this:

for ( $m = 11 ; $m <= $n ; ++$m )
{
   $LwrLim = int(-(sqrt(24*$m+1)-1)/6);
   $UprLim = int( (sqrt(24*$m+1)+1)/6);
   # Zero $p here, because we're starting a new partition
   # (otherwise $p accumulates junk from earlier partitions):
   $p = 0;
   # Use recurrence relation from
   # "https://en.wikipedia.org/wiki/Partition_function_(number_theory)"
   for ( $k = $LwrLim ; $k <= $UprLim ; ++$k )
   {
      if (0 == $k) {next}                        # "k∊ℤ\0"
      $idx = $m - Pent($k);                      # index for @PTable
      if ($idx < 0) {next}                       # "p[k]=0 if k<0"
      $p += ((-1)**($k+1)*$PTable[$m-Pent($k)]); # summation
   }
   # Add "number of partitions" for current m to @PTable:
   $PTable[$m] = $p;
} # end for each $m from 11 through $n

That's it for 201; looking forward to 202.

-- 
Cheers,
Robbie Hatley