imported my solutions (2 Perl + 2 C) to this weeks' tasks..

10 files changed, 582 insertions, 40 deletions

diff --git a/challenge-175/duncan-c-white/C/.cbuild b/challenge-175/duncan-c-white/C/.cbuild
index c205cb0889..aebcd2040a 100644
--- a/challenge-175/duncan-c-white/C/.cbuild
+++ b/challenge-175/duncan-c-white/C/.cbuild
@@ -1,3 +1,3 @@
-BUILD = ch-1 ch-1a
-CFLAGS = -Wall
+BUILD = ch-1 ch-2
+CFLAGS = -Wall -g
 #CFLAGS = -g
diff --git a/challenge-175/duncan-c-white/C/Makefile b/challenge-175/duncan-c-white/C/Makefile
new file mode 100644
index 0000000000..e88442625a
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/Makefile
@@ -0,0 +1,12 @@
+BUILD	= ch-1 ch-2
+CC	= gcc
+CFLAGS	= -Wall -g
+LDLIBS	= -lm
+
+all:	$(BUILD)
+
+clean:
+	/bin/rm -f $(BUILD) *.o core a.out
+
+ch-1:	ch-1.o args.o
+ch-1.o:	ch-1.c args.h
diff --git a/challenge-175/duncan-c-white/C/README b/challenge-175/duncan-c-white/C/README
new file mode 100644
index 0000000000..59181ad192
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/README
@@ -0,0 +1,8 @@
+Thought I'd also have a go at translating ch-1.pl and ch-2.c into C..
+
+ch-1.c produces identical (non-debugging) output to my Perl original.
+
+ch-1.c uses the command-line argument processing module args.[ch].
+
+Ditto for ch-2.c.  Note that the C version (ch-2.c) is approx 12 times as
+fast than my Perl version (ch-2.pl).
diff --git a/challenge-175/duncan-c-white/C/args.c b/challenge-175/duncan-c-white/C/args.c
new file mode 100644
index 0000000000..77834b0d5b
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/args.c
@@ -0,0 +1,174 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+
+
+bool debug = false;
+
+
+// process_flag_noarg( name, argc, argv );
+//	Process the -d flag, and check that there are no
+//	remaining arguments.
+void process_flag_noarg( char *name, int argc, char **argv )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left != 0 )
+	{
+		fprintf( stderr, "Usage: %s [-d]\n", name );
+		exit(1);
+	}
+}
+
+
+// process_onenumarg_default( name, argc, argv, defvalue, &n );
+//	Process the -d flag, and check that there is a single
+//	remaining numeric argument (or no arguments, in which case
+//	we use the defvalue), putting it into n
+void process_onenumarg_default( char *name, int argc, char **argv, int defvalue, int *n )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left > 1 )
+	{
+		fprintf( stderr, "Usage: %s [-d] n\n", name );
+		exit(1);
+	}
+
+	if( left == 0 )
+	{
+		*n = defvalue;
+		return;
+	}
+
+	// element is in argv[arg]
+
+	if( debug )
+	{
+		printf( "debug: remaining arguments are in arg=%d, "
+		        "firstn=%s\n", arg, argv[arg] );
+	}
+
+	*n = atoi( argv[arg] );
+}
+
+
+// process_onenumarg( name, argc, argv, &n );
+//	Process the -d flag, and check that there is a single
+//	remaining numeric argument, putting it into n
+void process_onenumarg( char *name, int argc, char **argv, int *n )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left != 1 )
+	{
+		fprintf( stderr, "Usage: %s [-d] n\n", name );
+		exit(1);
+	}
+
+	// element is in argv[arg]
+
+	if( debug )
+	{
+		printf( "debug: remaining arguments are in arg=%d, "
+		        "firstn=%s\n", arg, argv[arg] );
+	}
+
+	*n = atoi( argv[arg] );
+}
+
+
+// process_twonumargs( name, argc, argv, &m, &n );
+//	Process the -d flag, and check that there are 2
+//	remaining numeric arguments, putting them into m and n
+void process_twonumargs( char *name, int argc, char **argv, int *m, int *n )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left != 2 )
+	{
+		fprintf( stderr, "Usage: %s [-d] m n\n", name );
+		exit(1);
+	}
+
+	// elements are in argv[arg] and argv[arg+1]
+
+	if( debug )
+	{
+		printf( "debug: remaining arguments are in arg=%d, "
+		        "firstn=%s, secondn=%s\n",
+			arg, argv[arg], argv[arg+1] );
+	}
+
+	*m = atoi( argv[arg++] );
+	*n = atoi( argv[arg] );
+}
+
+// int arr[100];
+// int nel = process_listnumargs( name, argc, argv, arr, 100 );
+//	Process the -d flag, and check that there are >= 2
+//	remaining numeric arguments, putting them into arr[0..nel-1]
+//	and returning nel.
+int process_listnumargs( char *name, int argc, char **argv, int *arr, int maxel )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left < 2 )
+	{
+		fprintf( stderr, "Usage: %s [-d] list_of_numeric_args\n", name );
+		exit(1);
+	}
+	if( left > maxel )
+	{
+		fprintf( stderr, "%s: more than %d args\n", name, maxel );
+		exit(1);
+	}
+
+	// elements are in argv[arg], argv[arg+1]...
+
+	if( debug )
+	{
+		printf( "debug: remaining arguments are in arg=%d, "
+		        "firstn=%s, secondn=%s..\n",
+			arg, argv[arg], argv[arg+1] );
+	}
+
+	int nel = 0;
+	for( int i=arg; i<argc; i++ )
+	{
+		arr[nel++] = atoi( argv[i] );
+	}
+	arr[nel] = -1;
+	return nel;
+}
diff --git a/challenge-175/duncan-c-white/C/args.h b/challenge-175/duncan-c-white/C/args.h
new file mode 100644
index 0000000000..06ce79a696
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/args.h
@@ -0,0 +1,7 @@
+extern bool debug;
+
+extern void process_flag_noarg( char * name, int argc, char ** argv );
+extern void process_onenumarg_default( char * name, int argc, char ** argv, int defvalue, int * n );
+extern void process_onenumarg( char * name, int argc, char ** argv, int * n );
+extern void process_twonumargs( char * name, int argc, char ** argv, int * m, int * n );
+extern int process_listnumargs( char * name, int argc, char ** argv, int * arr, int maxel );
diff --git a/challenge-175/duncan-c-white/C/ch-1.c b/challenge-175/duncan-c-white/C/ch-1.c
new file mode 100644
index 0000000000..fc6483a3a3
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/ch-1.c
@@ -0,0 +1,83 @@
+/* 
+ * Task 1 - Last Sunday
+ * 
+ * GUEST LANGUAGE: THIS IS THE C VERSION OF ch-1.pl.
+ */ 
+
+//#define _XOPEN_SOURCE
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+//#include <assert.h>
+#include <time.h>
+
+#include "args.h"
+
+
+// seconds in a day
+#define SECSINDAY (24*60*60)
+
+
+//
+// time_t t = ymd( y, m, d );
+//	Return the abolute time (seconds since Jan 1st 1970 corresponding
+//	to the date y-m-d.
+//
+time_t ymd( int y, int m, int d )
+{
+	struct tm info;
+	info.tm_year = y - 1900;
+	info.tm_mon = m - 1;
+	info.tm_mday = d;
+	info.tm_hour = 0;
+	info.tm_min = 0;
+	info.tm_sec = 1;
+	info.tm_isdst = -1;
+	time_t t = mktime( &info );
+	if( t == -1 ) {
+		printf("Error: unable to make time using mktime\n");
+	} else {
+		char buffer[80];
+		strftime(buffer, sizeof(buffer), "%c", &info );
+		//printf("debug: %s\n", buffer);
+	}
+	return t;
+}
+
+
+int main( int argc, char **argv )
+{
+	int y;
+	process_onenumarg( "last-sunday", argc, argv, &y );
+
+	for( int m=1; m<=12; m++ )
+	{
+		char sunday[20];
+		for( time_t t = ymd( y, m, 1 ); ; t += SECSINDAY )
+		{
+			struct tm *day = localtime(&t);
+			if( debug )
+			{
+				char datestr[40];
+				strcpy( datestr, asctime(day) );
+				datestr[strlen(datestr)-1] = '\0';
+				printf( "%lu, %s: tm_mon=%d, tm_day=%d, tm_wday=%d\n",
+					t, datestr, day->tm_mon,
+					day->tm_mday, day->tm_wday );
+			}
+		if( day->tm_mon != m-1 ) break;
+			if( day->tm_wday == 0 )
+			{
+				strftime( sunday, 20, "%Y-%m-%d", day );
+				if( debug )
+				{
+					printf( "found a sunday: %s\n", sunday );
+				}
+			}
+		}
+		printf( "%s\n", sunday );
+	}
+	return 0;
+}
diff --git a/challenge-175/duncan-c-white/C/ch-2.c b/challenge-175/duncan-c-white/C/ch-2.c
new file mode 100644
index 0000000000..bc65f85dd2
--- /dev/null
+++ b/challenge-175/duncan-c-white/C/ch-2.c
@@ -0,0 +1,92 @@
+/* 
+ * Task 2 - Perfect Totient Numbers
+ * 
+ * GUEST LANGUAGE: THIS IS THE C VERSION OF ch-2.pl.
+ */ 
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+//#include <assert.h>
+
+#include "args.h"
+
+
+//
+// int result = gcd( a, b );
+//       Compute and return the GCD (Greatest Common Denominator) of a and b.
+//
+int gcd( int a, int b )
+{
+        while( b != 0 )
+        {
+		int t = a % b;
+		a = b;
+		b = t;
+        }
+        return a;
+}
+
+
+//
+// int ntot = totient( n );
+//	This function counts the positive integers up to $n that are
+//	relatively prime to $n.  In other words, it is the number of
+//	values in the range 1 <= k <= n for which gcd(n, k) == 1.
+//
+int totient( int n )
+{
+	int result = 0;
+	for( int k=1; k<=n; k++ )
+	{
+		if( gcd(n,k)==1 ) result++;
+	}
+	return result;
+}
+
+
+//
+// bool isptn = is_perfect_totient_number( n );
+//	A perfect totient number is an integer that is equal to the sum
+//	of its iterated totients. That is, we apply the totient function
+//	to a number n, apply it again to the resulting totient, and so on,
+//	until the number 1 is reached, and add together the resulting
+//	sequence of numbers; iff the sum equals n, then n is a perfect totient
+//	number.
+//
+bool is_perfect_totient_number( int n )
+{
+	int sum = 0;
+	int x = n;
+	do {
+		x = totient(x);
+		sum += x;
+		if( debug )
+		{
+			printf( "debug: x=%d, sum=%d\n", x, sum );
+		}
+	} while( x != 1 );
+	return sum==n?1:0;
+}
+
+
+int main( int argc, char **argv )
+{
+	int n;
+	process_onenumarg_default( "first-n-perfect-totient-numbers",
+				argc, argv, 20, &n );
+
+	int nfound = 0;
+	for( int i=2; nfound<n; i++ )
+	{
+		if( is_perfect_totient_number( i ) )
+		{
+			printf( "%d, ", i );
+			nfound++;
+		}
+	}
+	putchar( '\n' );
+
+	return 0;
+}
diff --git a/challenge-175/duncan-c-white/README b/challenge-175/duncan-c-white/README
index 667271dbff..c74b967883 100644
--- a/challenge-175/duncan-c-white/README
+++ b/challenge-175/duncan-c-white/README
@@ -1,57 +1,62 @@
-Task 1: Disarium Numbers
+Task 1: Last Sunday
 
