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-1e.pl @@ -0,0 +1,83 @@ +#!/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-1e.pl) makes another optimization: turn disarium_inorder() +# into next_disarium() that find the NEXT disarium number, this allows it to +# embed a fast loop inside it, share some of the calculations, plus of course +# the Perl interpreter has to execute millions fewer subroutine calls. +# these minor changes makes it run about twice as fast as ch-1d.pl +# + +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 $nextdis = next_disarium( $x ); +# Return the next disarium number >= $x +# +sub next_disarium +{ + 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 $x; + } + my $sum; + $x--; + do + { + $x++; + my $xd10 = int($x/10); + $sum = $dsum[$xd10] + ($x % 10) ** $len; + $dsum[$x] = $sum; + say "debug: dis($x): sum=$sum" if $debug; + if( $x == $pten ) + { + $len++; + $pten *= 10; + } + } while( $sum != $x ); + return $x; +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found = (0); +for( my $i = 1; @found < $n; $i++ ) +{ + $i = next_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-1f.pl b/challenge-174/duncan-c-white/perl/ch-1f.pl new file mode 100755 index 0000000000..31d70ef37f --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1f.pl @@ -0,0 +1,84 @@ +#!/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-1f.pl) makes a small optimization: it tries to avoid +# recalculating $ds, the dsum of the prefix, as that only changes once every +# 10 times. The code is also slightly neater. +# This minor change makes it run about 10% faster than as ch-1e.pl +# + +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 $nextdis = next_disarium( $x ); +# Return the next disarium number >= $x +# +sub next_disarium +{ + 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 $x; + } + my $ds = $dsum[int($x/10)]; + for(;;) + { + $ds = $dsum[int($x/10)] if $x%10==0; + if( $x == $pten ) + { + $len++; + $pten *= 10; + } + my $sum = $ds + ($x%10) ** $len; + $dsum[$x] = $sum; + say "debug: dis($x): sum=$sum" if $debug; + if( $sum == $x ) + { + return $x; + } + $x++; + } +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found = (0); +for( my $i = 1; @found < $n; $i++ ) +{ + $i = next_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-1g.pl b/challenge-174/duncan-c-white/perl/ch-1g.pl new file mode 100755 index 0000000000..61230ad141 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-1g.pl @@ -0,0 +1,85 @@ +#!/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-1g.pl) makes a final small optimization: it tries to avoid +# recalculating $x % 10 every time, as the increments with x (until x%10==0). +# This minor change makes it run about 5% faster than as ch-1f.pl +# + +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 $nextdis = next_disarium( $x ); +# Return the next disarium number >= $x +# +sub next_disarium +{ + 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 $x; + } + my $ds = $dsum[int($x/10)]; + my $digit = $x % 10; + for(;;) + { + $ds = $dsum[int($x/10)] if $digit==0; + if( $x == $pten ) + { + $len++; + $pten *= 10; + } + my $sum = $dsum[$x] = $ds + $digit ** $len; + say "debug: dis($x): sum=$sum" if $debug; + if( $sum == $x ) + { + return $x; + } + $x++; + $digit++; + $digit=0 if $digit==10; + } +} + + +#my $is = disarium(518); +#die "debug: dis(518) = $is\n"; + + +my @found = (0); +for( my $i = 1; @found < $n; $i++ ) +{ + $i = next_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-2.pl b/challenge-174/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..0603e76ed7 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,77 @@ +#!/usr/bin/perl +# +# 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: +# +# permutation2rank([1, 0, 2]) = 2 +# +# rank2permutation([0, 1, 2], 1) = [0, 2, 1] +# +# 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 does this, so let's reuse it to do the simplest possible +# version of this without really thinking over-hard. +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl +# into C (look in the C directory for that). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + +use lib qw(.); +use Perms; + +my $debug=0; +die "Usage: permute-stuff [--debug] string-of-digits (p2r | r2p R)\n" + unless GetOptions( "debug"=>\$debug ) && (@ARGV==2 || @ARGV==3); + +my $list = shift; +my $cmd = shift; +die "permute-stuff: bad command $cmd (should be p2r or r2p)\n" + unless $cmd eq "p2r" || $cmd eq "r2p"; +my @list = split( //, $list ); +my $perm = join( '', sort { $a <=> $b } @list ); + +if( $cmd eq "p2r" ) # permutation to rank +{ + my $rank; + for( $rank=0; $list ne $perm; $rank++ ) + { + $perm = Perms::next_perm( $perm ); + } + say "p2r($list) = $rank"; +} else +{ + die "permute-stuff: r2p needs to be followed by a rank no\n" + if @ARGV==0; + my $rank = shift; + for( my $i=0; $i != $rank; $i++ ) + { + $perm = Perms::next_perm( $perm ); + } + say "r2p( $list, $rank ) = $perm"; +} diff --git a/challenge-174/duncan-c-white/perl/timeall b/challenge-174/duncan-c-white/perl/timeall new file mode 100755 index 0000000000..a37c799815 --- /dev/null +++ b/challenge-174/duncan-c-white/perl/timeall @@ -0,0 +1,5 @@ +#!/bin/csh -f +foreach i ( ch-1*.pl ) + echo $i + time ./$i +end -- cgit