Merge pull request #5486 from dcw803/master

imported my solutions to both tasks

4 files changed, 231 insertions, 53 deletions

diff --git a/challenge-146/duncan-c-white/README b/challenge-146/duncan-c-white/README
index bdbeb3c3a5..aae0f64482 100644
--- a/challenge-146/duncan-c-white/README
+++ b/challenge-146/duncan-c-white/README
@@ -1,71 +1,39 @@
-TASK #1 - Dot Product
+TASK #1 - 10001st Prime Number
 
-You are given 2 arrays of same size, @a and @b.
+Write a script to generate the 10001st prime number.
 
-Write a script to implement Dot Product.
+(Remember that 2 is the 1st prime number).
 
-Example:
 
-	@a = (1, 2, 3);
-	@b = (4, 5, 6);
+MY NOTES: Very easy, especially (tada) if you happen to have a prime
+generating module that you've already used several times in these
+challenges..
 
-	$dot_product = (1 * 4) + (2 * 5) + (3 * 6) => 4 + 10 + 18 => 32
 
-MY NOTES: Very easy.
+TASK #2 - Curious Fraction Tree
 
+Consider the following Curious Fraction Tree:
 
-TASK #2 - Palindromic Tree
+[diagram in which the root is 1/1, and for each element N/D
+it's right child is N+D/D, and it's left child is N/N+D]
 
-You are given a string $s.
+You are given a N/D member of the tree created similar to the above sample.
 
-Write a script to create a Palindromic Tree for the given string.
-
-I found this blog exaplaining Palindromic Tree in detail:
-
-https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b
+Write a script to find out the parent and grandparent of the given member.
 
 Example 1:
 
-	Input: $s = 'redivider'
-	Output: r redivider e edivide d divid i ivi v
+    Input: $member = '3/5';
+    Output: parent = '3/2' and grandparent = '1/2'
 
 Example 2:
 
-	Input: $s = 'deific'
-	Output: d e i ifi f c
-
-Example 3:
-
-	Input: $s = 'rotors'
-	Output: r rotor o oto t s
-
-Example 4:
-
-	Input: $s = 'challenge'
-	Output: c h a l ll e n g
-
-Example 5:
-
-	Input: $s = 'champion'
-	Output: c h a m p i o n
-
-Example 6:
-
-	Input: $s = 'christmas'
-	Output: c h r i s t m a
-
-MY NOTES: hmm..  I read the blog, but what on earth is it
-talking about, it's not very clear?  the underlying paper
-https://arxiv.org/pdf/1506.04862.pdf is a lot clearer, but
-still way too detailed for 10pm on a Sunday.
+    Input: $member = '4/3';
+    Output: parent = '1/3' and grandparent = '1/2'
 
-Looking at the examples given above, the output seems to be
-a list of palindromic substrings not previously encountered,
-in the natural order found by sequencing through every starting
-position in the word and trying increasingly long substrings
-for "Palindromic"-ness.
+MY NOTES: hmm..  having determined the left and right child rules
+above, I worked out that given a child N/D the parent rule is
+"if D>N then (N, D-N) else (N-D, D)"
 
-So, could we solve the "generate the output from the input"
-problem, entirely ignoring the whole "build a weird tree"
-part of it?  Presumably a lot less efficient than their
-clever eertree/Palindrome tree thingy, but who cares.
+So very easy using that rule twice (and why not go all the way up to
+the root while we're doing it).
diff --git a/challenge-146/duncan-c-white/perl/MakePrimes.pm b/challenge-146/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..6b5cd8e9fe
--- /dev/null
+++ b/challenge-146/duncan-c-white/perl/MakePrimes.pm
@@ -0,0 +1,97 @@
+#
+#	mkprimes module (converted from mkprimes.c)
+#
+
+use strict;
+use warnings;
+use Function::Parameters;
+
+
+my $debug = 0;
+my @foundprimes;	# remember all primes we've found..
+
+
+fun prime_debug( $d )
+{
+	$debug = $d;
+}
+
+
+#
+# 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" if $debug;
+
+	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-146/duncan-c-white/perl/ch-1.pl b/challenge-146/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..c90a9b20de
--- /dev/null
+++ b/challenge-146/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,49 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - 10001st Prime Number
+# 
+# Write a script to generate the 10001st prime number.
+# 
+# (Remember that 2 is the 1st prime number).
+# 
+# 
+# MY NOTES: Very easy, especially (tada) if you happen to have a prime
+# generating module that you've already used several times in these
+# challenges..
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+
+use lib qw(.);
+use MakePrimes;
+
+my $debug=0;
+die "Usage: nth-prime [--debug] [N, default 10001]\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV<2;
+
+my $n = shift // 10001;
+
+prime_debug( $debug );
+
+my $bandwidth = 10000;
+my $upto = $bandwidth;
+my @primes = primes_upto( $upto );
+
+#die Dumper(\@primes);
+
+my $primesfound = @primes;
+
+while( $primesfound < $n )
+{
+	my $from = $upto;
+	$upto += $bandwidth;
+	my @moreprimes = more_primes( $from, $upto );
+	push @primes, @moreprimes;
+	$primesfound = @primes;
+}
+
+say $primes[$n-1];
diff --git a/challenge-146/duncan-c-white/perl/ch-2.pl b/challenge-146/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..c14d2ac179
--- /dev/null
+++ b/challenge-146/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,64 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Curious Fraction Tree
+# 
+# Consider the following Curious Fraction Tree:
+# 
+# [diagram in which the root is 1/1, and for each element N/D
+# it's right child is N+D/D, and it's left child is N/N+D]
+# 
+# You are given a N/D member of the tree created similar to the above sample.
+# 
+# Write a script to find out the parent and grandparent of the given member.
+# 
+# Example 1:
+# 
+#     Input: $member = '3/5';
+#     Output: parent = '3/2' and grandparent = '1/2'
+# 
+# Example 2:
+# 
+#     Input: $member = '4/3';
+#     Output: parent = '1/3' and grandparent = '1/2'
+# 
+# MY NOTES: hmm..  having determined the left and right child rules
+# above, I worked out that given a child N/D the parent rule is
+# "if D>N then (N, D-N) else (N-D, D)"
+# 
+# So very easy using that rule twice (and why not go all the way up to
+# the root while we're doing it).
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use Function::Parameters;
+
+
+my $debug=0;
+
+
+die "Usage: curious-fraction-tree-ancestors [--debug] N/D\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $s = shift;
+
+die "cft: bad N/D string $s\n" unless $s =~ m|^(\d+)/(\d+)$|;
+my( $n, $d ) = ( $1, $2 );
+
+my $label = "parent";
+
+while( $n>0 && $d>0 )
+{
+	# change (n,d) to parent(n,d)
+	if( $d > $n )
+	{
+		$d -= $n;
+	} else
+	{
+		$n -= $d;
+	}
+	say "$label: $n/$d" if $n>0 && $d>0;
+	$label = "grand$label";
+}