Merge pull request #2275 from dcw803/master

imported my solutions for this week's questions

7 files changed, 468 insertions, 61 deletions

diff --git a/challenge-077/duncan-c-white/README b/challenge-077/duncan-c-white/README
index 4a35d35c82..f173adcc40 100644
--- a/challenge-077/duncan-c-white/README
+++ b/challenge-077/duncan-c-white/README
@@ -1,69 +1,67 @@
-Task 1: "Prime Sum
+Task 1: "Fibonacci Sum
 
-You are given a number $N. Write a script to find the minimum number of
-prime numbers required, whose summation gives you $N.
-For the sake of this task, 1 is not a prime number.
+You are given a positive integer $N.
 
-Example:
+Write a script to find out all possible combination of Fibonacci Numbers
+required to get $N on addition.
 
-Input:
-    $N = 9
+You are NOT allowed to repeat a number. Print 0 if none found.
 
-Ouput:
-    2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
-    2 + 7 = 9.
+Example 1:
+
+Input: $N = 6
+
+Output:
+    1 + 2 + 3 = 6
+    1 + 5 = 6
+
+Example 2:
+
+Input: $N = 9
+
+Output:
+    1 + 8 = 9
+    1 + 3 + 5 = 9
 "
 
-My notes: ok. pretty straightforward.
-
-Task 2: "Word Search
-
-Write a script that takes two file names. The first file would contain
-word search grid as shown below. The second file contains list of words,
-one word per line. You could even use local dictionary file.
-
-Print out a list of all words seen on the grid, looking both orthogonally
-and diagonally, backwards as well as forwards.
-
-Search Grid
-
-B I D E M I A T S U C C O R S T
-L D E G G I W Q H O D E E H D P
-U S E I R U B U T E A S L A G U
-N G N I Z I L A I C O S C N U D
-T G M I D S T S A R A R E I F G
-S R E N M D C H A S I V E E L I
-S C S H A E U E B R O A D M T E
-H W O V L P E D D L A I U L S S
-R Y O N L A S F C S T A O G O T
-I G U S S R R U G O V A R Y O C
-N R G P A T N A N G I L A M O O
-E I H A C E I V I R U S E S E D
-S E T S U D T T G A R L I C N H
-H V R M X L W I U M S N S O T B
-A E A O F I L C H T O D C A E U
-Z S C D F E C A A I I R L N R F
-A R I I A N Y U T O O O U T P F
-R S E C I S N A B O S C N E R A
-D R S M P C U U N E L T E S I L
-
-Output
-
-Found 54 words of length 5 or more when checked against the local
-dictionary. You may or may not get the same result but that is fine.
-
-aimed, align, antes, argos, arose, ashed, blunt, blunts, broad, buries,
-clove, cloven, constitution, constitutions, croon, depart, departed,
-enter, filch, garlic, goats, grieve, grieves, hazard, liens, malign,
-malignant, malls, margo, midst, ought, ovary, parted, patna, pudgiest,
-quash, quashed, raped, ruses, shrine, shrines, social, socializing,
-spasm, spasmodic, succor, succors, theorem, theorems, traci, tracie,
-virus, viruses, wigged
+My notes: ok. pretty straightforward, especially after last weeks' first task.
+Not quite so trivial to do efficiently, my solution generates a lot of
+duplicate solutions (hence the dedup() function), and is very slow for large N.
+(See also ch-1a.pl for a tabulation of number of Fibonacci sums for i=1..N)
+
+
+Task 2: "Lonely X
+
+You are given m x n character matrix consists of O and X only.
+
+Write a script to count the total number of X surrounded by O only. Print
+0 if none found.
+
+Example 1:
+
+Input: [ O O X ]
+       [ X O O ]
+       [ X O O ]
+
+Output: 1 as there is only one X at the first row last column surrounded
+by only O.
+
+Example 2:
+
+Input: [ O O X O ]
+       [ X O O O ]
+       [ X O O X ]
+       [ O X O O ]
+
+Output: 2
+
+    a) First  X found at Row 1 Col 3.
+
+    b) Second X found at Row 3 Col 4.
 "
 