-Write a script to generate first 19 Disarium Numbers.
+Write a script to list Last Sunday of every month in the given year.
 
-A disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.
+For example, for year 2022, we should get the following:
 
-For example,
+2022-01-30
+2022-02-27
+2022-03-27
+2022-04-24
+2022-05-29
+2022-06-26
+2022-07-31
+2022-08-28
+2022-09-25
+2022-10-30
+2022-11-27
+2022-12-25
 
-518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518
-
-
-MY NOTES: ok, sounds pretty easy.  Once I'd solved it, as it seemed rather
-slow, I profiled it with NYTProf and generated successive optimised versions
-ch-1[a-g].pl - and ch-1g.pl runs about 7 times faster than the initial version.
+MY NOTES: ok, sounds pretty easy: basically, start on the 1st of the
+month, and walk forwards hitting the date when we hit a Sunday.  The
+hardest part is, as always, choosing which date manipulation module to use.
 
 GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl
 into C (look in the C directory for that).
 
 
-Task 2: Permutation Ranking
+Task 2: Perfect Totient Numbers
 
-You are given a list of integers with no duplicates, e.g. [0, 1, 2].
+Write a script to generate first 20 Perfect Totient Numbers. Please
+checkout the following wikipedia page for more information:
 
-Write two functions, permutation2rank() which will take the list and
-determine its rank (starting at 0) in the set of possible permutations
-arranged in lexicographic order, and rank2permutation() which will take
-the list and a rank number and produce just that permutation.
+  https://en.wikipedia.org/wiki/Perfect_totient_number
 
