Merge pull request #4043 from dcw803/master

imported this week's solutions

3 files changed, 144 insertions, 38 deletions

diff --git a/challenge-111/duncan-c-white/README b/challenge-111/duncan-c-white/README
index c8cf5c8876..65a6d1e549 100644
--- a/challenge-111/duncan-c-white/README
+++ b/challenge-111/duncan-c-white/README
@@ -1,52 +1,39 @@
-Task 1: "Valid Phone Numbers
+Task 1: "Search Matrix
 
-You are given a text file.
+You are given 5x5 matrix filled with integers such that each row is
+sorted from left to right and the first integer of each row is greater
+than the last integer of the previous row.
 
-Write a script to display all valid phone numbers in the given text file.
-Acceptable Phone Number Formats
+Write a script to find a given integer in the matrix using an efficient search algorithm.
 
-+nn  nnnnnnnnnn
-(nn) nnnnnnnnnn
-nnnn nnnnnnnnnn
+Example
 
-Input File
+    Matrix: [  1,  2,  3,  5,  7 ]
+            [  9, 11, 15, 19, 20 ]
+            [ 23, 24, 25, 29, 31 ]
+            [ 32, 33, 39, 40, 42 ]
+            [ 45, 47, 48, 49, 50 ]
 
-0044 1148820341
- +44 1148820341
-  44-11-4882-0341
-(44) 1148820341
-  00 1148820341
+    Input: 35
+    Output: 0 since it is missing in the matrix
 
-Output
-
-0044 1148820341
- +44 1148820341
-(44) 1148820341
+    Input: 39
+    Output: 1 as it exists in the matrix
 "
 
-My notes: as the valid formats are fixed, just a load of regexes.
-Would have been more interesting if the formats were inputs too.
-
-
-Task 2: "Transpose File
-
-You are given a text file.
+My notes: could flatten onto a 1D array and binary search.  Other
+methods?  Find which row it's in (if any) and then grep?  Did that.
+Not a very nice method (not even sure it works:-))
 
-Write a script to transpose the contents of the given file.
-Input File
 
-name,age,sex
-Mohammad,45,m
-Joe,20,m
-Julie,35,f
-Cristina,10,f
+Task 2: "Ordered Letters
 
-Output:
+Given a word, you can sort its letters alphabetically (case
+insensitive). For example, "beekeeper" becomes "beeeeekpr" and
+"dictionary" becomes "acdiinorty".
 
-name,Mohammad,Joe,Julie,Cristina
-age,45,20,35,10
-sex,m,m,f,f
+Write a script to find the longest English words that don't change when
+their letters are sorted.
 "
 
-My notes: simple to state.  Basically read into 2-D array and transpose
-array.
+My notes: nice!
diff --git a/challenge-111/duncan-c-white/perl/ch-1.pl b/challenge-111/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..4dce529b92
--- /dev/null
+++ b/challenge-111/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,73 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Search Matrix
+#
+# You are given 5x5 matrix filled with integers such that each row is
+# sorted from left to right and the first integer of each row is greater
+# than the last integer of the previous row.
+# 
+# Write a script to find a given integer in the matrix using an efficient search algorithm.
+# 
+# Example
+# 
+#     Matrix: [  1,  2,  3,  5,  7 ]
+#             [  9, 11, 15, 19, 20 ]
+#             [ 23, 24, 25, 29, 31 ]
+#             [ 32, 33, 39, 40, 42 ]
+#             [ 45, 47, 48, 49, 50 ]
+# 
+#     Input: 35
+#     Output: 0 since it is missing in the matrix
+# 
+#     Input: 39
+#     Output: 1 as it exists in the matrix
+# "
+# 
+# My notes: could flatten onto a 1D array and binary search.  Other
+# methods?  Find which row it's in (if any) and then grep?  Did that.
+# Not a very nice method (not even sure it works:-))
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+#use Data::Dumper;
+
+my @m = (
+	[ 1,  2,  3,  5,  7 ],
+	[  9, 11, 15, 19, 20 ],
+	[ 23, 24, 25, 29, 31 ],
+	[ 32, 33, 39, 40, 42 ],
+	[ 45, 47, 48, 49, 50 ],
+);
+
+#
+# my $found = search( $n, @m );
+#	Ok, search for $n in 2-D array @m.
+#	Return 1 if found, 0 otherwise.
+#
+fun search( $n, @m )
+{
+	return 0 if $n < $m[0][0];
+	return 0 if $n > $m[4][4];
+
+	# find row
+	my $rowno;
+	for( $rowno = 0; $rowno<5; $rowno++ )
+	{
+		last if $m[$rowno][0] <= $n && $m[$rowno][4] >= $n;
+	}
+
+	# in row rowno, just grep
+	my $found = grep { $_ == $n } @{$m[$rowno]};
+	return $found ? 1 : 0;
+}
+
+
+
+die "Usage: matrix-search N\n" unless @ARGV==1;
+my $n = shift;
+
+my $found = search( $n, @m );
+say ($found ? $n : 0);
diff --git a/challenge-111/duncan-c-white/perl/ch-2.pl b/challenge-111/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..8c1f7c6f50
--- /dev/null
+++ b/challenge-111/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,46 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Ordered Letters
+#
+# Given a word, you can sort its letters alphabetically (case
+# insensitive). For example, "beekeeper" becomes "beeeeekpr" and
+# "dictionary" becomes "acdiinorty".
+# 
+# Write a script to find the longest English words that don't change when
+# their letters are sorted.
+# "
+# 
+# My notes: nice!
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Text::CSV;
+#use Data::Dumper;
+
+
+my $wordfile = "/usr/share/dict/words";
+die "Usage: longest-sort-letters [wordfile]\n" if @ARGV>1;
+$wordfile = shift if @ARGV==1;
+
+my $longest = "NO SUCH WORD";
+my $longlen = -1;
+
+open( my $infh, '<', $wordfile ) || die "can't open $wordfile\n";
+while( <$infh> )
+{
+	chomp;
+	my $sig = join( '', sort split(//,$_) );
+	next unless $sig eq $_;
+	my $l = length($sig);
+	if( $l > $longlen )
+	{
+		$longlen = $l;
+		$longest = $_;
+	}
+}
+close( $infh );
+
+print "longest word same as it's signature: $longest\n";