-My notes: oh god, really?  one question: when searching in a particular
-direction from a particular starting cell, are we supposed to find only
-the LONGEST dictionary word found in that direction?  this is normally
-the rule in wordgrid puzzles, but was not stated.  So I've coded "find
-all words in a particular direction from a particular starting cell",
-which is probably why I get many more words than mentioned above.
+My notes: interesting question, sounds simple but perhaps not quite
+as simple as it sounds.  Especially (obviously) "surrounded by only O"..
+Note that I counted rows and columns from 0, not 1.  So the output I
+generate for the second grid (file grid2) is:
+"2 lonely Xs in grid: [0, 2],[2, 3]"
diff --git a/challenge-077/duncan-c-white/perl/ch-1.pl b/challenge-077/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..4075900650
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl
+#
+# Task 1: "Fibonacci Sum
+#
+# You are given a positive integer $N.
+# 
+# Write a script to find out all possible combination of Fibonacci Numbers
+# required to get $N on addition.
+# 
+# You are NOT allowed to repeat a number. Print 0 if none found.
+# 
+# Example 1:
+# 
+# Input: $N = 6
+# 
+# Output:
+#     1 + 2 + 3 = 6
+#     1 + 5 = 6
+# 
+# Example 2:
+# 
+# Input: $N = 9
+# 
+# Output:
+#     1 + 8 = 9
+#     1 + 3 + 5 = 9
+# "
+# 
+# My notes: ok. pretty straightforward, especially after last weeks' first task,
+# and I'm glad to see that this week says "not repeated":-)
+# Not quite so trivial to do efficiently, my solution generates a lot of
+# duplicate solutions (hence the dedup() function), and is very slow for
+# large N.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: fibonacci-sum target\n" unless @ARGV==1;
+my $N = shift;
+
+# let's generate distinct Fibonacci numbers up to N (so skip one of the 1s)
+my @fib = (1);
+my $a = 1;
+my $b = 1;
+for(;;)
+{
+	my $c = $a+$b;
+last if $c > $N;
+	push @fib, $c;
+	$a = $b;
+	$b = $c;
+}
+
+#die Dumper( \@fib );
+
+
+#
+# my @soln = findsum( $s, \@used, @value );
+#	Try to find all lists of non-repeated values from @value (sorted)
+#	that sums to $s, given that we've already used @used.  Return a list
+#	of all such lists we find.  This list can be () if no lists are found.
+#	In each solution, each value is either used once or zero times.
+#
+fun findsum( $s, $used, @value )
+{
+	my @result;
+	#say "debug: findsum($s, used=@$used, value=@value)";
+	foreach my $v (@value)
+	{
+		#say "debug: findsum($s, used=@$used, v=$v, value=@value)";
+		if( $v > $s )
+		{
+			#say "debug: no solution found, v=$v > s=$s";
+			last;
+		}
+
+		if( $v == $s )
+		{
+			my @soln = (@$used,$v);
+			push @result, \@soln;
+			#say "debug: found solution @soln";
+			last;
+		}
+
+		# v < s: try solutions with v (for sum s-v) and without v
+		my @rest = grep { $_ ne $v } @value;
+
+		# use v:
+		push @result, findsum( $s-$v, [@$used,$v], @rest );
+
+		# don't use v
+		push @result, findsum( $s, [ @$used ], @rest );
+	}
+	return @result;
+}
+
+#
+# my @result = dedup( @soln );
+#	Given a list of solutions (each a list of values),
+#	deduplicate all solutions.  Return the deduplicated list of lists.
+#
+fun dedup( @soln )
+{
+	my %seen;
+	my @result = grep { $seen{join(',',sort @$_)}++ == 0 } @soln;
+	return @result;
+}
+
+
+my @soln = findsum( $N, [], @fib );
+@soln = dedup( @soln );
+my $nsoln = @soln;
+if( $nsoln )
+{
+	say "found $nsoln solutions (sum of distinct fibonacci numbers==$N):";
+	say join(',',@$_) for @soln;
+} else
+{
+	say "0";
+}
diff --git a/challenge-077/duncan-c-white/perl/ch-1a.pl b/challenge-077/duncan-c-white/perl/ch-1a.pl
new file mode 100755
index 0000000000..fbacc48366
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/ch-1a.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl
+#
+# Task 1: "Fibonacci Sum - Duncan's variant
+#
+# You are given a positive integer $N.
+# 
+# Write a script to find out all possible combination of Fibonacci Numbers
+# required to get 1, 2, 3... $N on addition.
+# 
+# You are NOT allowed to repeat a number. Print 0 if none found.
+# 
+# Example 1:
+# 
+# Input: $N = 6
+# 
+# Output:
+#     1 + 2 + 3 = 6
+#     1 + 5 = 6
+# 
+# Example 2:
+# 
+# Input: $N = 9
+# 
+# Output:
+#     1 + 8 = 9
+#     1 + 3 + 5 = 9
+# "
+# 
+# My notes: ok. pretty straightforward, especially after last weeks' first task,
+# and I'm glad to see that this week says "not repeated":-)
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: fibonacci-sum target\n" unless @ARGV==1;
+my $N = shift;
+
+# let's generate distinct Fibonacci numbers up to N (so skip one of the 1s)
+my @fib = (1);
+my $a = 1;
+my $b = 1;
+for(;;)
+{
+	my $c = $a+$b;
+last if $c > $N;
+	push @fib, $c;
+	$a = $b;
+	$b = $c;
+}
+
+#die Dumper( \@fib );
+
+
+#
+# my @soln = findsum( $s, \@used, @value );
+#	Try to find all lists of non-repeated values from @value (sorted)
+#	that sums to $s, given that we've already used @used.  Return a list
+#	of all such lists we find.  This list can be () if no lists are found.
+#	In each solution, each value is either used once or zero times.
+#
+fun findsum( $s, $used, @value )
+{
+	my @result;
+	#say "debug: findsum($s, used=@$used, value=@value)";
+	foreach my $v (@value)
+	{
+		#say "debug: findsum($s, used=@$used, v=$v, value=@value)";
+		if( $v > $s )
+		{
+			#say "debug: no solution found, v=$v > s=$s";
+			last;
+		}
+
+		if( $v == $s )
+		{
+			my @soln = (@$used,$v);
+			push @result, \@soln;
+			#say "debug: found solution @soln";
+			last;
+		}
+
+		# v < s: try solutions with v (for sum s-v) and without v
+		my @rest = grep { $_ ne $v } @value;
+
+		# use v:
+		push @result, findsum( $s-$v, [@$used,$v], @rest );
+
+		# don't use v
+		push @result, findsum( $s, [ @$used ], @rest );
+	}
+	return @result;
+}
+
+#
+# my @result = dedup( @soln );
+#	Given a list of solutions (each a list of values),
+#	deduplicate all solutions.  Return the deduplicated list of lists.
+#
+fun dedup( @soln )
+{
+	my %seen;
+	my @result = grep { $seen{join(',',sort @$_)}++ == 0 } @soln;
+	return @result;
+}
+
+
+foreach my $x (1..$N)
+{
+	my @soln = findsum( $x, [], @fib );
+	@soln = dedup( @soln );
+	my $nsoln = @soln;
+	if( $nsoln )
+	{
+		say "found $nsoln solutions (sum of distinct fibonacci numbers==$x):";
+		#say join(',',@$_) for @soln;
+	} else
+	{
+		say "0 solutions for x=$x";
+	}
+}
diff --git a/challenge-077/duncan-c-white/perl/ch-2.pl b/challenge-077/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..43ea7163bc
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,151 @@
+#!/usr/bin/perl
+#
+# Task 2: "Lonely X
+#
+# You are given m x n character matrix consists of O and X only.
+# 
+# Write a script to count the total number of X surrounded by O only. Print
+# 0 if none found.
+# 
+# Example 1:
+# 
+# Input: [ O O X ]
+#        [ X O O ]
+#        [ X O O ]
+# 
+# Output: 1 as there is only one X at the first row last column surrounded
+# by only O.
+# 
+# Example 2:
+# 
+# Input: [ O O X O ]
+#        [ X O O O ]
+#        [ X O O X ]
+#        [ O X O O ]
+# 
+# Output: 2
+# 
+#     a) First  X found at Row 1 Col 3.
+# 
+#     b) Second X found at Row 3 Col 4.
+# "
+# 
+# My notes: interesting question, sounds simple but perhaps not quite
+# as simple as it sounds.  Especially (obviously) "surrounded by only O"..
+# Note that I counted rows and columns from 0, not 1.  So the output I
+# generate for the second grid (file grid2) is:
+# "2 lonely Xs in grid: [0, 2],[2, 3]"
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+use List::Util qw(max);
+
+die "Usage: lonely-x ox-filename\n" unless @ARGV==1;
+my $filename = shift;
+
+#
+# my @g = readgrid($filename);
+#	Read the ox grid file, return @g, the grid
+#	(an array of array-refs).
+#
+fun readgrid( $filename )
+{
+	open( my $infh, '<', $filename ) || die;
+	my @result;
+	while( <$infh> )
+	{
+		chomp;
+		tr/ \t[]//d;
+		die "readgrid: bad line '$_'\n" unless /^[OX]+$/;
+		my @ch = split(//);
+		push @result, \@ch;
+	}
+	close($infh);
+	return @result;
+}
+
+my @dir =
+(
+	[-1,0],	# up (delta r,c)
+	[-1,1], # ne
+	[0,1],  # e
+	[1,1],  # se
+	[1,0],  # down
+	[1,-1], # sw
+	[0,-1], # w
+	[-1,-1],# nw
+);
+
+
+#
+# my @sol = findlonelyxs( @grid );
+#	Given @grid, a grid (array of array refs) read by readgrid(),
+#	find all lonely Xs.  Return an array of [R,C] pairs.
+#
+fun findlonelyxs( @grid )
+{
+	my $rows = @grid;
+	my $cols = @{$grid[0]};
+	#say "debug: rows=$rows, cols=$cols";
+
+	my @result;
+	foreach my $r (0..$rows-1)
+	{
+		foreach my $c (0..$cols-1)
+		{
+			if( $grid[$r][$c] eq 'X' )
+			{
+				if( lonelyX( $r, $c, @grid ) )
+				{
+					#say "debug: found lonely X @ r=$r, c=$c";
+					push @result, [$r,$c];
+				}
+			}
+		}
+	}
+	return @result;
+}
+
+
+#
+# my $islonely = lonelyX( $r, $c, @grid );
+#	Given that cell ($r,$c) in @grid is an X, is it a lonely one?
+#	Return 1 iff it is, otherwise 0.
+#
+fun lonelyX( $r, $c, @grid )
+{
+	my $rows = @grid;
+	my $cols = @{$grid[0]};
+
+	# build the "str of adjacent cell values" in $adjstr.
+	my $adjstr = "";
+
+	foreach my $dir (@dir)
+	{
+		my( $dr, $dc ) = @$dir;
+		my $r2 = $r+$dr;
+		my $c2 = $c+$dc;
+
+		# have we fallen off the grid?
+		next if $r2<0 || $r2>=$rows || $c2<0 || $c2>=$cols;
+		my $ch = $grid[$r2][$c2];
+		#say "debug: X pos ($r,$c), adj pos ($r2,$c2) on board, is $ch";
+		$adjstr .= $ch;
+	}
+	#say "debug: X @ ($r,$c): adjstr: $adjstr";
+
+	# not lonely if any 'X' in $adjstr, otherwise lonely
+	return $adjstr =~ /X/ ? 0 : 1;
+}
+
+
+my @g = readgrid($filename);
+#say Dumper \@g;
+
+my @sol = findlonelyxs( @g );
+my $n = @sol;
+say "$n lonely Xs in grid: ", join(',',map { my($r,$c)=@$_; "[$r, $c]" } @sol);
diff --git a/challenge-077/duncan-c-white/perl/grid0 b/challenge-077/duncan-c-white/perl/grid0
new file mode 100644
index 0000000000..6eb9fec4a9
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/grid0
@@ -0,0 +1,3 @@
+[ O O X ]
+[ X O X ]
+[ X O O ]
diff --git a/challenge-077/duncan-c-white/perl/grid1 b/challenge-077/duncan-c-white/perl/grid1
new file mode 100644
index 0000000000..f6034dc2f3
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/grid1
@@ -0,0 +1,3 @@
+[ O O X ]
+[ X O O ]
+[ X O O ]
diff --git a/challenge-077/duncan-c-white/perl/grid2 b/challenge-077/duncan-c-white/perl/grid2
new file mode 100644
index 0000000000..723198205d
--- /dev/null
+++ b/challenge-077/duncan-c-white/perl/grid2
@@ -0,0 +1,4 @@
+[ O O X O ]
+[ X O O O ]
+[ X O O X ]
+[ O X O O ]