Merge pull request #2225 from dcw803/master

belatedly finished the second question and imported my solutions

6 files changed, 536 insertions, 62 deletions

diff --git a/challenge-076/duncan-c-white/README b/challenge-076/duncan-c-white/README
index 07716b97a6..4a35d35c82 100644
--- a/challenge-076/duncan-c-white/README
+++ b/challenge-076/duncan-c-white/README
@@ -1,71 +1,69 @@
-Task 1: "Coins Sum
+Task 1: "Prime Sum
 
-You are given a set of coins @C, assuming you have infinite amount of each coin in the set.
+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.
 
-Write a script to find how many ways you make sum $S using the coins from the set @C.
 Example:
 
 Input:
-    @C = (1, 2, 4)
-    $S = 6
+    $N = 9
 
-Output: 6
-There are 6 possible ways to make sum 6.
-a) (1, 1, 1, 1, 1, 1)
-b) (1, 1, 1, 1, 2)
-c) (1, 1, 2, 2)
-d) (1, 1, 4)
-e) (2, 2, 2)
-f) (2, 4)
+Ouput:
+    2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
+    2 + 7 = 9.
 "
 
-My notes: ok.  Reasonably easy: bag of coins shows what coins we've used,
-at every stage explore 2 paths: 1). add another instance of each possible coin,
-2). don't add another instance..
-
-Task 2: "Largest Rectangle Histogram
-
-You are given an array of positive numbers @A.
-
-Write a script to find the largest rectangle histogram created by the given array.
-BONUS: Try to print the histogram as shown in the example, if possible.
-
-Example 1:
-
-Input: @A = (2, 1, 4, 5, 3, 7)
-
-     7           #
-     6           #
-     5       #   #
-     4     # #   #
-     3     # # # #
-     2 #   # # # #
-     1 # # # # # #
-     _ _ _ _ _ _ _
-       2 1 4 5 3 7
-
-Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns (4, 5, 3 and 7).
-Output: 12
-
-Example 2:
-
-Input: @A = (3, 2, 3, 5, 7, 5)
-
-     7         #
-     6         #
-     5       # # #
-     4       # # #
-     3 #   # # # #
-     2 # # # # # #
-     1 # # # # # #
-     _ _ _ _ _ _ _
-       3 2 3 5 7 5
-
-Looking at the above histogram, the largest rectangle (3 x 5) is formed by columns (5, 7 and 5).
-Output: 15"
+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: hmm.. so max(area of all rectangles "in" a histogram).  But what does that mean?
-Hang on: the "graphs" are NOT actually histograms: each is simply the array of values itself.
-So forgot frequency hashes.  The simplest way that I can see is to calculate the area of all
-possible rectangles (where 1 or more adjacent values are at least some minimum height) and
-then to find the maximum of all those.
+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.
diff --git a/challenge-076/duncan-c-white/perl/MakePrimes.pm b/challenge-076/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..7261977c57
--- /dev/null
+++ b/challenge-076/duncan-c-white/perl/MakePrimes.pm
@@ -0,0 +1,91 @@
+#
+#	mkprimes module (converted from mkprimes.c)
+#
+
+use strict;
+use warnings;
+use Function::Parameters;
+
+
+my $debug = 0;
+my @foundprimes;	# remember all primes we've found..
+
+
+#
+# my @primes = primes_upto( $n );
+#	Find all primes up to N; return a list of all such primes
+#	(note that 1 is not usually considered a prime)
+#
+fun primes_upto( $n )
+{
+	my @isprime;
+
+	for( my $i=1; $i<=$n; $i++ )
+	{
+		$isprime[$i] = 1;		# initially
+	}
+
+	# now sieve the non-primes out..
+	my $upper = int(sqrt($n));
+	printf( "debug: n=%d, upper=%d\n", $n, $upper ) if $debug;
+	for( my $i=2; $i<=$upper; $i++ )
+	{
+		if( $isprime[$i] )
+		{
+			#printf( "debug: crossing out multiples of %d\n", $i );
+			for( my $j=$i*$i; $j<=$n; $j+=$i )
+			{
+				$isprime[$j] = 0;
+			}
+		}
+	}
+
+	# after sieving, extract the primes
+	my @primes = grep { $isprime[$_] } 2..$n;
+
+	# remember them
+	@foundprimes = @primes;
+
+	return @primes;
+}
+
+
+#
+# my @moreprimes = more_primes( $n, $m );
+#	Need more primes!  Have @foundprimes up to $n, but need
+#	to sieve primes from $n+1..$m, so re-sieve, return
+#	a list of all new primes (in the range $n+1..$m) that we find.
+#
+fun more_primes( $n, $m )
+{
+	my %isprime;
+
+	print "finding more primes from ", $n+1, "..$m\n";
+
+	for( my $i=$n+1; $i<=$m; $i++ )
+	{
+		$isprime{$i} = 1;	# pre-sieving
+	}
+
+	# now sieve the non-primes out..
+	foreach my $prime (@foundprimes)
+	{
+		# find first multiple of $prime > $n
+		my $mult = $prime * (int($n/$prime)+1);
+
+		#print "debug: xo multiples of $prime from $mult to $m\n";
+
+		for( my $j=$mult; $j<=$m; $j+=$prime )
+		{
+			delete $isprime{$j};
+		}
+	}
+
+	# after sieving, extract the primes
+	my @primes = grep { $isprime{$_} } $n+1..$m;
+	push @foundprimes, @primes;
+	return @primes;
+}
+
+
+1;
diff --git a/challenge-076/duncan-c-white/perl/ch-1.pl b/challenge-076/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..95554e621e
--- /dev/null
+++ b/challenge-076/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,87 @@
+#!/usr/bin/perl
+#
+# Task 1: "Prime 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.
+# 
+# Example:
+# 
+# Input:
+#     $N = 9
+# 
+# Ouput:
+#     2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
+#     2 + 7 = 9.
+# "
+# 
+# My notes: ok. pretty straightforward.  One question: do the primes have to be
+# different, it doesn't say "minimum number of DIFFERENT prime numbers.." so I
+# assume they can be the same..
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+use lib qw(.);
+use MakePrimes;
+
+die "Usage: prime-sum target\n" unless @ARGV==1;
+my $N = shift;
+
+my @primes = primes_upto( $N );	# definitely enough
+
+my %isprime = map { $_ => 1 } @primes;
+
+if( $isprime{$N} )
+{
+	say "$N is a prime: so sum of 1-prime ($N itself) is $N";
+	exit 0;
+}
+
+
+#
+# my @soln = findsum( $nprimes, $N );
+#	Try to find a list of exactly $nprimes primes (held in global @primes)
+#	that sums to $N.  If we find such a list of primes, return that list.
+#	If we find no such list of primes, return ().
+#
+fun findsum( $nprimes, $N )
+{
+	if( $nprimes == 1 )
+	{
+		return $isprime{$N} ? ($N) : ();
+	}
+	# $nprimes>1
+	foreach my $p (@primes)
+	{
+		last if $p >= $N;
+
+		# $p < $N
+		my @soln = findsum( $nprimes-1, $N-$p );
+		if( @soln )
+		{
+			unshift @soln, $p;
+			return @soln;
+		}
+
+	}
+	return ();
+}
+
+
+foreach my $nprimes (2..$N)
+{
+	say "looking for an $nprimes-primes sum that is $N";
+	my @soln = findsum( $nprimes, $N );
+	if( @soln )
+	{
+		say "found sum of $nprimes primes == $N, primes are: ", join(',',@soln);
+		last;
+	}
+}
+
diff --git a/challenge-076/duncan-c-white/perl/ch-1a.pl b/challenge-076/duncan-c-white/perl/ch-1a.pl
new file mode 100755
index 0000000000..2e112a86d4
--- /dev/null
+++ b/challenge-076/duncan-c-white/perl/ch-1a.pl
@@ -0,0 +1,79 @@
+#!/usr/bin/perl
+#
+# Task 1: "Prime 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.
+# 
+# Example:
+# 
+# Input:
+#     $N = 9
+# 
+# Ouput:
+#     2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
+#     2 + 7 = 9.
+# "
+# 
+# My notes: VARIATION: let's find out the smallest number $N that CANNOT be represented
+# as a sum of 2 prime numbers..
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+use lib qw(.);
+use MakePrimes;
+
+die "Usage: smallestn-not-sum-2-primes\n" unless @ARGV==0;
+
+my @primes = primes_upto( 100 );
+my %isprime = map { $_ => 1 } @primes;
+
+
+#
+# my @soln = findsum( $nprimes, $N );
+#	Try to find a list of exactly $nprimes primes (held in global @primes)
+#	that sums to $N.  If we find such a list of primes, return that list.
+#	If we find no such list of primes, return ().
+#
+fun findsum( $nprimes, $N )
+{
+	if( $nprimes == 1 )
+	{
+		return $isprime{$N} ? ($N) : ();
+	}
+	# $nprimes>1
+	foreach my $p (@primes)
+	{
+		last if $p >= $N;
+
+		# $p < $N
+		my @soln = findsum( $nprimes-1, $N-$p );
+		if( @soln )
+		{
+			unshift @soln, $p;
+			return @soln;
+		}
+
+	}
+	return ();
+}
+
+
+foreach my $N (2..100)
+{
+	my @soln = findsum( 2, $N );
+	if( @soln )
+	{
+		#say "found sum of 2 primes == $N, primes are: ", join(',',@soln);
+	} else
+	{
+		say "DIDN'T find sum of 2 primes == $N";
+	}
+}
+
diff --git a/challenge-076/duncan-c-white/perl/ch-2.pl b/challenge-076/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..2bee6eda2b
--- /dev/null
+++ b/challenge-076/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,200 @@
+#!/usr/bin/perl
+#
+# 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: 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.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+use List::Util qw(max);
+
+die "Usage: word-search wordgrid-filename dict-filename\n" unless @ARGV==2;
+my( $gridfilename, $dictfilename ) = @ARGV;
+
+#
+# my @g = readgrid($gridfilename);
+#	Read the wordgrid filename, return @g, the grid
+#	(an array of array-refs).
+#
+fun readgrid( $gridfilename )
+{
+	open( my $infh, '<', $gridfilename ) || die;
+	my @result;
+	while( <$infh> )
+	{
+		chomp;
+		tr/ \t//d;
+		my @ch = split(//);
+		push @result, \@ch;
+	}
+	close($infh);
+	return @result;
+}
+
+#
+# my %words = readdict($dictfilename);
+#	Read the dictionary filename, one word per line,
+#	return a hash of upper-cased plain ASCII words.
+#
+fun readdict( $dictfilename )
+{
+	open( my $infh, '<', $dictfilename ) || die;
+	my %result;
+	while( <$infh> )
+	{
+		chomp;
+		$_ = uc($_);
+		$result{$_}++ if /^[A-Z][A-Z]+$/;
+	}
+	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 %foundword = findwordsonedir($grid,$isdictword,$r,$c,$deltar,$deltac);
+#	Find all dictionary words (for which $isdictword->{word} is true)
+#	contained in the grid starting at ($r,$c), looking in the
+#	direction represented by ($deltar,$deltac)
+#	as far as you like (without falling off the grid).
+#	Return the set of words found, or () if no dictionary word is found.
+#
+fun findwordsonedir($grid,$isdictword,$r,$c,$deltar,$deltac)
+{
+	my %result;
+	my $rows = @$grid;
+	my $cols = @{$grid->[0]};
+	my $word = $grid->[$r][$c];
+	for( my $len = 1; ; $len++ )
+	{
+		$r += $deltar;
+		$c += $deltac;
+		last unless $r>=0 && $r<$rows && $c>=0 && $c<$cols;
+		$word .= $grid->[$r][$c];
+		next unless $isdictword->{$word};
+		#say "found dict word $word";
+		$result{$word}++;
+	} 
+	my @found = sort keys(%result);
+	if( @found==0 )
+	{
+		#say "no dict words starting from ($r,$c) in direction ($deltar,$deltac)";
+	}
+	else
+	{
+		say "dict words starting from ($r,$c) in direction ($deltar,$deltac): ",
+			join(',',@found);
+	}
+	return %result;
+}
+
+
+#
+# my @found = findwords( $grid, $isword );
+#	Find all words (for which $isword->{word} is true)
+#	contained in the grid, looking in all 8 orthogonal
+#	(up/down, left/right) and diagonal directions.
+#	Return the list of all such distinct words found.
+#
+fun findwords( $grid, $isword )
+{
+	my $rows = @$grid;
+	my $cols = @{$grid->[0]};
+	say "rows=$rows, cols=$cols";
+	#say "isword(BIDE) = ", $isword->{BIDE}//"null";
+
+	my %result;
+	foreach my $r (0..$rows-1)
+	{
+		foreach my $c (0..$cols-1)
+		{
+			foreach my $dir (@dir)
+			{
+				my( $dr, $dc ) = @$dir;
+				#say "starting at grid pos ($r,$c), dir ($dr,$dc)";
+				my %foundword = findwordsonedir($grid,$isword,$r,$c,$dr,$dc);
+				my @found = keys %foundword;
+				next unless @found;
+				@result{@found}=(1) x scalar(@found);
+			}
+		}
+	}
+	return sort(keys %result);
+}
+
+
+my @g = readgrid($gridfilename);
+#say Dumper \@g;
+
+my %isword = readdict($dictfilename);
+#say Dumper \%isword;
+##say "isword(BIDE) = ", $isword{BIDE}//"null";
+
+my @found = findwords( \@g, \%isword );
+my $n = @found;
+say "found $n words in grid: ", join(',',@found);
diff --git a/challenge-076/duncan-c-white/perl/grid1 b/challenge-076/duncan-c-white/perl/grid1
new file mode 100644
index 0000000000..31cf2e0fd8
--- /dev/null
+++ b/challenge-076/duncan-c-white/perl/grid1
@@ -0,0 +1,19 @@
+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