diff options
| -rw-r--r-- | challenge-175/duncan-c-white/C/.cbuild | 4 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/Makefile | 12 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/README | 8 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/args.c | 174 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/args.h | 7 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/ch-1.c | 83 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/C/ch-2.c | 92 | ||||
| -rw-r--r-- | challenge-175/duncan-c-white/README | 81 | ||||
| -rwxr-xr-x | challenge-175/duncan-c-white/perl/ch-1.pl | 48 | ||||
| -rwxr-xr-x | challenge-175/duncan-c-white/perl/ch-2.pl | 113 |
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 ); |