Merge pull request #3839 from dcw803/master

imported last week's solutions (after forgetting to do it yesterday)

3 files changed, 201 insertions, 30 deletions

diff --git a/challenge-106/duncan-c-white/README b/challenge-106/duncan-c-white/README
index e2e541033b..cf5c006dc0 100644
--- a/challenge-106/duncan-c-white/README
+++ b/challenge-106/duncan-c-white/README
@@ -1,48 +1,47 @@
-Task 1: "Nth root
+Task 1: "Maximum Gap
 
-You are given positive numbers $N and $k.
+You are given an array of integers @N.
 
-Write a script to find out the $Nth root of $k. For more information,
-please take a look at
-https://en.wikipedia.org/wiki/Nth_root#Computing_principal_roots
+Write a script to display the maximum difference between two successive
+elements once the array is sorted.
+If the array contains only 1 element then display 0.
 
 Example
 
-	Input: $N = 5, $k = 248832
-	Output: 12
+	Input: @N = (2, 9, 3, 5)
+	Output: 4
 
-	Input: $N = 5, $k = 34
-	Output: 2.02
+	Input: @N = (1, 3, 8, 2, 0)
+	Output: 5
+
+	Input: @N = (5)
+	Output: 0
 "
 
-My notes: ok, dull but easy, using the Newton-Raphson Method.
+My notes: should be easy.
 
 
-Task 2: "The Name Game
+Task 2: "Decimal String
 
-You are given a $name.
+You are given numerator and denominator i.e. $N and $D.
 
-Write a script to display the lyrics to the Shirley Ellis song The Name
-Game. Please checkout https://en.wikipedia.org/wiki/The_Name_Game
-for more information.
+Write a script to convert the fraction into decimal string. If the
+fractional part is recurring then put it in parenthesis.
 
 Example
 
-  Input: $name = "Katie"
-  Output:
+	Input: $N = 1, $D = 3
+	Output: "0.(3)"
+
+	Input: $N = 1, $D = 2
+	Output: "0.5"
 
-    Katie, Katie, bo-batie,
-    Bonana-fanna fo-fatie
-    Fee fi mo-matie
-    Katie!
+	Input: $N = 5, $D = 66
+	Output: "0.0(75)"
 "
 
