Merge pull request #5000 from dcw803/master

added my solutions to this week's tasks.. both pretty easy this week

4 files changed, 293 insertions, 88 deletions

diff --git a/challenge-133/duncan-c-white/README b/challenge-133/duncan-c-white/README
index 4918f2b94a..7c8d08653f 100644
--- a/challenge-133/duncan-c-white/README
+++ b/challenge-133/duncan-c-white/README
@@ -1,106 +1,44 @@
-TASK #1 - Mirror Dates
+TASK #1 - Integer Square Root
 
-You are given a date (yyyy/mm/dd).
+You are given a positive integer $N.
 
-Assuming, the given date is your date of birth. Write a script to find
-the mirror dates of the given date.
+Write a script to calculate the integer square root of the given number.
 
-Assuming today is 2021/09/22.
+Please avoid using a built-in function. Find out more about it:
 
-Example 1:
+https://en.wikipedia.org/wiki/Integer_square_root
 
-Input: 2021/09/18
-Output: 2021/09/14, 2021/09/26
+Examples
 
-On the date you were born, someone who was your current age, would have
-been born on 2021/09/14.  Someone born today will be your current age
-on 2021/09/26.
+  Input: $N = 10
+  Output: 3
 
-Example 2:
+  Input: $N = 27
+  Output: 5
 
-Input: 1975/10/10
-Output: 1929/10/27, 2067/09/05
+  Input: $N = 85
+  Output: 9
 
-On the date you were born, someone who was your current age, would have
-been born on 1929/10/27.  Someone born today will be your current age
-on 2067/09/05.
+  Input: $N = 101
+  Output: 10
 
-Example 3:
+MY NOTES: Pretty easy as the Wikipedia page shows a C implementation
 
-Input: 1967/02/14
-Output: 1912/07/08, 2076/04/30
 
-On the date you were born, someone who was your current age, would have
-been born on 1912/07/08.  Someone born today will be your current age
-on 2076/04/30.
+TASK #2 - Smith Numbers
 
-MY NOTES: Sounds like a pretty easy date manipulation exercise:  dob - delta,
-today + delta where delta = today - date.  The hardest part is working out
-which Date manipulation module to use, as Perl has so many.
+Write a script to generate first 10 Smith Numbers in base 10.
 
+According to Wikipedia:
 
-TASK #2 - Hash Join
+"In number theory, a Smith number is a composite number for which, in
+a given number base, the sum of its digits is equal to the sum of the
+digits in its prime factorization in the given number base."
 
-Write a script to implement Hash Join algorithm as suggested by wikipedia.
+MY NOTES: Ok, an example in the Wikipedia clarifies this:
 
-1. For each tuple r in the build input R
-    1.1 Add r to the in-memory hash table
-    1.2 If the size of the hash table equals the maximum in-memory size:
-        1.2.1 Scan the probe input S, and add matching join tuples to the output relation
-        1.2.2 Reset the hash table, and continue scanning the build input R
-2. Do a final scan of the probe input S and add the resulting join tuples to the output relation
+    4937775 = 3**1 5**2 658371 (prime factors)
+    4 + 9 + 3 + 7 + 7 + 7 + 5 = 42
+    3 x· 1 + 5x 2 + (6 + 5 + 8 + 3 + 7) x 1 = 42 too
 
