diff options
| -rw-r--r-- | challenge-126/duncan-c-white/README | 93 | ||||
| -rwxr-xr-x | challenge-126/duncan-c-white/perl/ch-1.pl | 63 | ||||
| -rwxr-xr-x | challenge-126/duncan-c-white/perl/ch-2.pl | 146 | ||||
| -rw-r--r-- | challenge-126/duncan-c-white/perl/minesweeper.in | 5 |
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 |