Merge pull request #4767 from dcw803/master

imported my solution's to this week's challenge - 2 nice tasks…

4 files changed, 252 insertions, 55 deletions

diff --git a/challenge-126/duncan-c-white/README b/challenge-126/duncan-c-white/README
index 366395c261..aa79957d19 100644
--- a/challenge-126/duncan-c-white/README
+++ b/challenge-126/duncan-c-white/README
@@ -1,74 +1,57 @@
-Task 1: "Pythagorean Triples
+Task 1: "Count Numbers
 
 You are given a positive integer $N.
 
-Write a script to print all Pythagorean Triples containing $N as a
-member. Print -1 if it can't be a member of any. i
-
-Triples with the same set of elements are considered the same, i.e. if
-your script has already printed (3, 4, 5), (4, 3, 5) should not be
-printed.
-
-The famous Pythagorean theorem states that in a right angle triangle,
-the length of the two shorter sides and the length of the longest
-side are related by a2+b2 = c2.
-
-A Pythagorean triple refers to the triple of three integers whose lengths
-can compose a right-angled triangle.
+Write a script to print count of numbers from 1 to $N that don't
+contain digit 1.
 
 Example
 
-    Input: $N = 5
-    Output:
-        (3, 4, 5)
-        (5, 12, 13)
-
-    Input: $N = 13
-    Output:
-        (5, 12, 13)
-        (13, 84, 85)
-
-    Input: $N = 1
-    Output:
-        -1
-"
+Input: $N = 15
+Output: 8
 
-My notes: the tricky part here is knowing how to generate all Pythagorean
-triples that MIGHT contain $N, i.e. when to stop generating triples..
+    There are 8 numbers between 1 and 15 that don't contain digit 1.
+    2, 3, 4, 5, 6, 7, 8, 9.
 
+Input: $N = 25
+Output: 13
 
-Task 2: "Binary Tree Diameter
-
-You are given binary tree as below:
-
-    1
-   / \
-  2   5
- / \ / \
-3  4 6  7
-       / \
-      8  10
-     /
-    9
-
-Write a script to find the diameter of the given binary tree.
+    There are 13 numbers between 1 and 25 that don't contain digit 1.
+    2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25.
+"
 
-    The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn't have to pass through the root.
+My notes: very easy.  Let's produce the "There are ..." output if --debug
+is given, the terse output otherwise.
 
-For the above given binary tree, possible diameters (6) are:
 
-3, 2, 1, 5, 7, 8, 9
+Task 2: "Minesweeper Game
 
-or
+You are given a rectangle with points marked with either x or *.
+Please consider the x as a land mine (DCW adds: and a * as a non-landmine).
 
-4, 2, 1, 5, 7, 8, 9
+Write a script to print a rectangle with numbers and x as in the
+Minesweeper game.
 
+A number in a square of the minesweeper game indicates the number
+of mines within the neighbouring squares (usually 8), also implies
+that there are no bombs on that square.
 
-UPDATE (2021-08-10 17:00:00 BST): Jorg Sommrey corrected the example.
+Example
 
-The length of a path is the number of its edges, not the number of the vertices it connects. So the diameter should be 6, not 7.
+Input:
+    x * * * x * x x x x
+    * * * * * * * * * x
+    * * * * x * x * x *
+    * * * x x * * * * *
+    x * * * x * * * * x
+
+Output:
+    x 1 0 1 x 2 x x x x
+    1 1 0 2 2 4 3 5 5 x
+    0 0 1 3 x 3 x 2 x 2
+    1 1 1 x x 4 1 2 2 2
+    x 1 1 3 x 2 0 0 1 x
 "
 
