imported my solutions to this week's tasks.. 2 straightforward tasks

5 files changed, 270 insertions, 85 deletions

diff --git a/challenge-098/duncan-c-white/README b/challenge-098/duncan-c-white/README
index b6b3cf4d76..076c190712 100644
--- a/challenge-098/duncan-c-white/README
+++ b/challenge-098/duncan-c-white/README
@@ -1,103 +1,55 @@
-Task 1: "Caesar Cipher
+Task 1: "Read N-characters
 
-You are given string $S containing alphabets A..Z only and a number $N.
+You are given file $FILE.
 
-Write a script to encrypt the given string $S using Caesar Cipher with
-left shift of size $N.
+Create subroutine readN($FILE, $number) returns the first n-characters
+and moves the pointer to the (n+1)th character.
 
-Example
-
-	Input: $S = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG", $N = 3
-	Output: "QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD"
-
-	Plain:    ABCDEFGHIJKLMNOPQRSTUVWXYZ
-	Cipher:   XYZABCDEFGHIJKLMNOPQRSTUVW
-
-	Plaintext:  THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
-	Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
+Example:
 
+Input: Suppose the file (input.txt) contains "1234567890"
+Output:
+    print readN("input.txt", 4); # returns "1234"
+    print readN("input.txt", 4); # returns "5678"
+    print readN("input.txt", 4); # returns "90"
 "
 
-My notes: ah, the good old Caesar cipher, aka rotN..  easy.
-
+My notes: weird question, hiding IO handles, so presumably a hash of filenames
+to IO handles is needed?
 
-Task 2: "Binary Substrings
 
-You are given a binary string $B and an integer $S.
+Task 2: "Search Insert Position
 
-Write a script to split the binary string $B of size $S and then find
-the minimum number of flips required to make it all the same.
+You are given a sorted array of distinct integers @N and a target $N.
+Write a script to return the index of the given target if found otherwise
+place the target in the sorted array and return the index.
 
 Example 1:
 
-	Input: $B = "101100101" $S = 3
-	Output: 1
-
-	Binary Substrings:
-	    "101": 0 flip
-	    "100": 1 flip to make it "101"
-	    "101": 0 flip
+	Input: @N = (1, 2, 3, 4) and $N = 3
+	Output: 2 since the target 3 is in the array at the index 2.
 
 Example 2:
 
-	Input $B = "10110111" $S = 4
-	Output: 2
+	Input: @N = (1, 3, 5, 7) and $N = 6
+	Output: 3 since the target 6 is missing and
+	   should be placed at the index 3.
+
+Example 3:
+
+	Input: @N = (12, 14, 16, 18) and $N = 10
+	Output: 0 since the target 10 is missing and
+	   should be placed at the index 0.
+
+Example 4:
 
-	Binary Substrings:
-	    "1011": 0 flip
-	    "0111": 2 flips to make it "1011"
+	Input: @N = (11, 13, 15, 17) and $N = 19
+	Output: 4 since the target 19 is missing and
+	   should be placed at the index 4.
 "
 
