imported my solutions to this week's challenge..

3 files changed, 212 insertions, 38 deletions

diff --git a/challenge-092/duncan-c-white/README b/challenge-092/duncan-c-white/README
index c8483d64bb..e657d3335c 100644
--- a/challenge-092/duncan-c-white/README
+++ b/challenge-092/duncan-c-white/README
@@ -1,60 +1,46 @@
-Task 1: "Count Number
+Task 1: "Isomorphic Strings
 
-You are given a positive number $N.  Write a script to count number and display as you read it.
+You are given two strings $A and $B.
 
-Example 1:
+Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.
+(Isomorphic means: same length, and with a 1-1 mapping between distinct chars in $A and those in $B).
 
-Input: $N = 1122234
-Output: 21321314
+Example 1:
 
-as we read "two 1 three 2 one 3 one 4"
+	Input: $A = "abc"; $B = "xyz"
+	Output: 1
 
 Example 2:
 
-Input: $N = 2333445
-Output: 12332415
-
-as we read "one 2 three 3 two 4 one 5"
+	Input: $A = "abb"; $B = "xyy"
+	Output: 1
 
 Example 3:
 
-Input: $N = 12345
-Output: 1112131415
-
-as we read "one 1 one 2 one 3 one 4 one 5"
+	Input: $A = "sum"; $B = "add"
+	Output: 0
 "
 
-My notes: not brilliantly clearly defined, but simple to do with a freq hash.
+My notes: nice!
 
 
-Task 2: "Jump Game
+Task 2: "Insert Interval
 
-You are given an array of positive numbers @N, where value at each index
-determines how far you are allowed to jump further.  Write a script to
-decide if you can jump to the last index. Print 1 if you are able to
-reach the last index otherwise 0.
+You are given a set of sorted non-overlapping intervals and a new interval.
 
-Example 1:
-
-	Input: @N = (1, 2, 1, 2)
-	Output: 1
+Write a script to merge the new interval to the given set of intervals.
 
-as we jump one place from index 0 and then twoe places from index 1 to
-reach the last index.
+Example 1:
+	Input $S = (1,4), (8,10); $N = (2,6)
+	Output: (1,6), (8,10)
 
 Example 2:
+	Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+	Output: (1,2), (3,10)
 
-	Input: @N = (2,1,1,0,2)
-	Output: 0
-
-it is impossible to reach the last index. as we jump two places from index
-0 to reach index 2, followed by one place jump from index 2 to reach the
-index 3. once you reached the index 3, you can't go any further because
-you can only jump 0 position further.
+Example 3:
+	Input $S = (1,5), (7,9); $N = (10,11)
+	Output: (1,5), (7,9), (10,11)
 "
 