-My notes: wtf?  are we reduced to ill-defined childhood rhymes now?
-use simple rules:
-- remove first consonant from name if the first letter is a consonant,
-- otherwise leave the name alone.
-- if the removed consonant was b, f or m, then (respectively) bo-b
-  becomes bo-, fo-f becomes fo-, and mo-m becomes mo-
-- ignore the "no indication what to do with names like Anita where the stress
-  falls on a later syllable" problem, as that was in one cover version, so
-  I claim it's not part of the official rules.
+My notes: the recurring bit is of course the core of this problem.
+How to do it?  Refreshing my memory with some examples of long
+division (sad), I realise that if we've seen the remainder before
+the recurring part is from where we saw that remainder before to
+the end of the digits produced.
diff --git a/challenge-106/duncan-c-white/perl/ch-1.pl b/challenge-106/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..49d5acdde3
--- /dev/null
+++ b/challenge-106/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,51 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Maximum Gap
+# 
+# You are given an array of integers @N.
+# 
+# Write a script to display the maximum difference between two successive
+# elements once the array is sorted.
+# If the array contains only 1 element then display 0.
+# 
+# Example
+# 
+# 	Input: @N = (2, 9, 3, 5)   [sorted: 2 3 5 9]
+# 	Output: 4
+# 
+# 	Input: @N = (1, 3, 8, 2, 0) [sorted: 0 1 2 3 8]
+# 	Output: 5
+# 
+# 	Input: @N = (5)
+# 	Output: 0
+# "
+# 
+# My notes: should be easy.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: maxgap [--debug] N1 N2...\n"
+	unless GetOptions( "debug" => \$debug ) && @ARGV>0;
+
+my @n = sort { $a <=> $b } @ARGV;
+
+say "0" if @n==1;
+
+if( @n > 1 )
+{
+	my $maxdiff = 0;
+	foreach my $i (0..$#n-1)
+	{
+		$a = $n[$i];
+		$b = $n[$i+1];
+		my $diff = $b-$a;
+		$maxdiff = $diff if $diff > $maxdiff;
+	}
+	say $maxdiff;
+}
diff --git a/challenge-106/duncan-c-white/perl/ch-2.pl b/challenge-106/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..4b0ecb28d1
--- /dev/null
+++ b/challenge-106/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,121 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Decimal String
+# 
+# You are given numerator and denominator i.e. $N and $D.
+# 
+# Write a script to convert the fraction into decimal string. If the
+# fractional part is recurring then put it in parenthesis.
+# 
+# Example
+# 
+# 	Input: $N = 1, $D = 3
+# 	Output: "0.(3)"
+# 
+# 	Input: $N = 1, $D = 2
+# 	Output: "0.5"
+# 
+# 	Input: $N = 5, $D = 66
+# 	Output: "0.0(75)"
+# "
+# 
+# My notes: the recurring bit is of course the core of this problem.
+# How to do it?  Refreshing my memory with some examples of long
+# division (sad), I realise that if we've seen the remainder before
+# the recurring part is from where we saw that remainder before to
+# the end of the digits produced.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Getopt::Long;
+#use Data::Dumper;
+
+my $debug = 0;
+die "Usage: decimal-string [--debug] N D\n"
+	unless GetOptions("debug"=>\$debug) && @ARGV==2;
+
+
+my( $n, $d ) = @ARGV;
+
+#
+# my $frac = fraction( $n, $d );
+#	Compute the fraction n/d, as a decimal string,
+#	but in the case of a recurring fraction, represent
+#	the recurring sequence as (seq).  examples given above.
+#
+fun fraction( $n, $d )
+{
+	die "fraction($n, $d): cannot divide by 0\n" if $d==0;
+
+	my $result = "";
+
+	# deal with any sign..
+	if( $d < 0 )
+	{
+		$n = -$n; $d = -$d;
+	}
+	if( $n < 0 )
+	{
+		$result = "-";
+		$n = -$n;
+	}
+	# now both are positive
+
+	# deal with the integer part.
+	my $intpart = int($n/$d);
+	$result .= $intpart;
+	$n -= $intpart * $d;
+	if( $n != 0 )
+	{
+		$result .= ".";
+
+		# now deal with the fractional part
+		$result .= recurring( $n, $d );
+	}
+	return $result;
+}
+
+
+#
+# my $result = recurring( $n, $d );
+#	Given $n and $d, where both are +ve, $d is not zero,
+#	and $n < $d, representing a fraction n/d in the range
+#	0 to 0.9999.., generate a string showing that fraction
+#	with any recurring sequence shown as (seq).
+#
+fun recurring( $n, $d )
+{
+	my @seen;	# maps any value of n we've seen -> it's position
+	my $digits="";
+	my $rem = $n;
+
+	$seen[$rem] = 0;
+	$rem *= 10;
+	for( my $pos=0; $rem!=0 && ! defined $seen[$rem]; $pos++ )
+	{
+		my $intpart = int($rem / $d);
+		$digits .= $intpart;
+		say "rem:$rem intpart:$intpart digits:$digits" if $debug;
+		$seen[$rem] = $pos;
+		$seen[$rem] = length($digits)-1;
+		$rem -= $intpart*$d;
+		$rem *= 10;
+	}
+	return $digits if $rem==0;		# not repeating
+
+	my $repstart = $seen[$rem];
+	say "rem:$rem repstart:$repstart" if $debug;
+
+	# the digits from pos $repstart to end are repeating
+
+	my $nonrep = substr($digits,0,$repstart);
+	my $rep = substr($digits,$repstart);
+	return "$nonrep($rep)";
+}
+
+
+my $frac = fraction( $n, $d );
+say $frac;