-My notes:  hmm.. this could be specified a LOT more clearly.  bad phrasing!
-and the examples don't completely clarify what we're supposed to do.
-The first task is obvious: split BS into "length S" chunks - that's trivial..
-
-But then what we do with the chunks is not quite clear - both examples seem
-to show taking the first chunk as the "goal to reach" and then all we
-do is to find out the maximum number of bits that have to be flipped to turn
-any of the OTHER chunks into the goal-chunk.  But what's special about the
-first chunk?  Also, if we do that, where does the word "minimum" come in?
-
-I wonder whether it means, instead:
-- try each distinct chunk as the goal chunk, for each such goal, find the
-  maximum number of bits that have to be flipped to turn chunkN into the
-  goalchunk, AND THEN FIND THE MINIMUM OF ALL THOSE MAXIMUMS.
-
-I'm going to assume that it's the latter..  Update: having coded it, yes,
-this can produce different answers than "first chunk is the goal".
-The following example demonstrates the difference:
-
-Example dcw-1:
-	Input: $B = "000101011111" $S = 3
-	Output: 2
-
-	Binary Substrings:
-	000
-	101
-	011
-	111
-
- If 000 is the goal, then we'd work out how many bits have to be
- flipped in each of the other substrings to reach 000, getting:
-	Binary Substrings:
-	000: 0 flips to teach 000
-	101: 2 flips to teach 000
-	011: 2 flips to teach 000
-	111: 3 flips to teach 000
- max those is 3.
-
- But if 101 is the goal, we'd have:
-	Binary Substrings:
-	000: 2 flips to teach 101
-	101: 0 flips to teach 101
-	011: 2 flips to teach 101
-	111: 1 flip to teach 101
- let's abbreviate that as: goal: 101: flips=2,0,2,1
- max those is 2.
-
- If 011 is the goal, we get flips=2,2,0,1, max 2.
-
- Finally, if 111 is the goal, we get flips=3,1,1,0, max 3
-
- So the MINIMUM of all those maximums is: min(3,2,2,3) = 2.
- That's the answer!
+My notes: nice question.  Clearly defined for once:-)
+Note that inserting the element in the list only matters if
+we print the list out, so let's do that.
+Also added decent amount of input checking (is the list sorted etc)
+Also added test suite [invoke with --test]
diff --git a/challenge-098/duncan-c-white/perl/ch-1.pl b/challenge-098/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..bf76fbae1b
--- /dev/null
+++ b/challenge-098/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/perl
+#
+# Task 1: "Read N-characters
+# 
+# You are given file $FILE.
+# 
+# Create subroutine readN($FILE, $number) returns the first n-characters
+# and moves the pointer to the (n+1)th character.
+# 
+# Example:
+# 
+# Input: Suppose the file (input.txt) contains "1234567890"
+# Output:
+#     print readN("input.txt", 4); # returns "1234"
+#     print readN("input.txt", 4); # returns "5678"
+#     print readN("input.txt", 4); # returns "90"
+# "
+# 
+# My notes: weird question, hiding IO handles, so presumably a hash of filenames
+# to IO handles is needed?
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Data::Dumper;
+
+die "Usage: readN filename1:N1 [filename2:N2...]\n" unless @ARGV>=1;
+foreach my $fn (@ARGV)
+{
+	die "readN: argument should be of the form filename:N\n"
+		unless $fn =~ /^([^:]+):(\d+)$/;
+	my( $f, $n ) = ( $1, $2 );
+	say "readN($f,$n) = ".readN( $f, $n );
+}
+
+
+#
+# my $str = readN( $filename, $nchars );
+#	Read the next $nchars from $filename.
+#
+my %filename2fh;
+sub readN
+{
+	my( $filename, $nchars ) = @_;
+	my $fh = $filename2fh{$filename};
+	unless( defined $fh )
+	{
+		open( $fh, '<', $filename ) ||
+			die "readN: can't open $filename\n";
+		$filename2fh{$filename} = $fh;
+	}
+	my $s = "";
+	my $nread = sysread( $fh, $s, $nchars );
+
+	# if hit eof, close filehandle for neatness
+	# (this would case future calls to readN from this
+	# same filename will simply reread the file from the
+	# beginning.  But if we don't do this, we never
+	# close any filehandles.
+	if( $nchars > 0 && $nread == 0 )
+	{
+		close $fh;
+		delete $filename2fh{$filename};
+	}
+	return $s;
+}
diff --git a/challenge-098/duncan-c-white/perl/ch-2.pl b/challenge-098/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..c9a08a0cfb
--- /dev/null
+++ b/challenge-098/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,164 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Search Insert Position
+# 
+# You are given a sorted array of distinct integers @N and a target $N.
+# Write a script to return the index of the given target if found otherwise
+# place the target in the sorted array and return the index.
+# 
+# Example 1:
+# 
+# 	Input: @N = (1, 2, 3, 4) and $N = 3
+# 	Output: 2 since the target 3 is in the array at the index 2.
+# 
+# Example 2:
+# 
+# 	Input: @N = (1, 3, 5, 7) and $N = 6
+# 	Output: 3 since the target 6 is missing and
+# 	   should be placed at the index 3.
+# 
+# Example 3:
+# 
+# 	Input: @N = (12, 14, 16, 18) and $N = 10
+# 	Output: 0 since the target 10 is missing and
+# 	   should be placed at the index 0.
+# 
+# Example 4:
+# 
+# 	Input: @N = (11, 13, 15, 17) and $N = 19
+# 	Output: 4 since the target 19 is missing and
+# 	   should be placed at the index 4.
+# "
+# 
+# My notes: nice question.  Clearly defined for once:-)
+# Note that inserting the element in the list only matters if
+# we print the list out, so let's do that.
+# Also added decent amount of input checking (is the list sorted etc)
+# Also added test suite [invoke with --test]
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug=0;
+my $test=0;
+die "Usage: search-insert-position [--test] [--debug]\n".
+    "Or...  search-insert-position [--debug] N sorted-numeric-list\n"
+	unless GetOptions( "debug" => \$debug, "test" => \$test )
+	    && ($test && @ARGV==0 || !$test && @ARGV>=2);
+
+if( $test )
+{
+	dotests();
+	exit 0;
+}
+
+my( $n, @values ) = @ARGV;
+# allow list to be separate args (eg 1 2 3 4) or csv (eg 1,2,3,4)
+my $instr = join(',', @values);
+@values = split(/,/,$instr);
+
+die "search-insert-position: list must be sorted\n" unless
+	isnumericallysorted(@values);
+my $pos = findorinsert( $n, \@values );
+say "insertion pos: $pos";
+say "values after: ", join(',',@values);
+
+
+#
+# my $issorted = isnumericallysorted( @x );
+#	Return true iff the element in @x are numerically sorted;
+#	false otherwise.
+#
+fun isnumericallysorted( @x )
+{
+	my $prev = shift @x;
+	foreach my $next (@x)
+	{
+		return 0 if $next < $prev;
+		$prev = $next;
+	}
+	return 1;
+}
+
+#
+# my $pos = findorinsert( $target, $values );
+#	Implement the core problem of this task:
+#	Return the index of the given $target in sorted array @$values if
+#	found otherwise place the target in the sorted array and return
+#	the index.
+#
+fun findorinsert( $target, $values )
+{
+	foreach my $pos (0..$#$values)
+	{
+		my $v = $values->[$pos];
+		if( $v == $target )
+		{
+			say "debug: found $target at pos $pos" if $debug;
+			return $pos;
+		}
+		if( $v > $target )
+		{
+			say "debug: inserting $target at pos $pos" if $debug;
+			splice( @$values, $pos, 0, $target );
+			return $pos;
+		}
+	}
+	say "debug: appending $target at end" if $debug;
+	push( @$values, $target );
+	return $#$values;
+}
+
+
+#
+# dotests();
+#	Do a load of tests.
+#
+fun dotests()
+{
+	eval "use Test::More"; die $@ if $@;
+
+# format of each list: inputlist (eg 1,2,3,4):target:pos[:modifiedlist]
+my @tests = (
+	"1,2,3,4:3:2",
+	"1,2,3,4:4:3",
+	"1,2,3,4:2:1",
+	"1,2,3,4:7:4:1,2,3,4,7",
+	"10,20,30,40:7:0:7,10,20,30,40",
+	"10,20,30,40:17:1:10,17,20,30,40",
+	"1,2,3,4:5:4:1,2,3,4,5",
+);
+
+	say "dotests() entry" if $debug;
+	say "dotests(): tests=". Dumper(\@tests) if $debug;
+	foreach my $test (@tests)
+	{
+		say "test $test" if $debug;
+		my( $input, $target, $exppos, $output ) = split( /:/, $test );
+		$output //= '';
+		die "dotests: bad input $input\n" unless
+			$input =~ /^(\d+,)*\d+$/;
+		die "dotests: bad target $target\n" unless
+			$target > 0;
+		die "dotests: bad pos $exppos\n" unless $exppos >= 0;
+		die "dotests: bad output $output\n" unless
+			$output eq '' || $output =~ /^(\d+,)*\d+$/;
+		my @i = split(/,/, $input);
+		$output = $input if $output eq '';
+
+		my $pos = findorinsert( $target, \@i );
+		say "insertion pos: $pos" if $debug;
+		say "values after: ", join(',',@i) if $debug;
+		my $fin = "findinsert($target,". join(',',@i).") ";
+		is( $pos, $exppos, " $fin: position $exppos" );
+		is( join(',',@i), $output, " $fin: output $output" );
+
+	}
+	done_testing();
+	say "dotests() exit" if $debug;
+}
diff --git a/challenge-098/duncan-c-white/perl/input.txt b/challenge-098/duncan-c-white/perl/input.txt
new file mode 100644
index 0000000000..a32a4347a4
--- /dev/null
+++ b/challenge-098/duncan-c-white/perl/input.txt
@@ -0,0 +1 @@
+1234567890
diff --git a/challenge-098/duncan-c-white/perl/input2.txt b/challenge-098/duncan-c-white/perl/input2.txt
new file mode 100644
index 0000000000..ce01362503
--- /dev/null
+++ b/challenge-098/duncan-c-white/perl/input2.txt
@@ -0,0 +1 @@
+hello