-My notes: Looks quite tricky.  We can use generate and test - if we can
-generate all paths, then we could do a "max" test.  Also, how to represent
-the binary tree?  let's hard-code it for now.
+My notes: also looks pretty easy.  It's not the WHOLE minesweeper game,
+just the "work out what the finished puzzle looks like"
diff --git a/challenge-126/duncan-c-white/perl/ch-1.pl b/challenge-126/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..b99c4c617d
--- /dev/null
+++ b/challenge-126/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,63 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Count Numbers
+# 
+# You are given a positive integer $N.
+# 
+# Write a script to print count of numbers from 1 to $N that don't
+# contain digit 1.
+# 
+# Example
+# 
+# Input: $N = 15
+# Output: 8
+# 
+#     There are 8 numbers between 1 and 15 that don't contain digit 1.
+#     2, 3, 4, 5, 6, 7, 8, 9.
+# 
+# Input: $N = 25
+# Output: 13
+# 
+#     There are 13 numbers between 1 and 25 that don't contain digit 1.
+#     2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25.
+# "
+# 
+# My notes: very easy.  Let's produce the "There are ..." output if --debug
+# is given, the terse output otherwise.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: count-numbers-wo-1 [-d|--debug] N\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $n = shift;
+die "count-numbers-wo-1: N ($n) must be > 0\n" unless $n>0;
+
+#
+# my @answers = find_numbers_wo_1( $n );
+#	Find all numbers between 1 and $n NOT containing /1/;
+#	return the array of such numbers.
+#
+fun find_numbers_wo_1( $n )
+{
+	my @x = grep { ! /1/ } 2..$n;
+	return @x;
+}
+
+
+my @answers = find_numbers_wo_1( $n );
+my $nanswers = @answers;
+if( $debug )
+{
+	say "There are $nanswers numbers between 1 and $n that don't contain 1:";
+	say join(', ', @answers );
+} else
+{
+	say $nanswers;
+}
diff --git a/challenge-126/duncan-c-white/perl/ch-2.pl b/challenge-126/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..31ba6be6b8
--- /dev/null
+++ b/challenge-126/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,146 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Minesweeper Game
+# 
+# You are given a rectangle with points marked with either x or *.
+# Please consider the x as a land mine (DCW adds: and a * as a non-landmine).
+# 
+# Write a script to print a rectangle with numbers and x as in the
+# Minesweeper game.
+# 
+# A number in a square of the minesweeper game indicates the number
+# of mines within the neighbouring squares (usually 8), also implies
+# that there are no bombs on that square.
+# 
+# Example
+# 
+# Input:
+#     x * * * x * x x x x
+#     * * * * * * * * * x
+#     * * * * x * x * x *
+#     * * * x x * * * * *
+#     x * * * x * * * * x
+# 
+# Output:
+#     x 1 0 1 x 2 x x x x
+#     1 1 0 2 2 4 3 5 5 x
+#     0 0 1 3 x 3 x 2 x 2
+#     1 1 1 x x 4 1 2 2 2
+#     x 1 1 3 x 2 0 0 1 x
+# "
+# 
+# My notes: also looks pretty easy.  It's not the WHOLE minesweeper game,
+#  just the "work out what the finished puzzle looks like"
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Getopt::Long;
+use Data::Dumper;
+
+my $debug = 0;
+
+die "Usage: minesweeper [-d|--debug]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==0;
+
+#
+# my @board = read_board( $fh );
+#	Read the board from input file $fh, building
+#	a 2D array of rows x columns, skipping any amount
+#	of whitespace.  Every non-blank character is either
+#	an 'x' (meaning "this cell is a mine") or '*' (meaning
+#	"this cell is not a mine").  We'd better check that
+#	every row has the same number of columns..
+#
+fun read_board( $fh )
+{
+	my @board;
+	my $ncols = -1;
+	while( <$fh> )
+	{
+		chomp;
+		last unless /[x*]/;
+		s/^\s+//;
+		s/\s+$//;
+		s/\s\s+/ /g;
+		my @row = split( /\s/ );
+		$ncols = @row if $ncols == -1;
+		my $cols = @row;
+		die "read_board: line $_ has $cols columns (earlier lines ".
+		    "have $ncols columns)\n" unless $cols == $ncols;
+		push @board, \@row;
+	}
+	return @board;
+}
+
+
+#
+# show_board( @b );
+#	Show the board @b.
+#
+fun show_board( @b )
+{
+	foreach my $row (@b)
+	{
+		say join(' ', @$row );
+	}
+}
+
+
+#
+# my $val = mark( $r, $c, $cell, $board );
+#	Mark cell $cell ($r,$c) on @$board; return 'x' for mine
+#	or a number 0..8 for number of surrounding mines.
+#
+fun mark( $r, $c, $cell, $board )
+{
+	return 'x' if $cell eq 'x';
+	my $cols = @{$board->[0]};
+	my $count = 0;
+	foreach my $rn ($r-1..$r+1)
+	{
+		foreach my $cn ($c-1..$c+1)
+		{
+			next if $rn == $r && $cn == $c;
+			next if $rn < 0 || $rn >= @$board;
+			next if $cn < 0 || $cn >= $cols;
+			$count++ if $board->[$rn][$cn] eq 'x';
+		}
+	}
+	return $count;
+}
+
+
+#
+# my @output = minesweep( @board );
+#	Solve the problem: given a board in which mines are marked with 'x'
+#	and non-mines as a '*', count up the mines near each cell and return
+#	the marked, mineswept, output.
+#
+fun minesweep( @board )
+{
+	my @result;
+	foreach my $r (0..$#board)
+	{
+		my $row = $board[$r];
+		my @newrow;
+		foreach my $c (0..$#$row)
+		{
+			my $cell = $row->[$c];
+			my $newcell = mark( $r, $c, $cell, \@board );
+			push @newrow, $newcell;
+		}
+		push @result, \@newrow;
+	}
+	return @result;
+}
+
+
+my @board = read_board( \*STDIN );
+#show_board( @board );
+#exit 0;
+
+my @output = minesweep( @board );
+show_board( @output );
diff --git a/challenge-126/duncan-c-white/perl/minesweeper.in b/challenge-126/duncan-c-white/perl/minesweeper.in
new file mode 100644
index 0000000000..acf700e3c2
--- /dev/null
+++ b/challenge-126/duncan-c-white/perl/minesweeper.in
@@ -0,0 +1,5 @@
+     x * * * x * x x x x
+    * * * * *       * * * * x
+   * * * * x * x * x *
+  * *   * x x * *    * * *
+ x * * * x * * * * x