Merge pull request #1370 from dcw803/master

incorporated my solutions for this week's challenges

3 files changed, 183 insertions, 40 deletions

diff --git a/challenge-050/duncan-c-white/README b/challenge-050/duncan-c-white/README
index 6895a656b2..3d714d2e48 100644
--- a/challenge-050/duncan-c-white/README
+++ b/challenge-050/duncan-c-white/README
@@ -1,57 +1,52 @@
-Task 1: "Smallest Multiple:
+Task 1: "Merge Intervals
 
-Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.
-
-For example:
-For given number 55, the smallest multiple is 110 consisting of digits 0 and 1.
-"
-
-My notes: cute.
+Write a script to merge the given intervals whereever possible.
 
+    [2,7], [3,9], [10,12], [15,19], [18,22]
 
-Task #2: "LRU Cache
+The script should merge [2, 7] and [3, 9] together to return [2, 9].
 
-Write a script to demonstrate LRU Cache feature. It should support
-operations get and set. Accept the capacity of the LRU Cache as command
-line argument.
+Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22].
 
-Definition of LRU: An access to an item is defined as a get or a set
-operation of the item. "Least recently used" item is the one with the
-oldest access time.
+The final result should be something like below:
 
-For example:
-
-capacity = 3
-set(1, 3)
-set(2, 5)
-set(3, 7)
-
-Cache at this point:
-[Least recently used] 1,2,3 [most recently used]
+[2, 9], [10, 12], [15, 22]
+"
 
-get(2)      # returns 5
+My notes: Fine, but why wouldn't we also merge [2,9] and [10,12] to give
+[2,12]?  I think we would.  The immediate thought to implement this is
+to collapse all ranges to an integer set, and then reconstruct the minimal
+sequence of ranges direct from the set.
 
-Cache looks like now:
-[Least recently used] 1,3,2 [most recently used]
 
-get(1)      # returns 3
+Task #2: "Noble Integer
 
-Cache looks like now:
-[Least recently used] 3,2,1 [most recently used]
+You are given a list, @L, of three or more random integers between 1 and
+50. A Noble Integer is an integer N in @L, such that there are exactly
+N integers greater than N in @L. Output any Noble Integer found in @L,
+or an empty list if none were found.
 
-get(4)      # returns -1
+An interesting question is whether or not there can be multiple Noble
+Integers in a list.
 
-Cache unchanged:
-[Least recently used] 3,2,1 [most recently used]
+For example,
 
-set(4, 9)
+Suppose we have list of 4 integers [2, 6, 1, 3].
 
-Cache is full, so pushes out key = 3:
-[Least recently used] 2,1,4 [most recently used]
+Here we have 2 in the above list, known as Noble Integer, since there
+are exactly 2 integers in the list greater than 2: 3 and 6.
 
-get(3)      # returns -1
+Therefore the script would print 2.
 "
 