-Please checkout this post for more informations and algorithm:
-  https://tryalgo.org/en/permutations/2016/09/05/permutation-rank/
+Explanation gleaned from those notes:
 
-Given the list [0, 1, 2] the ordered permutations are:
+A perfect totient number is an integer that is equal to the sum of its
+iterated totients. That is, we apply the totient function to a number n,
+apply it again to the resulting totient, and so on, until the number 1
+is reached, and add together the resulting sequence of numbers; if the
+sum equals n, then n is a perfect totient number.
 
-0: [0, 1, 2]
-1: [0, 2, 1]
-2: [1, 0, 2]
-3: [1, 2, 0]
-4: [2, 0, 1]
-5: [2, 1, 0]
+The totient function counts the positive integers up to a given integer
+n that are relatively prime to n.  In other words, it is the number of
+integers k in the range 1 <= k <= n for which gcd(n, k) is equal to 1.
 
-and therefore:
+For example, there are six positive integers less than 9 and relatively
+prime to it, so the totient of 9 is 6; there are two numbers less than
+6 and relatively prime to it, so the totient of 6 is 2; and there is one
+number less than 2 and relatively prime to it, so the totient of 2 is 1;
+and 9 = 6 + 2 + 1, so 9 is a perfect totient number.
 
-permutation2rank([1, 0, 2]) = 2
+Output
 
