Robbie Hatley's C and Perl solutions for 201-2 (will add 201-1 later).

2 files changed, 302 insertions, 0 deletions

diff --git a/challenge-201/robbie-hatley/c/part.c b/challenge-201/robbie-hatley/c/part.c
new file mode 100644
index 0000000000..46d184d625
--- /dev/null
+++ b/challenge-201/robbie-hatley/c/part.c
@@ -0,0 +1,170 @@
+/*
+part.c
+Prints the number P(n) of ways of partitioning a non-negative integer n into
+increasing or decreasing serieses of positive integers.
+For example, 5 may be partitioned in these (and ONLY these) 7 ways:
+5 = 5
+5 = 4 + 1
+5 = 3 + 2
+5 = 3 + 1 + 1
+5 = 2 + 2 + 1
+5 = 2 + 1 + 1 + 1
+5 = 1 + 1 + 1 + 1 + 1
+Hence P(5)=7.
+
+Note: The algorithm for this program is taken from the "Recurrence Relations" section of this web site:
+https://en.wikipedia.org/wiki/Partition_function_(number_theory)
+
+Note: "partitions" is nearly identical to my program "part", except that it prints P(i) for ALL values of i from 1
+through the given argument n. "partitions" is a trivial extention of "part", because "part" already calculates all of
+those numbers anyone, but only prints P(n).
+
+Written by Robbie Hatley on Wednesday April 4, 2018.
+
+Edit History:
+2018-04-04: Wrote it.
+2022-07-16: Dramatically-improved comments.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <gmp.h>
+
+// Set maximum number of partitions, then set array size to 5 over that:
+#define MAX_N 1000000
+#define ARRAY_SIZE (MAX_N + 5)
+
+mpz_t PTable [ARRAY_SIZE];
+
+// Initialize first TopOfZone elements of PTable, and set the value of the first 10 elements manually:
+void InitPTable (int TopOfZone)
+{
+   int i = 0;
+
+   if (TopOfZone <   10 ) TopOfZone = 10;
+   if (TopOfZone > MAX_N) TopOfZone = MAX_N;
+
+   // Only initialize the elements we actually need:
+   for ( i = 0 ; i <= TopOfZone ; ++i )
+   {
+      mpz_init(PTable[i]);
+   }
+
+   // Insert #s of partitions for n in 0-10 range manually:
+   mpz_set_si(PTable[ 0],  1);
+   mpz_set_si(PTable[ 1],  1);
+   mpz_set_si(PTable[ 2],  2);
+   mpz_set_si(PTable[ 3],  3);
+   mpz_set_si(PTable[ 4],  5);
+   mpz_set_si(PTable[ 5],  7);
+   mpz_set_si(PTable[ 6], 11);
+   mpz_set_si(PTable[ 7], 15);
+   mpz_set_si(PTable[ 8], 22);
+   mpz_set_si(PTable[ 9], 30);
+   mpz_set_si(PTable[10], 42);
+}
+
+// Inline the "Generalized Pentagonal Numbers" function
+// by making it a function-like macro (metaprogramming):
+#define Pent(X) ((X)*(3*(X)-1)/2)
+
+void NumberOfPartitions (mpz_t result, const int n)
+{
+   if      (n <   0) {mpz_set_si(result,   0     );}
+   else if (n ==  0) {mpz_set_si(result,   1     );}
+   else if (n <= 10) {mpz_set   (result,PTable[n]);}
+   else//if(n >= 11):
+   {
+      int    m       = 0;
+      int    LwrLim  = 0;
+      int    UprLim  = 0;
+      int    k       = 0;
+      mpz_t  Term;   mpz_init(Term);
+      mpz_t  p;      mpz_init(p);
+
+      // We already have the partition numbers for 0-10, so
+      // now lets build up the table, starting from 11 and
+      // working up to m. This way, no recursion is required.
+      for ( m = 11 ; m <= n ; ++m )
+      {
+         LwrLim = (int) ceil  (-(sqrt(24.0*m+1.0)-1.0)/6.0);
+         UprLim = (int) floor ( (sqrt(24.0*m+1.0)+1.0)/6.0);
+         // printf("m = %d  LwrLim = %d  UprLim = %d\n", m, LwrLim, UprLim);
+         // Zero p here, because we're starting a new partition
+         // (otherwise p accumulates junk from earlier partitions):
+         mpz_set_si(p, 0);
+         for ( k = LwrLim ; k <= UprLim ; ++k )
+         {
+            if (0 == k) continue;
+            if (m-Pent(k) < 0)
+            {
+               fprintf(stderr, "m-Pent(k) < 0\n");
+               continue;
+            }
+            mpz_set(Term, PTable[m-Pent(k)]);
+            if (0 == k%2)
+            {
+               mpz_sub(p, p, Term);
+            }
+            else
+            {
+               mpz_add(p, p, Term);
+            }
+         }
+         mpz_set(PTable[m], p);
+      } // end for each m
+      // Set "result" to nth element of table:
+      mpz_set(result, PTable[n]);
+   } // end else (n >= 11)
+   // Return. (Since we're passing the output in the "result" parameter,
+   // there's no return value.)
+   return;
+}
+
+int main (int Beren, char * Luthien[])
+{
+   // Declare any necessary variables:
+   long    n_raw  = 0L;
+   int     n      = 0;
+   mpz_t   p;
+
+   // Do all necessary preliminary book-keeping:
+   mpz_init(p);
+   if (Beren != 2)
+   {
+      fprintf
+      (
+         stderr, 
+         "Error: \"part\" requires exactly 1 argument, which must be\n"
+         "a non-negative integer not exceeding %d.\n",
+         MAX_N
+      );
+      exit(666);
+   }
+   n_raw = strtol(Luthien[1], NULL, 10);
+   if (n_raw > MAX_N || n_raw < 0)
+   {
+      fprintf
+      (
+         stderr, 
+         "Error: argument must be a non-negative integer\n"
+         "not exceeding %d\n", 
+         MAX_N
+      );
+      exit(666);
+   }
+
+   // n is the number to be partitioned, and is also the number of possible numbers of stacks, as any positive integer n
+   // will have partitions including all numbers of stacks from 1 through n:
+   n = (int)n_raw;  
+
+   // Initialize the first n elements of PTable, and set the value of the first 10 elements manually to
+   // P(n) for n values from 1 through 10:
+   InitPTable(n);
+
+   // With the preliminaries out of the way, let's get to calculating and printing P(n):
+   NumberOfPartitions(p, n); // Calculate P(n).
+   gmp_printf("%Zd", p);     // Print P(n).
+   return 0; 
+}
diff --git a/challenge-201/robbie-hatley/perl/ch-2.pl b/challenge-201/robbie-hatley/perl/ch-2.pl
new file mode 100755
index 0000000000..52e910efa8
--- /dev/null
+++ b/challenge-201/robbie-hatley/perl/ch-2.pl
@@ -0,0 +1,132 @@
+#! /usr/bin/perl
+# Robbie Hatley's Perl solution to PWCC 201-2
+
+=pod
+
+Task 2: Penny Piles
+Submitted by: Robbie Hatley
+
+You are 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.
+
+Example:  Input: 5  Output: 7
+Since $n=5, there are 7 ways of stacking 5 pennies in ascending piles:
+1 1 1 1 1
+1 1 1 2
+1 2 2
+1 1 3
+2 3
+1 4
+5
+
+Note: The algorithm for this program is taken from the 
+"Recurrence Relations" section of Wikipedia's article on
+"Partition Function":
+"https://en.wikipedia.org/wiki/Partition_function_(number_theory)"
+
+The numbers-of-partitions for integers 0-10 are taken from 
+Sequence # A000041 on the "oeis.org" web site:
+"https://oeis.org/A000041"
+
+=cut
+
+# IO NOTES:
+#
+# NOTE: Input is from @ARGV and must be a single integer
+#       in the range 0-1000000.
+#
+# NOTE: Output will be to stdout and will be the number
+#       of ways of "partitioning" the input integer.
+
+# PRELIMINARIES:
+
+use v5.36;
+use bigint;
+
+# GLOBAL VARIABLES:
+
+# Most computers can handle an array of one million integers.
+# (You may need to set this number smaller if yours can't.)
+my $MAX_N = 1000000;
+
+# Taken from web site "oeis.org" sequence # A000041:
+my @PTable = (1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42);
+
+# SUBROUTINES:
+
+# Generalized-Pentagonal-Numbers function.
+# (See "https://en.wikipedia.org/wiki/Pentagonal_number".)
+sub Pent($x) {return $x*(3*$x-1)/2}
+
+# Fill-in entries in our "Number of Partitions of n" table
+# from 11 through $n:
+sub NumberOfPartitions ($n)
+{
+   if ( $n < 0 )
+      {die "Error in NumberOfPartitions: \$n is negative ($n)."}
+
+   if ( $n > $MAX_N )
+      {die "Error in NumberOfPartitions: \$n is > $MAX_N ($n)."}
+
+   if ( 0 <= $n && $n <= 10 )
+      {return} # Work is already done for 0-10.
+
+   # If we get to here, 11 <= n <= $MAX_N, so we need to create
+   # new entries in our table of "number of partitions of n" for
+   # 11 through $n, because we only initialized 0-10.
+
+   my $m       = 0;
+   my $LwrLim  = 0;
+   my $UprLim  = 0;
+   my $k       = 0;
+   my $Term    = 0;
+   my $p       = 0;
+
+   # We already have the number-of-partitions for 0-10,
+   # so now lets build up the table, starting from 11 and
+   # working up to $n. This way, no recursion is required.
+   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;
+      for ( $k = $LwrLim ; $k <= $UprLim ; ++$k )
+      {
+         if (0 == $k)             {next}
+         if (($m - Pent($k)) < 0) {next}
+         $Term = $PTable[$m-Pent($k)];
+         if   (0 == $k%2) {$p -= $Term}
+         else             {$p += $Term}
+      }
+      $PTable[$m] = $p;
+   } # end for each $m
+   # The results are all stored in global @PTable so just return:
+   return;
+}
+
+# Print message and die if program encounters an error:
+sub croak{
+   die "Error: This program must have exactly one argument,\n".
+       "which must be an integer from 0 through $MAX_N.\n".
+       "This program will then print the number of ways of\n".
+       "partitioning that integer.\n";}
+
+# INPUT:
+# Die unless we have exactly 1 argument which is an integer in
+# the range from 0 through $MAX_N:
+if (1 != scalar(@ARGV))          {croak}
+my $n = $ARGV[0];
+if ($n !~ m/(^0$)|(^[1-9]\d*$)/) {croak}
+if ($n < 0)                      {croak}
+if ($n > $MAX_N)                 {croak}
+
+# MAIN BODY OF SCRIPT:
+
+# Fill-in partition table:
+NumberOfPartitions($n);
+
+# Print result:
+say $PTable[$n];