-My notes: ok, so an array of keys in most-recently-used
-order, and a hash to store the (no more than $capacity)
-key, value pairs.
+My notes: Interesting, especially the question about "whether or not there
+can be multiple Noble Integers in a list": If repeated numbers are allowed,
+you can definitely have multiple (identical) noble numbers eg 2 1 1 1 1...
+(each 1 is noble because there's exactly one number >1 (the 2)).  So disallow that.
+Now, given distinct numbers, I don't think multiple noble numbers are possible
+in one list. "find a list with 2 numbers greater than 2 and 3 numbers greater
+than 3" is not possible, because every number greater than 3 is ALSO greater
+than 2, so there are at least as many numbers greater than 2 as there are
+numbers greater than 3, i.e. at least 3 numbers in the list are greater than 2,
+which contradicts the specification that only (exactly) 2 numbers in the list are
+greater than 2.
diff --git a/challenge-050/duncan-c-white/perl/ch-1.pl b/challenge-050/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..2d78c526f0
--- /dev/null
+++ b/challenge-050/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,70 @@
+#!/usr/bin/perl
+#
+# Task 1: "Merge Intervals
+#
+# Write a script to merge the given intervals whereever possible.
+# 
+#     [2,7], [3,9], [10,12], [15,19], [18,22]
+# 
+# The script should merge [2, 7] and [3, 9] together to return [2, 9].
+# 
+# Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22].
+# 
+# The final result should be something like below:
+# 
+# [2, 9], [10, 12], [15, 22]
+# "
+# 
+# My notes: Fine, but why wouldn't we also merge [2,9] and [10,12] to give
+# [2,12]?  I think we would.  The immediate thought to implement this is
+# to collapse all ranges to an integer set, and then reconstruct the minimal
+# sequence of ranges direct from the set.
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+#use Function::Parameters;
+#use Data::Dumper;
+
+die "Usage: int-sequences A B [C D [E F]]...\n" if @ARGV % 2 == 1;
+
+# build %on: a set of all integers marked "on" by the ranges
+
+my %on;
+my $min = 1000000;
+my $max = -1;
+
+while( @ARGV >= 2 )
+{
+	( my $a, my $b, @ARGV ) = @ARGV;
+	die "int-sequences: a=$a, b=$b, a>b\n" if $a>$b;
+	foreach my $i ($a..$b)
+	{
+		$on{$i}++;
+		$min = $i if $i<$min;
+		$max = $i if $i>$max;
+	}
+}
+
+#say "min=$min, max=$max";
+
+
+# now, produce the sequence of ranges from %on, using min and max
+
+my $start = my $end = $min;
+for(;;)
+{
+	while( $on{$end+1} )
+	{
+		$end++;
+	}
+	say "[$start - $end]";
+	$start = $end+1;
+	while( $start<=$max && ! $on{$start} )
+	{
+		$start++;
+	}
+last if $start>$max;
+	$end = $start;
+}
diff --git a/challenge-050/duncan-c-white/perl/ch-2.pl b/challenge-050/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..1914674d53
--- /dev/null
+++ b/challenge-050/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,78 @@
+#!/usr/bin/perl
+#
+# Task #2: "Noble Integer
+#
+# You are given a list, @L, of three or more random integers between 1 and
+# 50. A Noble Integer is an integer N in @L, such that there are exactly
+# N integers greater than N in @L. Output any Noble Integer found in @L,
+# or an empty list if none were found.
+# 
+# An interesting question is whether or not there can be multiple Noble
+# Integers in a list.
+# 
+# For example,
+# 
+# Suppose we have list of 4 integers [2, 6, 1, 3].
+# 
+# Here we have 2 in the above list, known as Noble Integer, since there
+# are exactly 2 integers in the list greater than 2: 3 and 6.
+# 
+# Therefore the script would print 2.
+# "
+# 
+# My notes: Interesting, especially the question about "whether or not there
+# can be multiple Noble Integers in a list": If repeated numbers are allowed,
+# you can definitely have multiple (identical) noble numbers eg 2 1 1 1 1...
+# (each 1 is noble because there's exactly one number >1 (the 2)).
+# So disallow that.
+# Now, given distinct numbers, I don't think multiple noble numbers are possible
+# in one list. "find a list with 2 numbers greater than 2 and 3 numbers greater
+# than 3" is not possible, because every number greater than 3 is ALSO greater
+# than 2, so there are at least as many numbers greater than 2 as there are
+# numbers greater than 3, i.e. at least 3 numbers in the list are greater than 2,
+# which contradicts the specification that only (exactly) 2 numbers in the list are
+# greater than 2.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+#use Data::Dumper;
+
+die "Usage: noble list_of_3_or_more_ints\n" unless @ARGV>2;
+
+foreach my $i (@ARGV)
+{
+	die "noble: element $i out of range 1..50\n" unless
+		$i >= 1 && $i <= 50;
+}
+
+# remove duplicate items by turning list into set..
+my %set = map { $_ => 1 } @ARGV;
+
+# and finding the (distinct) keys of that set..
+my @l = keys %set;
+
+my @noble = find_all_noble( @l );
+say "noble: $_" for @noble;
+
+
+#
+# my @noble = find_all_noble( @l );
+#	Find and return a list of all noble elements in @l,
+#	or the empty list if none are noble.  The definition
+#	of noble is from above:
+#	"A Noble Integer is an integer N in @L,
+#	such that there are exactly N integers greater than N in @L"
+#
+fun find_all_noble( @l )
+{
+	my @noble;
+	foreach my $element (@l)
+	{
+		my $ngt = grep { $_ > $element } @l;
+		push @noble, $element if $element == $ngt;
+	}
+	return @noble;
+}