-rank2permutation([0, 1, 2], 1) = [0, 2, 1]
+3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729,
+2187, 2199, 3063, 4359, 4375, 5571
 
+MY NOTES: given a gcd() function it seems relatively straightforward.
+We last used gcd() in challenge 136.
 
-MY NOTES: hmm.. I hate permutations, never managed to memorise the
-algorithm in all my years of programming.  However, I've got a module
-Perm.pm which permutes the digits in a number, so let's reuse it to solve
-this pesky problem in the simplest possible way: Perms' "next_perm()"
-function generates all the perms in order, so sticking that inside
-various simple counting loops does the trick, albeit very inefficiently.
-That'll do!
-
-I didn't have time to translate this (and the Perms module) to C, although it
-should be pretty straightforward.
+GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl
+into C (look in the C directory for that).
diff --git a/challenge-175/duncan-c-white/perl/ch-1.pl b/challenge-175/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..6b5aeb5e56
--- /dev/null
+++ b/challenge-175/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,48 @@
+#!/usr/bin/perl
+# 
+# Task 1: Last Sunday
+# 
+# Write a script to list Last Sunday of every month in the given year.
+# 
+# For example, for year 2022, we should get the following:
+# 
+# 2022-01-30
+# 2022-02-27
+# 2022-03-27
+# 2022-04-24
+# 2022-05-29
+# 2022-06-26
+# 2022-07-31
+# 2022-08-28
+# 2022-09-25
+# 2022-10-30
+# 2022-11-27
+# 2022-12-25
+# 
+# MY NOTES: ok, sounds pretty easy: basically, start on the 1st of the
+# month, and walk forwards hitting the date when we hit a Sunday.  The
+# hardest part is, as always, choosing which date manipulation module to use.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use Date::Simple ('ymd');
+
+
+my $debug=0;
+die "Usage: last-sunday-in-every-month [--debug] YYYY\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $y = shift;
+
+foreach my $m (1..12)
+{
+	my $sunday;
+	for( my $d = ymd($y, $m, 1); $d->month == $m; $d++ )
+	{
+		$sunday = $d if $d->day_of_week() == 0;
+	}
+	say $sunday;
+}
diff --git a/challenge-175/duncan-c-white/perl/ch-2.pl b/challenge-175/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..ccd7a4a4fd
--- /dev/null
+++ b/challenge-175/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,113 @@
+#!/usr/bin/perl
+# 
+# Task 2: Perfect Totient Numbers
+# 
+# Write a script to generate first 20 Perfect Totient Numbers. Please
+# checkout the following wikipedia page for more information:
+# 
+#   https://en.wikipedia.org/wiki/Perfect_totient_number
+# 
+# Explanation gleaned from those notes:
+# 
+# A perfect totient number is an integer that is equal to the sum of its
+# iterated totients. That is, we apply the totient function to a number n,
+# apply it again to the resulting totient, and so on, until the number 1
+# is reached, and add together the resulting sequence of numbers; if the
+# sum equals n, then n is a perfect totient number.
+# 
+# The totient function counts the positive integers up to a given integer
+# n that are relatively prime to n.  In other words, it is the number of
+# integers k in the range 1 <= k <= n for which gcd(n, k) is equal to 1.
+# 
+# For example, there are six positive integers less than 9 and relatively
+# prime to it, so the totient of 9 is 6; there are two numbers less than
+# 6 and relatively prime to it, so the totient of 6 is 2; and there is one
+# number less than 2 and relatively prime to it, so the totient of 2 is 1;
+# and 9 = 6 + 2 + 1, so 9 is a perfect totient number.
+# 
+# Output
+# 
+# 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729,
+# 2187, 2199, 3063, 4359, 4375, 5571
+# 
+# MY NOTES: given a gcd() function it seems relatively straightforward.
+# We last used gcd() in challenge 136, so let's re-use our implementation.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use Function::Parameters;
+
+my $debug=0;
+die "Usage: first-n-perfect-totient-numbers [--debug] [N default 20]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+
+
+#
+# my $gcd = gcd( $a, $b );
+#       Compute and return the GCD (Greatest Common Denominator) of $a and $b.
+#
+fun gcd( $a, $b )
+{
+        while( $b != 0 )
+        {
+                ( $a, $b ) = ( $b, $a % $b );
+        }
+        return $a;
+}
+
+
+#
+# my $ntot = totient( $n );
+#	This function counts the positive integers up to $n that are
+#	relatively prime to $n.  In other words, it is the number of
+#	values in the range 1 <= k <= n for which gcd(n, k) == 1.
+#
+fun totient( $n )
+{
+	my $result = 0;
+	foreach my $k (1..$n)
+	{
+		$result++ if gcd($n,$k)==1;
+	}
+	return $result;
+}
+
+
+#say totient(9);
+#say totient(6);
+#say totient(2);
+
+#
+# my $isptn = is_perfect_totient_number( $n );
+#	A perfect totient number is an integer that is equal to the sum
+#	of its iterated totients. That is, we apply the totient function
+#	to a number n, apply it again to the resulting totient, and so on,
+#	until the number 1 is reached, and add together the resulting
+#	sequence of numbers; iff the sum equals n, then n is a perfect totient
+#	number.
+#
+fun is_perfect_totient_number( $n )
+{
+	my $sum = 0;
+	my $x = $n;
+	do {
+		$x = totient($x);
+		$sum += $x;
+		say "debug: x=$x, sum=$sum" if $debug;
+	} while( $x != 1 );
+	return $sum==$n?1:0;
+}
+
+
+my $firstn = shift // 20;
+my @found;
+for( my $i=2; @found<$firstn; $i++ )
+{
+	push @found, $i if is_perfect_totient_number( $i );
+}
+
+say join( ', ', @found );