From cbcd936c890a9608f5c7a89322aefae1c0b2bb97 Mon Sep 17 00:00:00 2001 From: dcw Date: Mon, 18 Jul 2022 21:48:43 +0100 Subject: belatedly tackling challenge #172, #173 still to do.. --- challenge-172/duncan-c-white/C/Makefile | 16 +++ challenge-172/duncan-c-white/C/README | 7 ++ challenge-172/duncan-c-white/C/args.c | 136 ++++++++++++++++++++++++ challenge-172/duncan-c-white/C/args.h | 6 ++ challenge-172/duncan-c-white/C/ch-1.c | 109 +++++++++++++++++++ challenge-172/duncan-c-white/C/ch-2.c | 108 +++++++++++++++++++ challenge-172/duncan-c-white/C/primes.c | 67 ++++++++++++ challenge-172/duncan-c-white/C/primes.h | 1 + challenge-172/duncan-c-white/README | 43 ++++---- challenge-172/duncan-c-white/perl/MakePrimes.pm | 90 ++++++++++++++++ challenge-172/duncan-c-white/perl/ch-1.pl | 68 ++++++++++++ challenge-172/duncan-c-white/perl/ch-2.pl | 63 +++++++++++ 12 files changed, 695 insertions(+), 19 deletions(-) create mode 100644 challenge-172/duncan-c-white/C/Makefile create mode 100644 challenge-172/duncan-c-white/C/README create mode 100644 challenge-172/duncan-c-white/C/args.c create mode 100644 challenge-172/duncan-c-white/C/args.h create mode 100644 challenge-172/duncan-c-white/C/ch-1.c create mode 100644 challenge-172/duncan-c-white/C/ch-2.c create mode 100644 challenge-172/duncan-c-white/C/primes.c create mode 100644 challenge-172/duncan-c-white/C/primes.h create mode 100644 challenge-172/duncan-c-white/perl/MakePrimes.pm create mode 100755 challenge-172/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-172/duncan-c-white/perl/ch-2.pl diff --git a/challenge-172/duncan-c-white/C/Makefile b/challenge-172/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..c1c8318a24 --- /dev/null +++ b/challenge-172/duncan-c-white/C/Makefile @@ -0,0 +1,16 @@ +BUILD = ch-1 ch-2 +CC = gcc +CFLAGS = -Wall # -g +LDLIBS = -lm + +all: $(BUILD) + +clean: + /bin/rm -f $(BUILD) *.o core a.out + +primes.o: primes.c + +ch-1: ch-1.o primes.o args.o +ch-1.o: ch-1.c args.h +ch-2: ch-2.o args.o +ch-2.o: ch-2.c args.h diff --git a/challenge-172/duncan-c-white/C/README b/challenge-172/duncan-c-white/C/README new file mode 100644 index 0000000000..931c4d8879 --- /dev/null +++ b/challenge-172/duncan-c-white/C/README @@ -0,0 +1,7 @@ +Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C.. + +Both C versions produce identical (non-debugging) output to my Perl originals + +ch-1.c uses primes.[ch], a prime number generator module that I wrote ages ago, +and I've finally split out the command-line argument processing code into +args.[ch]. diff --git a/challenge-172/duncan-c-white/C/args.c b/challenge-172/duncan-c-white/C/args.c new file mode 100644 index 0000000000..73a471464a --- /dev/null +++ b/challenge-172/duncan-c-white/C/args.c @@ -0,0 +1,136 @@ +#include +#include +#include +#include + + +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( 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 +#include +#include +//#include +#include +#include +#include +#include + +#include "args.h" +#include "primes.h" + + + +#define MAXSTRINGLEN 800 +typedef char string[MAXSTRINGLEN]; + + +#define MAXPRIMES 512 + + +int main( int argc, char **argv ) +{ + int m, n; + process_twonumargs( "prime-partition", argc, argv, &m, &n ); + + // get all primes less than m + int numprimes; + int *primes = primes_upto( m, &numprimes ); + if( debug ) + { + printf( "found %d primes, %d, %d, %d...%d\n", + numprimes, primes[0], primes[1], primes[2], + primes[numprimes-1] ); + } + assert( numprimes < MAXPRIMES ); + + string pps = ""; // single string "pp1 or pp2 ..." + + int two2n = 1<>1; + for( int pos=0; pos>= 1; + } + #if 0 + if( debug ) + { + printf( "debug: i=%d, nchosen=%d, sum=%d\n", + i, nchosen, sum ); + } + #endif + + if( sum == m && nchosen == n ) + { + string buf = ""; + char *p = buf; + for( int i=0; i0 ) + { + pps[len-4] = '\0'; + } + printf( "%s\n", pps ); + + return 0; +} diff --git a/challenge-172/duncan-c-white/C/ch-2.c b/challenge-172/duncan-c-white/C/ch-2.c new file mode 100644 index 0000000000..86aea9c9f3 --- /dev/null +++ b/challenge-172/duncan-c-white/C/ch-2.c @@ -0,0 +1,108 @@ +/* + * Task 2 - Five-number Summary + * + * GUEST LANGUAGE: THIS IS THE C VERSION OF ch-2.pl. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "args.h" + + +// +// double med = median( arr[], nel ); +// Calculate the median value in the sorted array arr[0..nel-1]. +// +double median( int *arr, int nel ) +{ + int midpos = nel/2; + double median = nel%2 == 0 ? + (arr[midpos-1]+arr[midpos])/2.0 : + arr[midpos]; + return median; +} + + +int intcompare( const void *p1, const void *p2 ) +{ + // The actual arguments to this function are "pointers to + // pointers to char", but strcmp(3) arguments are "pointers + // to char", hence the following cast plus dereference */ + + int a = *((int *)p1); + int b = *((int *)p2); + return a - b; +} + + +void prarr( int *arr, int nel ) +{ + for( int i=0; i +#include +#include +#include +#include + + +// int *primes = primes_upto(n,&numprimes); +// Generate a dynamic array of integers containing +// all primes up to $n. The array is zero-terminated. +// We also set numprimes to the number of primes found. +// The caller should free(primes) when they've finished +// using it. +// +int * primes_upto( int n, int *numprimep ) +{ + bool *isprime = (bool *) malloc( (n+1) * sizeof(bool) ); + assert( isprime != NULL ); + + int i; + for( i=1; i<=n; i++ ) + { + isprime[i] = 1; // initially + } + + int upper = (int)(sqrt((double)(n))); + //printf( "debug: n=%d, upper=%d\n", n, upper ); + for( i=2; i<=upper; i++ ) + { + if( isprime[i] ) + { + //printf( "debug: crossing out multiples of %d\n", i ); + int j; + for( j=i*i; j<=n; j+=i ) + { + isprime[j] = 0; + } + } + } + + // count how many primes there are + int np = 0; + for( i=2; i<=n; i++ ) + { + if( isprime[i] ) + { + np++; + } + } + *numprimep = np; + + // dynamically allocate an array of np+1 ints, and fill it in + int *primes = malloc( (np+1) * sizeof(int) ); + int p = 0; + for( i=2; i<=n; i++ ) + { + if( isprime[i] ) + { + primes[p++] = i; + } + } + primes[p] = 0; + + free( isprime ); + + return primes; +} diff --git a/challenge-172/duncan-c-white/C/primes.h b/challenge-172/duncan-c-white/C/primes.h new file mode 100644 index 0000000000..d9fd437aa7 --- /dev/null +++ b/challenge-172/duncan-c-white/C/primes.h @@ -0,0 +1 @@ +extern int * primes_upto( int n, int * numprimep ); diff --git a/challenge-172/duncan-c-white/README b/challenge-172/duncan-c-white/README index 755694b9fc..604f28c0b7 100644 --- a/challenge-172/duncan-c-white/README +++ b/challenge-172/duncan-c-white/README @@ -1,33 +1,38 @@ -Task 1: Abundant Number +Task 1: Prime Partition -Write a script to generate first 20 Abundant Odd Numbers. +You are given two positive integers, $m and $n. -According to wikipedia: A number n for which the sum of proper divisors -(divisors from 1 but less than n) s(n) > n. +Write a script to find out the Prime Partition of the given number $m that +contains $n elements. No duplicates allowed. -For example, 945 is the first Abundant Odd Number. +For example, -Sum of divisors: -1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975 + Input: $m = 18, $n = 2 + Output: 5, 13 or 7, 11 -MY NOTES: ok, sounds easy, and at least it's nowt to do with Primes:-) + Input: $m = 19, $n = 3 + Output: 3, 5, 11 + +MY NOTES: ok, sounds quite easy, even if it is to do with Primes. Without +duplicates means that each prime p < m is either present or absent in a +given partition, so we can use our old trick of having a counting loop from +0..2**(nitems)-1 and compute the sum of just those items selected by the +binary bits of the count that are 1 (then check that the sum is $m and +the number of elements being summed is $n) 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: First-class Function - -Create sub compose($f, $g) which takes in two parameters $f and $g as -subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) -= $f->($g->($x)) +Task 2: Five-number Summary -e.g. +You are given an array of integers. -$f = (one or more parameters function) -$g = (one or more parameters function) +Write a script to compute the five-number summary of the given set of integers. -$h = compose($f, $g) -$f->($g->($x,$y, ..)) == $h->($x, $y, ..) for any $x, $y, ... +You can find the definition and example in the wikipedia page: + https://en.wikipedia.org/wiki/Five-number_summary -MY NOTES: An interesting question at last. Think it's quite easy.. +MY NOTES: Nice and simple: sort the data, pick the median, first and third +quartile values. Note that the median can be the average (mean) of the +two central values if the #values is even. diff --git a/challenge-172/duncan-c-white/perl/MakePrimes.pm b/challenge-172/duncan-c-white/perl/MakePrimes.pm new file mode 100644 index 0000000000..e268fa06a3 --- /dev/null +++ b/challenge-172/duncan-c-white/perl/MakePrimes.pm @@ -0,0 +1,90 @@ +# +# mkprimes module (converted from mkprimes.c) +# + +use strict; +use warnings; +use Function::Parameters; + +my $debug = 0; +my @foundprimes; # remember all primes we've found.. + + +# +# my @primes = primes_upto( $n ); +# Find all primes up to N; return a list of all such primes +# (note that 1 is not usually considered a prime) +# +fun primes_upto( $n ) +{ + my @isprime; + + for( my $i=1; $i<=$n; $i++ ) + { + $isprime[$i] = 1; # initially + } + + # now sieve the non-primes out.. + my $upper = int(sqrt($n)); + printf( "debug: n=%d, upper=%d\n", $n, $upper ) if $debug; + for( my $i=2; $i<=$upper; $i++ ) + { + if( $isprime[$i] ) + { + #printf( "debug: crossing out multiples of %d\n", $i ); + for( my $j=$i*$i; $j<=$n; $j+=$i ) + { + $isprime[$j] = 0; + } + } + } + + # after sieving, extract the primes + my @primes = grep { $isprime[$_] } 2..$n; + + # remember them + @foundprimes = @primes; + + return @primes; +} + + +# +# my @moreprimes = more_primes( $n, $m ); +# Need more primes! Have @foundprimes up to $n, but need +# to sieve primes from $n+1..$m, so re-sieve, return +# a list of all new primes (in the range $n+1..$m) that we find. +# +fun more_primes( $n, $m ) +{ + my %isprime; + + print "finding more primes from ", $n+1, "..$m\n"; + + for( my $i=$n+1; $i<=$m; $i++ ) + { + $isprime{$i} = 1; # pre-sieving + } + + # now sieve the non-primes out.. + foreach my $prime (@foundprimes) + { + # find first multiple of $prime > $n + my $mult = $prime * (int($n/$prime)+1); + + #print "debug: xo multiples of $prime from $mult to $m\n"; + + for( my $j=$mult; $j<=$m; $j+=$prime ) + { + delete $isprime{$j}; + } + } + + # after sieving, extract the primes + my @primes = grep { $isprime{$_} } $n+1..$m; + push @foundprimes, @primes; + return @primes; +} + + +1; diff --git a/challenge-172/duncan-c-white/perl/ch-1.pl b/challenge-172/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..d2b3daf950 --- /dev/null +++ b/challenge-172/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,68 @@ +#!/usr/bin/perl +# +# Task 1: Prime Partition +# +# You are given two positive integers, $m and $n. +# +# Write a script to find out the Prime Partition of the given number $m that +# contains $n elements. No duplicates allowed. +# +# For example, +# +# Input: $m = 18, $n = 2 +# Output: 5, 13 or 7, 11 +# +# Input: $m = 19, $n = 3 +# Output: 3, 5, 11 +# +# MY NOTES: ok, sounds quite easy, even if it is to do with Primes. Without +# duplicates means that each prime p < m is either present or absent in a +# given partition, so we can use our old trick of having a counting loop from +# 0..2**(nitems)-1 and compute the sum of just those items selected by the +# binary bits of the count that are 1 (then check that the sum is $m and +# the number of elements being summed is $n) +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl +# into C (look in the C directory for that). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use List::Util qw(sum0); + +use lib qw(.); +use MakePrimes; + +my $debug=0; +die "Usage: prime-partition [--debug] M N\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==2; +my( $m, $n ) = @ARGV; + +my @primes = primes_upto( $m-1 ); +my $nitems = @primes; + +my @pp; # array of prime partitions, each a string + +my $two2n = 2**$nitems; + +for( my $i=0; $i<$two2n; $i++ ) +{ + my $b = sprintf("%0${nitems}b", $i ); + my @select = split( //, $b ); + + my @chosen = map { $primes[$_] } grep { $select[$_] } 0..$nitems-1; + my $sum = sum0(@chosen); + #say "$i: b=$b, select=", join(',',@select), + # ", chosen=", join(',',@chosen), + # ", sum=$sum" if $debug; + next unless $sum == $m; + next unless @chosen == $n; + say "$i: b=$b, found a pp: ", join(',',@chosen) if $debug; + push @pp, join( ', ', @chosen); +} + +my $str = join( ' or ', @pp ); +say $str; diff --git a/challenge-172/duncan-c-white/perl/ch-2.pl b/challenge-172/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..06618cae8d --- /dev/null +++ b/challenge-172/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,63 @@ +#!/usr/bin/perl +# +# Task 2: Five-number Summary +# +# You are given an array of integers. Write a script to compute the +# five-number summary of the given set of integers. +# You can find the definition and example in the wikipedia page: +# https://en.wikipedia.org/wiki/Five-number_summary +# +# MY NOTES: Nice and simple: sort the data, pick the median, first and third +# quartile values. Note that the median can be the average (mean) of the +# two central values if the #values is even. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + +my $debug=0; +die "Usage: five-number-summary [--debug] list_of_ints\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>1; + +my @n = sort { $a <=> $b } @ARGV; +say "debug: sorted ", join(',', @n ) if $debug; + + +# +# my $median = median( @n ); +# Calculate the median value in the sorted array @n. +# +sub median +{ + my( @n ) = @_; + my $midpos = int(@n/2); + my $median = @n%2 == 0 ? ($n[$midpos-1]+$n[$midpos])/2 : $n[$midpos]; + return $median; +} + + +my $median = median( @n ); + +my $midpos = int(@n/2); +say "debug: midpos=$midpos" if $debug; + +my @h1 = @n[0..$midpos-1]; + +$midpos++ if @n%2 != 0; +my @h2 = @n[$midpos..@n-1]; + +say "debug: h1 = ", join(',',@h1), ", h2 = ", join(',',@h2) + if $debug; + +my $firstq = median( @h1 ); +my $thirdq = median( @h2 ); + +my $min = $n[0]; +my $max = $n[-1]; + +printf " %5.1f\n", $median; +printf "%5.1f %5.1f\n", $firstq, $thirdq; +printf "%5.1f %5.1f\n", $min, $max; -- cgit From ebff3d92804951f510087c8e24d5447d611c6a59 Mon Sep 17 00:00:00 2001 From: dcw Date: Tue, 19 Jul 2022 21:36:06 +0100 Subject: belatedly had a crack at challenge 173.. both probs done in Perl and C --- challenge-173/duncan-c-white/C/.cbuild | 3 +- challenge-173/duncan-c-white/C/Makefile | 14 +++ challenge-173/duncan-c-white/C/README | 9 ++ challenge-173/duncan-c-white/C/args.c | 174 ++++++++++++++++++++++++++++++ challenge-173/duncan-c-white/C/args.h | 7 ++ challenge-173/duncan-c-white/C/ch-1.c | 91 ++++++++++++++++ challenge-173/duncan-c-white/C/ch-2.c | 58 ++++++++++ challenge-173/duncan-c-white/README | 51 +++++---- challenge-173/duncan-c-white/perl/ch-1.pl | 90 ++++++++++++++++ challenge-173/duncan-c-white/perl/ch-2.pl | 59 ++++++++++ 10 files changed, 537 insertions(+), 19 deletions(-) create mode 100644 challenge-173/duncan-c-white/C/Makefile create mode 100644 challenge-173/duncan-c-white/C/README create mode 100644 challenge-173/duncan-c-white/C/args.c create mode 100644 challenge-173/duncan-c-white/C/args.h create mode 100644 challenge-173/duncan-c-white/C/ch-1.c create mode 100644 challenge-173/duncan-c-white/C/ch-2.c create mode 100755 challenge-173/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-173/duncan-c-white/perl/ch-2.pl diff --git a/challenge-173/duncan-c-white/C/.cbuild b/challenge-173/duncan-c-white/C/.cbuild index 7171ba4c65..fce622d376 100644 --- a/challenge-173/duncan-c-white/C/.cbuild +++ b/challenge-173/duncan-c-white/C/.cbuild @@ -1,3 +1,4 @@ -BUILD = ch-1 +BUILD = ch-1 ch-2 CFLAGS = -Wall +LDFLAGS = -lgmp #CFLAGS = -g diff --git a/challenge-173/duncan-c-white/C/Makefile b/challenge-173/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..9d1b99a602 --- /dev/null +++ b/challenge-173/duncan-c-white/C/Makefile @@ -0,0 +1,14 @@ +BUILD = ch-1 ch-2 +CC = gcc +CFLAGS = -Wall -g +LDLIBS = -lm -lgmp + +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 +ch-2: ch-2.o args.o +ch-2.o: ch-2.c args.h diff --git a/challenge-173/duncan-c-white/C/README b/challenge-173/duncan-c-white/C/README new file mode 100644 index 0000000000..d860e74093 --- /dev/null +++ b/challenge-173/duncan-c-white/C/README @@ -0,0 +1,9 @@ +Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C.. + +Both C versions produce identical (non-debugging) output to my Perl originals + +Both ch-1.c and ch-2.c use the command-line argument processing module +args.[ch], which I've tweaked slightly (adding a default value to +process_onenumarg()). + +ch-2.c uses libgmp, the Gnu multi-precision library, to provide bigint support. diff --git a/challenge-173/duncan-c-white/C/args.c b/challenge-173/duncan-c-white/C/args.c new file mode 100644 index 0000000000..77834b0d5b --- /dev/null +++ b/challenge-173/duncan-c-white/C/args.c @@ -0,0 +1,174 @@ +#include +#include +#include +#include + + +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 +#include +#include +//#include +#include +#include + +#include "args.h" + + + +// +// bool isesth = is_esthetic( n, msgbuf, bufsize ); +// Determine whether n is esthetic, returning the +// boolean answer to the question "is it esthetic?", +// and using msgbuf (a writable string buf of size bufsize) +// to store a printable explanation of why - or why not - +// n is esthetic, in the above format. +// |5 - 4| = |4 - 5| = |5 - 6| = 1 +// or |2 - 0| != 1 +// +bool is_esthetic( int n, char *msgbuf, int bufsize ) +{ + if( n<10 ) + { + assert( bufsize>20 ); + strcpy( msgbuf, "because no single digit is" ); + return 0; + } + + // convert n to string form (for easier access to digits) + char dig[100]; + sprintf( dig, "%d", n ); + int ndig = strlen(dig); + + // look for any pair of digits not differing by 1 + for( int i=0; i20 ); + sprintf( msgbuf, "|%c - %c| != 1", a, b ); + return 0; + } + } + + // ok, all pairs of digits differ by 1.. form msgbuf + strcpy( msgbuf, "" ); + int mlen = 0; + for( int i=0; i +#include +#include +#include +#include +#include +#include +#include + +// let's use the Gnu Multi Precision library +#include + +#include "args.h" + + +int main( int argc, char **argv ) +{ + int n; + process_onenumarg_default( "sylvester-numbers", argc, argv, 10, &n ); + + // set p to 2 + mpz_t p; + mpz_init_set_str( p, "2", 10 ); + + // sigh: need "one" + mpz_t one; + mpz_init_set_str( one, "1", 10 ); + + puts( "2" ); + + mpz_t next; + mpz_init( next ); + + for( int i; i n. +Write a script to find out if the given number is Esthetic Number. -For example, 945 is the first Abundant Odd Number. +An esthetic number is a positive integer where every adjacent digit +differs from its neighbour by +-1. -Sum of divisors: -1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975 +For example, -MY NOTES: ok, sounds easy, and at least it's nowt to do with Primes:-) +5456 is an esthetic number as |5 - 4| = |4 - 5| = |5 - 6| = 1 +120 is not an esthetic numner as |2 - 0| != 1 + +MY NOTES: ok, sounds quite easy. Let's make it slightly harder by allowing +ourselves (in debug mode) to reproduce the examples as written.. although +note that I've cheated slighltly: I've simplified the "not" output format +above to show only the first "|a-b| != 1", because it's not quite clear +what the output should be in all cases. 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: First-class Function +Task 2: Sylvester's sequence -Create sub compose($f, $g) which takes in two parameters $f and $g as -subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) -= $f->($g->($x)) +Write a script to generate first 10 members of Sylvester's sequence. For +more informations, please refer to the wikipedia page: + https://en.wikipedia.org/wiki/Sylvester%27s_sequence -e.g. +(In summary, each term of the sequence is the product of the previous +terms, plus one. The first few terms of the sequence are 2, 3, 7, 43, 1807) -$f = (one or more parameters function) -$g = (one or more parameters function) +Output -$h = compose($f, $g) -$f->($g->($x,$y, ..)) == $h->($x, $y, ..) for any $x, $y, ... +2 +3 +7 +43 +1807 +3263443 +10650056950807 +113423713055421844361000443 +12864938683278671740537145998360961546653259485195807 +165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 -MY NOTES: An interesting question at last. Think it's quite easy.. +MY NOTES: Also very easy, although the numbers grow ridiculously fast. +Sounds like a job for BigInt. diff --git a/challenge-173/duncan-c-white/perl/ch-1.pl b/challenge-173/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..89fcf6e671 --- /dev/null +++ b/challenge-173/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,90 @@ +#!/usr/bin/perl +# +# Task 1: Esthetic Number +# +# You are given a positive integer, $n. +# +# Write a script to find out if the given number is Esthetic Number. +# +# An esthetic number is a positive integer where every adjacent digit +# differs from its neighbour by +-1. +# +# For example, +# +# 5456 is an esthetic number as |5 - 4| = |4 - 5| = |5 - 6| = 1 +# 120 is not an esthetic numner as |2 - 0| != 1 +# +# MY NOTES: ok, sounds quite easy. Let's make it slightly harder by allowing +# ourselves (in debug mode) to reproduce the examples as written.. although +# note that I've cheated slighltly: I've simplified the "not" output format +# above to show only the first "|a-b| != 1", because it's not quite clear +# what the output should be in all cases. +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl +# into C (look in the C directory for that). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: esthetic-number [--debug] N\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==1; +my $n = shift; + +# +# my( $isesth, $mesg ) = is_esthetic( $n ); +# Determine whether $n is esthetic, returning a pair +# ($isesth, $mesg). $isesth is the boolean answer to the +# question "is it esthetic?", and $mesg is a printable +# explanation of why - or why not - in the above format. +# |5 - 4| = |4 - 5| = |5 - 6| = 1 +# or |2 - 0| != 1 +# +sub is_esthetic +{ + my( $n ) = @_; + + return (0, "because no single digit is") if $n<10; + + # let's form a list of [prevdig, nextdig, diff] triples + my @dig = split( //, $n ); + my @trips = map { + my $a = $dig[$_]; + my $b = $dig[$_+1]; + [ $a, $b, abs($a-$b) ] + } 0..$#dig-1; + + #die Dumper \@trips; + my @not1 = grep { $trips[$_][2] != 1 } 0..$#trips; + #die Dumper \@not1; + + if( @not1 ) + { + my $not = $trips[shift @not1]; + my( $a, $b, $diff ) = @$not; + return ( 0, "|$a - $b| != 1" ); + } + + my $mesg = join( " = ", map { + my $not = $trips[$_]; + my( $a, $b, $diff ) = @$not; + "|$a - $b|" + } 0..$#trips ) . " = 1"; + return ( 1, $mesg ); +} + + +my( $isesth, $mesg ) = is_esthetic( $n ); +if( $debug ) +{ + my $not = $isesth ? "": " not"; + say "$n is$not an esthetic number as $mesg"; +} else +{ + say $isesth ? "yes" : "no"; +} diff --git a/challenge-173/duncan-c-white/perl/ch-2.pl b/challenge-173/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..6e2decd61f --- /dev/null +++ b/challenge-173/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,59 @@ +#!/usr/bin/perl +# +# Task 2: Sylvester's sequence +# +# Write a script to generate first 10 members of Sylvester's sequence. For +# more informations, please refer to the wikipedia page: +# https://en.wikipedia.org/wiki/Sylvester%27s_sequence +# +# (In summary, each term of the sequence is the product of the previous +# terms, plus one. The first few terms of the sequence are 2, 3, 7, 43, 1807) +# +# Output +# +# 2 +# 3 +# 7 +# 43 +# 1807 +# 3263443 +# 10650056950807 +# 113423713055421844361000443 +# 12864938683278671740537145998360961546653259485195807 +# 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 +# +# MY NOTES: Also very easy, although the numbers grow ridiculously fast. +# Sounds like a job for BigInt. +# +# You are given an array of integers. Write a script to compute the +# five-number summary of the given set of integers. +# You can find the definition and example in the wikipedia page: +# https://en.wikipedia.org/wiki/Five-number_summary +# +# MY NOTES: Nice and simple: sort the data, pick the median, first and third +# quartile values. Note that the median can be the average (mean) of the +# two central values if the #values is even. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use bigint; + +my $debug=0; +die "Usage: sylvester-numbers [--debug] N (default 10)\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; + +my $n = shift // 10; + +my $p = 2; +say $p; + +foreach my $i (1..$n-1) +{ + my $next = $p + 1; + say $next; + $p *= $next; +} -- cgit From 5badff2e0666b32a31c5704e6d54d1990bfcdad4 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 24 Jul 2022 23:03:35 +0100 Subject: added my solutions to this week's challenges, plus some optimizations of ch-1 in Perl (got it running 7x faster in the end), plus a translation of ch-1 into C as well (plus one optimization of the C code) --- challenge-174/duncan-c-white/C/.cbuild | 2 +- challenge-174/duncan-c-white/C/Makefile | 14 +++ challenge-174/duncan-c-white/C/README | 12 ++ challenge-174/duncan-c-white/C/args.c | 174 +++++++++++++++++++++++++++++ challenge-174/duncan-c-white/C/args.h | 7 ++ challenge-174/duncan-c-white/C/ch-1.c | 88 +++++++++++++++ challenge-174/duncan-c-white/C/ch-1a.c | 116 +++++++++++++++++++ challenge-174/duncan-c-white/README | 60 +++++++--- challenge-174/duncan-c-white/perl/Perms.pm | 46 ++++++++ challenge-174/duncan-c-white/perl/ch-1.pl | 60 ++++++++++ challenge-174/duncan-c-white/perl/ch-1a.pl | 62 ++++++++++ challenge-174/duncan-c-white/perl/ch-1b.pl | 79 +++++++++++++ challenge-174/duncan-c-white/perl/ch-1c.pl | 75 +++++++++++++ challenge-174/duncan-c-white/perl/ch-1d.pl | 79 +++++++++++++ challenge-174/duncan-c-white/perl/ch-1e.pl | 83 ++++++++++++++ challenge-174/duncan-c-white/perl/ch-1f.pl | 84 ++++++++++++++ challenge-174/duncan-c-white/perl/ch-1g.pl | 85 ++++++++++++++ challenge-174/duncan-c-white/perl/ch-2.pl | 77 +++++++++++++ challenge-174/duncan-c-white/perl/timeall | 5 + 19 files changed, 1189 insertions(+), 19 deletions(-) create mode 100644 challenge-174/duncan-c-white/C/Makefile create mode 100644 challenge-174/duncan-c-white/C/README create mode 100644 challenge-174/duncan-c-white/C/args.c create mode 100644 challenge-174/duncan-c-white/C/args.h create mode 100644 challenge-174/duncan-c-white/C/ch-1.c create mode 100644 challenge-174/duncan-c-white/C/ch-1a.c create mode 100644 challenge-174/duncan-c-white/perl/Perms.pm create mode 100755 challenge-174/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1a.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1b.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1c.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1d.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1e.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1f.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-1g.pl create mode 100755 challenge-174/duncan-c-white/perl/ch-2.pl create mode 100755 challenge-174/duncan-c-white/perl/timeall diff --git a/challenge-174/duncan-c-white/C/.cbuild b/challenge-174/duncan-c-white/C/.cbuild index 7171ba4c65..c205cb0889 100644 --- a/challenge-174/duncan-c-white/C/.cbuild +++ b/challenge-174/duncan-c-white/C/.cbuild @@ -1,3 +1,3 @@ -BUILD = ch-1 +BUILD = ch-1 ch-1a CFLAGS = -Wall #CFLAGS = -g diff --git a/challenge-174/duncan-c-white/C/Makefile b/challenge-174/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..2786b44ed1 --- /dev/null +++ b/challenge-174/duncan-c-white/C/Makefile @@ -0,0 +1,14 @@ +BUILD = ch-1 ch-1a +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 +ch-1a: ch-1a.o args.o +ch-1a.o: ch-1a.c args.h diff --git a/challenge-174/duncan-c-white/C/README b/challenge-174/duncan-c-white/C/README new file mode 100644 index 0000000000..b29b95c490 --- /dev/null +++ b/challenge-174/duncan-c-white/C/README @@ -0,0 +1,12 @@ +Thought I'd also have a go at translating ch-1.pl 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]. + +The C version (ch-1.c) is approx twice as fast than even my fastest +Perl version (ch-1g.pl). + +As a further optimization in ch-1a.c: let's pre-compute all the powers +of digits: this runs about 30% faster than ch-1.c did. + diff --git a/challenge-174/duncan-c-white/C/args.c b/challenge-174/duncan-c-white/C/args.c new file mode 100644 index 0000000000..77834b0d5b --- /dev/null +++ b/challenge-174/duncan-c-white/C/args.c @@ -0,0 +1,174 @@ +#include +#include +#include +#include + + +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 +#include +#include +//#include +#include +#include + +#include "args.h" + + +// +// int p = intpower( x, y ); +// Compute x**y (x to-the-power y). +// +int intpower( int x, int y ) +{ + int p = x; + for( int i=1; i +#include +#include +//#include +#include +#include + +#include "args.h" + + +unsigned long dpow[10][20]; // precomputed powers of digit ** n + + +// +// initialise_pow( ); +// Initialize the dpow[] array +void initialise_pow( void ) +{ + for( int d = 0; d<10; d++ ) + { + unsigned long dp = 1; + for( int p = 0; p<20; p++ ) + { + dpow[d][p] = dp; + dp *= d; + //printf( "dpow[%d][%d] = %lu\n", d, p, dpow[d][p] ); + } + } +} + + +// +// unsigned long p = intpower( x, y ); +// Compute x**y (x to-the-power y). +// +unsigned long intpower( int x, int y ) +{ + #if CALC + int p = x; + for( int i=1; i n. +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, 945 is the first Abundant Odd Number. +For example, -Sum of divisors: -1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975 +518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 -MY NOTES: ok, sounds easy, and at least it's nowt to do with Primes:-) + +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. 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: First-class Function +Task 2: Permutation Ranking + +You are given a list of integers with no duplicates, e.g. [0, 1, 2]. + +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. + +Please checkout this post for more informations and algorithm: + https://tryalgo.org/en/permutations/2016/09/05/permutation-rank/ + +Given the list [0, 1, 2] the ordered permutations are: + +0: [0, 1, 2] +1: [0, 2, 1] +2: [1, 0, 2] +3: [1, 2, 0] +4: [2, 0, 1] +5: [2, 1, 0] + +and therefore: -Create sub compose($f, $g) which takes in two parameters $f and $g as -subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) -= $f->($g->($x)) +permutation2rank([1, 0, 2]) = 2 -e.g. +rank2permutation([0, 1, 2], 1) = [0, 2, 1] -$f = (one or more parameters function) -$g = (one or more parameters function) -$h = compose($f, $g) -$f->($g->($x,$y, ..)) == $h->($x, $y, ..) for any $x, $y, ... +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! -MY NOTES: An interesting question at last. Think it's quite easy.. +I didn't have time to translate this (and the Perms module) to C, although it +should be pretty straightforward. diff --git a/challenge-174/duncan-c-white/perl/Perms.pm b/challenge-174/duncan-c-white/perl/Perms.pm new file mode 100644 index 0000000000..ce65b89760 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/Perms.pm @@ -0,0 +1,46 @@ +package Perms; + +# +# Generate permutations, one at a time, using a +# standard lexicographic permutation algorithm. +# + +use strict; +use warnings; +use feature 'say'; +#use Data::Dumper; + +# +# my $next = next_perm( $val ); +# Find and return the next permutation in lexicographic order +# of $val. Return undef is $val is the last permutation (in order). +# Algorithm treats $val as an array of digits a[n]: +# 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, +# the permutation is the last permutation. +# 2. Find the largest index l greater than k such that a[k] < a[l]. +# 3. Swap the value of a[k] with that of a[l]. +# 4. Reverse the sequence from a[k + 1] up to and including the final element a[n]. +# +sub next_perm ($) +{ + my( $val )= @_; + my @a = split( //, $val ); + my( $k, $l ); + my $n = @a-1; + for( $k=$n-1; $k>=0 && ord($a[$k])>=ord($a[$k+1]); $k-- ) + { + } + return undef if $k<0; + for( $l=$n; $l>$k && ord($a[$k])>=ord($a[$l]); $l-- ) + { + } + ( $a[$k], $a[$l] ) = ( $a[$l], $a[$k] ); + + # reverse a[k+1]..a[n] + @a[$k+1..$n] = reverse @a[$k+1..$n]; + + return join( '', @a ); +} + + +1; diff --git a/challenge-174/duncan-c-white/perl/ch-1.pl b/challenge-174/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..77457893b9 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,60 @@ +#!/usr/bin/perl +# +# Task 1: Disarium Numbers +# +# Write a script to generate first 19 Disarium Numbers. +# +# 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, +# +# 518 is a disarium number as +# (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 +# +# MY NOTES: ok, sounds pretty easy. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: first-N-disarium-numbers [--debug] [N default 19]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 19; + +# +# my $isdis = disarium( $x ); +# Return 1 iff $x is a disarium number; 0 otherwise. +# +sub disarium +{ + my( $x ) = @_; + my @dig = split( //, $x ); + my $sum = 0; + for( my $pos=0; $pos < @dig; $pos++ ) + { + $sum += $dig[$pos] ** ($pos+1); + } + say "debug: dis($x): sum=$sum" if $debug; + return $sum == $x ? 1 : 0; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found; +for( my $i = 0; @found < $n; $i++ ) +{ + # check if $i is a disarium number, if so add it to @found + next unless disarium($i); + say "debug: found dis $i" if $debug; + push @found, $i; +} + +say join(',', @found ); diff --git a/challenge-174/duncan-c-white/perl/ch-1a.pl b/challenge-174/duncan-c-white/perl/ch-1a.pl new file mode 100755 index 0000000000..20b4744616 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1a.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl +# +# Task 1: Disarium Numbers +# +# Write a script to generate first 19 Disarium Numbers. +# +# 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, +# +# 518 is a disarium number as +# (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 +# +# MY NOTES: ok, sounds pretty easy. +# This version (ch-1a.pl) makes a tiny optimization: stop the loop if +# sum exceeds $x. Sadly, this runs slower than the original! +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: first-N-disarium-numbers [--debug] [N default 19]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 19; + +# +# my $isdis = disarium( $x ); +# Return 1 iff $x is a disarium number; 0 otherwise. +# +sub disarium +{ + my( $x ) = @_; + my @dig = split( //, $x ); + my $sum = 0; + for( my $pos=0; $pos < @dig && $sum < $x; $pos++ ) + { + $sum += $dig[$pos] ** ($pos+1); + } + say "debug: dis($x): sum=$sum" if $debug; + return $sum == $x ? 1 : 0; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found; +for( my $i = 0; @found < $n; $i++ ) +{ + # check if $i is a disarium number, if so add it to @found + next unless disarium($i); + say "debug: found dis $i" if $debug; + push @found, $i; +} + +say join(',', @found ); diff --git a/challenge-174/duncan-c-white/perl/ch-1b.pl b/challenge-174/duncan-c-white/perl/ch-1b.pl new file mode 100755 index 0000000000..97f744e86e --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1b.pl @@ -0,0 +1,79 @@ +#!/usr/bin/perl +# +# Task 1: Disarium Numbers +# +# Write a script to generate first 19 Disarium Numbers. +# +# 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, +# +# 518 is a disarium number as +# (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 +# +# MY NOTES: ok, sounds pretty easy. +# This version (ch-1b.pl) makes a tiny optimization: precompute the digit +# powers, storing them in an array. Sadly, this runs no faster than the +# original, I guess '**' must be well optimized in Perl. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: first-N-disarium-numbers [--debug] [N default 19]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 19; + +# precompute the digit powers.. + +my @dp; # dp[dig][pow] = dig**pow +foreach my $dig (0..9) +{ + $dp[$dig] = []; + my $p = $dig; + foreach my $pow (1..10) + { + $dp[$dig][$pow] = $p; + $p *= $dig; + } +} +#die Dumper \@dp; + + +# +# my $isdis = disarium( $x ); +# Return 1 iff $x is a disarium number; 0 otherwise. +# +sub disarium +{ + my( $x ) = @_; + my @dig = split( //, $x ); + my $sum = 0; + for( my $pos=0; $pos < @dig; $pos++ ) + { + $sum += $dp[$dig[$pos]][$pos+1]; + } + say "debug: dis($x): sum=$sum" if $debug; + return $sum == $x ? 1 : 0; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found; +for( my $i = 0; @found < $n; $i++ ) +{ + # check if $i is a disarium number, if so add it to @found + next unless disarium($i); + say "debug: found dis $i" if $debug; + push @found, $i; +} + +say join(',', @found ); diff --git a/challenge-174/duncan-c-white/perl/ch-1c.pl b/challenge-174/duncan-c-white/perl/ch-1c.pl new file mode 100755 index 0000000000..def483e33c --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1c.pl @@ -0,0 +1,75 @@ +#!/usr/bin/perl +# +# Task 1: Disarium Numbers +# +# Write a script to generate first 19 Disarium Numbers. +# +# 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, +# +# 518 is a disarium number as +# (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 +# +# MY NOTES: ok, sounds pretty easy. +# This version (ch-1c.pl) makes a tiny optimization: cache disarium sums, +# as we are checking successively bigger numbers for "disarium-ness". +# This minor change makes it run about 3 TIMES FASTER than the original! +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: first-N-disarium-numbers [--debug] [N default 19]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 19; + +my @dsum; # cache of disarium sum + + +# +# my $isdis = disarium( $x ); +# Return 1 iff $x is a disarium number; 0 otherwise. +# +sub disarium +{ + my( $x ) = @_; + my( $xd10, $xm10 ) = ( int($x/10), $x % 10 ); + my $sum = 0; + if( defined $dsum[$xd10] ) + { + my $len = length($x); + $sum = $dsum[$xd10] + $xm10 ** $len; + } else + { + my @dig = split( //, $x ); + for( my $pos=0; $pos < @dig; $pos++ ) + { + $sum += $dig[$pos] ** ($pos+1); + } + } + $dsum[$x] = $sum; + say "debug: dis($x): sum=$sum" if $debug; + return $sum == $x ? 1 : 0; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found; +for( my $i = 0; @found < $n; $i++ ) +{ + # check if $i is a disarium number, if so add it to @found + next unless disarium($i); + say "debug: found dis $i" if $debug; + push @found, $i; +} + +say join(',', @found ); diff --git a/challenge-174/duncan-c-white/perl/ch-1d.pl b/challenge-174/duncan-c-white/perl/ch-1d.pl new file mode 100755 index 0000000000..86e6aeb48a --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1d.pl @@ -0,0 +1,79 @@ +#!/usr/bin/perl +# +# Task 1: Disarium Numbers +# +# Write a script to generate first 19 Disarium Numbers. +# +# 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, +# +# 518 is a disarium number as +# (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518 +# +# MY NOTES: ok, sounds pretty easy. +# This version (ch-1d.pl) makes another optimization: turn disarium() into +# disarium_inorder() that MUST be called with each value of $x in order +# which allows various optimizations. +# This minor change makes it run about 20% faster, but is a stepping stone +# to better things to come. +# + +use strict; +use warnings; +use feature 'say'; +use feature 'state'; +use Getopt::Long; +use Data::Dumper; + + +my $debug=0; +die "Usage: first-N-disarium-numbers [--debug] [N default 19]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $n = shift // 19; + + + +# +# my $isdis = disarium_inorder( $x ); +# Return 1 iff $x is a disarium number; 0 otherwise. +# ONLY WORKS IF THIS IS INVOKED FOR EACH VALUE OF $x IN ORDER +# +sub disarium_inorder +{ + my( $x ) = @_; + state @dsum; # cache of disarium sum + state $len = 1; # length of $x + state $pten = 10;# next power of 10 + if( $x<10 ) + { + $dsum[$x] = $x; + return 1; + } + my( $xd10, $xm10 ) = ( int($x/10), $x % 10 ); + my $sum = $dsum[$xd10] + $xm10 ** $len; + $dsum[$x] = $sum; + say "debug: dis($x): sum=$sum" if $debug; + if( $x == $pten ) + { + $len++; + $pten *= 10; + } + return $sum == $x ? 1 : 0; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found; +for( my $i = 0; @found < $n; $i++ ) +{ + # check if $i is a disarium number, if so add it to @found + next unless disarium_inorder($i); + say "debug: found dis $i" if $debug; + push @found, $i; +} + +say join(',', @found ); diff --git a/challenge-174/duncan-c-white/perl/ch-1e.pl b/challenge-174/duncan-c-white/perl/ch-1e.pl new file mode 100755 index 0000000000..fad33280c0 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-