-Example
-
-Input:
-
-    @player_ages = (
-        [20, "Alex"  ],
-        [28, "Joe"   ],
-        [38, "Mike"  ],
-        [18, "Alex"  ],
-        [25, "David" ],
-        [18, "Simon" ],
-    );
-
-    @player_names = (
-        ["Alex", "Stewart"],
-        ["Joe",  "Root"   ],
-        ["Mike", "Gatting"],
-        ["Joe",  "Blog"   ],
-        ["Alex", "Jones"  ],
-        ["Simon","Duane"  ],
-    );
-
-Output:
-
-    Based on index = 1 of @players_age and index = 0 of @players_name.
-
-    20, "Alex",  "Stewart"
-    20, "Alex",  "Jones"
-    18, "Alex",  "Stewart"
-    18, "Alex",  "Jones"
-    28, "Joe",   "Root"
-    28, "Joe",   "Blog"
-    38, "Mike",  "Gatting"
-    18, "Simon", "Duane"
-
-MY NOTES: Ok, I think I understand, but I'm going to ignore the
-whole "out of memory" part as that's too complicated.
-Also, I can't see what logical order the example output is ordered by,
-as far as I can see, the described algorithm leads to the order that I
-produce - not the order the above example output shows; so I'm going to
-ignore that too.  After all, in a relation, order doesn't matter, right?
-
-So for the example I build %name2ages containing:
-"Alex" => [20, 18],
-"Joe" => [28],
-"Mike" => [38],
-"David" => [25],
-"Simon" => [18].
-Then use %name2ages while iterating over @player_names.
-
-There's also the question of how to provide the relations,
-in ch-2.pl I hard-coding them as arrays of pairs as shown above,
-but see also ch-2a.pl which generalises them as files, read by Text::CSV
-and containing fieldnames in row 1.
+Should be quite straightforward.
diff --git a/challenge-133/duncan-c-white/perl/MakePrimes.pm b/challenge-133/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..7261977c57
--- /dev/null
+++ b/challenge-133/duncan-c-white/perl/MakePrimes.pm
@@ -0,0 +1,91 @@
+#
+#	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-133/duncan-c-white/perl/ch-1.pl b/challenge-133/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..9f0dc28028
--- /dev/null
+++ b/challenge-133/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,65 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Integer Square Root
+#
+# You are given a positive integer $N.
+# 
+# Write a script to calculate the integer square root of the given number.
+# 
+# Please avoid using a built-in function. Find out more about it:
+# 
+# https://en.wikipedia.org/wiki/Integer_square_root
+# 
+# Examples
+# 
+#   Input: $N = 10
+#   Output: 3
+# 
+#   Input: $N = 27
+#   Output: 5
+# 
+#   Input: $N = 85
+#   Output: 9
+# 
+#   Input: $N = 101
+#   Output: 10
+# 
+# MY NOTES: Pretty easy as the Wikipedia page shows a C implementation
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+#
+# my $isqrt = isqrt($n);
+#	Return the integer sqrt of $n.
+#
+sub isqrt
+{
+	my( $n ) = @_;
+
+	return $n if $n < 2;
+
+	my $x0 = $n >> 1;			# Initial estimate
+
+	my $x1 = ( $x0 + $n / $x0 ) >> 1;	# Update
+		
+	while ( $x1 < $x0 )			# This also checks for cycle
+	{
+		$x0 = $x1;
+		$x1 = ( $x0 + $n / $x0 ) >> 1;
+	}
+	
+	return $x0;
+}
+
+
+my $debug=0;
+die "Usage: int-sqrt N\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $n = shift @ARGV;
+
+say isqrt($n);
diff --git a/challenge-133/duncan-c-white/perl/ch-2.pl b/challenge-133/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..b343c6af2a
--- /dev/null
+++ b/challenge-133/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,111 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Smith Numbers
+# 
+# Write a script to generate first 10 Smith Numbers in base 10.
+# 
+# According to Wikipedia:
+# 
+# "In number theory, a Smith number is a composite number for which, in
+# a given number base, the sum of its digits is equal to the sum of the
+# digits in its prime factorization in the given number base."
+# 
+# MY NOTES: Ok, an example in the Wikipedia clarifies this:
+# 
+#     4937775 = 3**1 5**2 658371 (prime factors)
+#     4 + 9 + 3 + 7 + 7 + 7 + 5 = 42
+#     3 x 1 + 5 x 2 + (6 + 5 + 8 + 3 + 7) x 1 = 42 too
+# 
+# Should be quite straightforward.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Getopt::Long;
+use Data::Dumper;
+use List::Util qw(sum);
+
+use lib qw(.);
+use MakePrimes;
+
+my $debug = 0;
+
+die "Usage: smith-nos [-d|--debug] [FIRSTN]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $firstn = shift @ARGV // 10;
+
+my @primes = primes_upto( 2000 );
+my %isprime = map { $_ => 1 } @primes;
+
+
+#
+# my @pfact = prime_factors( $n, @primes );
+#	Split $n into it's list of one or more prime factors,
+#	using @primes to determine prime-ness or not.  Return the list.
+#	eg. prime_factors( 332, (2,3,5,7,11,13,17) ) is 2 x 2 x 83, ie (2,2,83)
+#
+fun prime_factors( $n, @primes )
+{
+	my $orig = $n;
+	#say "debug: pf($n): primes=".join(',',@primes)."\n";
+	return ( $n ) if $n<=2;
+
+	my @result;
+	foreach my $f (@primes)
+	{
+		return @result if $f > $n;
+		while( $n % $f == 0 )
+		{
+			push @result, $f;
+			$n /= $f;
+		}
+	}
+	die "prime_factors($orig,".join(',',@primes)."): @ end n ($n) should be 1, where result=".
+	    join(',',@result)."\n" unless $n == 1;
+	return @result;
+}
+
+#my @pfact = prime_factors( 2, @primes );
+#say "debug pf(2): ". join(',',@pfact);
+#
+#@pfact = prime_factors( 3, @primes );
+#say "debug pf(3): ". join(',',@pfact);
+#
+#@pfact = prime_factors( 4, @primes );
+#say "debug pf(4): ". join(',',@pfact);
+#
+#@pfact = prime_factors( 332, @primes );
+#say "debug pf(332): ". join(',',@pfact);
+
+
+#
+# my $is = is_smith($x);
+#	Return true iff $x is a SMITH NUMBER, as described above.
+#
+fun is_smith( $x )
+{
+	return 0 if $isprime{$x};
+
+	my @pfact = prime_factors( $x, @primes );
+	#die "debug: pf($x) = ".join(',',@pfact);
+
+	my $sumdigits = sum( split(//,$x ) );		# sum of digits
+	#say "debug: smth($x): sumdigits=$sumdigits";
+
+	my $sumpf = sum( map { sum( split(//,$_) ) } @pfact );
+	#say "debug: smth($x): sumpf=$sumpf";
+
+	return 0 unless $sumdigits == $sumpf;
+	return 1;
+}
+
+
+for( my $nfound = 0, my $x = 2; $nfound < $firstn; $x++ )
+{
+	next unless is_smith($x);
+	$nfound++;
+	print "$x,";
+}
+print "\n";