-My notes: does it mean "decide if you can jump to the last index, starting at index 0"?
-all the examples show that, so I'm going to assume that's what it means.  But it
-doesn't say that explicitly - reading at first I thought you would have a
-free choice of where to start, so would have to search "starting at pos 0",
-"starting at pos 1"... etc.  Negative numbers would also make it more interesting.
+My notes: interesting. Sounds familiar.
diff --git a/challenge-092/duncan-c-white/perl/ch-1.pl b/challenge-092/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..427853a6fa
--- /dev/null
+++ b/challenge-092/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,73 @@
+#!/usr/bin/perl
+#
+# Task 1: "Isomorphic Strings
+# 
+# You are given two strings $A and $B.
+# 
+# Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.
+# (Isomorphic means: same length, and with a 1-1 mapping between distinct chars in $A and those in $B).
+# 
+# Example 1:
+# 
+# 	Input: $A = "abc"; $B = "xyz"
+# 	Output: 1
+# 
+# Example 2:
+# 
+# 	Input: $A = "abb"; $B = "xyy"
+# 	Output: 1
+# 
+# Example 3:
+# 
+# 	Input: $A = "sum"; $B = "add"
+# 	Output: 0
+# "
+# 
+# My notes: nice!
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug = 0;
+die "Usage: isomorphic-strings [--debug] A B\n" unless
+	GetOptions( "debug" => \$debug ) &&
+	@ARGV==2;
+my( $a, $b ) = @ARGV;
+
+#
+# my $isiso = isomorphic( $a, $b );
+#	Determine whether strings $a and $b are isomorphic;
+#	return 1 iff they are, 0 otherwise.
+#
+fun isomorphic( $a, $b )
+{
+	my $l = length($a);
+	return 0 unless $l == length($b);
+
+	my %atob;	# mapping of char from $a to equivalent char in $b
+	my %btoa;	# mapping of char from $b to equivalent char in $a
+	foreach my $pos (0..$l-1)
+	{
+		my $ach = substr($a,$pos,1);
+		my $bch = substr($b,$pos,1);
+		if( defined $atob{$ach} )
+		{
+			return 0 unless $atob{$ach} eq $bch;
+		} else
+		{
+			return 0 if defined $btoa{$bch};
+			$atob{$ach} = $bch;
+			$btoa{$bch} = $ach;
+		}
+	}
+	return 1;
+}
+
+
+my $isiso = isomorphic( $a, $b );
+say $isiso;
diff --git a/challenge-092/duncan-c-white/perl/ch-2.pl b/challenge-092/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..4343aa8db1
--- /dev/null
+++ b/challenge-092/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,115 @@
+#!/usr/bin/perl
+#
+# Task 2: "Insert Interval
+# 
+# You are given a set of sorted non-overlapping intervals and a new interval.
+# 
+# Write a script to merge the new interval to the given set of intervals.
+# 
+# Example 1:
+# 	Input $S = (1,4), (8,10); $N = (2,6)
+# 	Output: (1,6), (8,10)
+# 
+# Example 2:
+# 	Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+# 	Output: (1,2), (3,10)
+# 
+# Example 3:
+# 	Input $S = (1,5), (7,9); $N = (10,11)
+# 	Output: (1,5), (7,9), (10,11)
+# "
+# 
+# My notes: interesting. Sounds familiar.  let's use from:to as interval syntax.
+# 
+
+use strict;
+use warnings;
+use Data::Dumper;
+use Function::Parameters;
+use feature 'say';
+use Getopt::Long;
+
+my $debug = 0;
+die "Usage: insert-interval [--debug] newinterval interval1 .. intervalN\n" unless
+	GetOptions( "debug" => \$debug ) &&
+	@ARGV>2;
+my( $newint, @int ) = map { validate_interval($_) } @ARGV;
+
+my @result = merge_interval( $newint, @int );
+say "$_->[0]:$_->[1]" for @result;
+
+
+#
+# my $validint = validate_interval( $int );
+#	Check that $int is a valid interval of the form FROM:TO,
+#	with FROM and TO being numbers, and with FROM<=TO.
+#	die with error message if it isn't.  Return a validinterval [$from,$to] if it is.
+#
+fun validate_interval( $int )
+{
+	die "Usage: insert-interval: bad interval $int, should be of form INT:INT\n"
+		unless $int=~ /^(\d+):(\d+)$/;
+	my( $from, $to ) = ($1,$2);
+	die "Usage: insert-interval: bad interval $int, from $from must be <= to $to\n"
+		unless $from<=$to;
+	return [ $from, $to ];
+}
+
+
+#
+# my @result = merge_interval( $newint, @int );
+#	Ok, given $newint (a [from,to] arrayref) and @int, a sorted
+#	array of nonoverlapping [from,to] arrayrefs, let's merge $newint
+#	and @int, returning @result, the merged sorted array of
+#	nonoverlapping [from,to] arrayrefs.
+#
+fun merge_interval( $newint, @int )
+{
+	my( $newfrom, $newto ) = @$newint;
+
+	return ($newint) if @int==0;	# empty list of intervals..
+
+	# I'm sure there's a clever way of doing this, I can nearly see my way to it, identifying
+	# overlapping intervals (and merging adjacent intervals), but as it's after 11pm on
+	# Sunday 27th Dec, let's do it the grunt way, which works as long as the intervals involve
+	# positive numbers only (which is what \d+ matches anyway):
+
+	# First: expand all the intervals (new and old) into a number line - an array of booleans
+	my @x;				# all default to false
+	foreach my $i ($newfrom..$newto)
+	{
+		$x[$i] = 1;		# set it to true
+	}
+	foreach my $int (@int)
+	{
+		foreach my $i ($int->[0]..$int->[1])
+		{
+			$x[$i] = 1;		# set it to true
+		}
+	}
+	#die Dumper \@x;
+
+	# Second: find all the intervals in @x
+	my @result;
+	my $from = 0;
+	for(;;)
+	{
+		while( $from <= $#x && ! $x[$from] )
+		{
+			$from++;
+		}
+	last if $from > $#x;
+		my $to = $from;
+		while( $x[$to] )
+		{
+			$to++;
+		}
+		say "debug: from=$from, to=".($to-1) if $debug;
+		push @result, [$from,$to-1];
+		$from = $to;
+	}
+
+	return @result;
+}
+
+