# Perl Weekly Challenge 126.

My solutions (task 1, and task 2 ) to the The Weekly Challenge - 126.

# Task 1: Count Numbers

```
Submitted by: Mohammad S Anwar
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.
```

A quick solution consists of enumerating all numbers up to *N*
discarding those that contain a ‘1’ and then counting them.

```
perl -E 'say "Input: $_\nOutput: ", scalar grep {$_!~/1/} 1..$_ foreach @ARGV' 15 25 1000
```

Results:

```
Input: 15
Output: 8
Input: 25
Output: 13
Input: 1000
Output: 728
```

This may take a long time and consume a lot of memory for very large numbers:

```
time (perl -E 'say "Input: $_\nOutput: ", scalar grep {$_!~/1/} 1..$_ foreach @ARGV' 1e8) 2>&1
```

Results:

```
Input: 1e8
Output: 43046720
real 0m43.292s
user 0m39.539s
sys 0m3.111s
```

Thus, a more complicated but faster approach may be
better. Consider a *d* digit number *N=abcd…* with *a, b, c…* its
decimal digits. I can first count up from *0* up to *(a-1)999…*,
then from *a000…* up to *abcd…*, and finally substract 1,
corresponding to the initial 0. The first set yields simply
*(a-1)✕9 ^{d-1}*, as there are nine posibilities

*(0,2,3,4,5,6,7,8,9)*for the rightmost

*d-1*digits and

*a-1*possibilities

*(0,2,3…a-1)*for the leftmost digit. The case

*a=0,1*are special:

*a=0*doesn’t contribute and

*a=1*contributes

*9*. The second term contributes the same count as the number

^{d-1}*bcd…*, provided

*a≠1*, suggesting the following recursive solution.

```
# Perl weekly challenge 126
# Task 1: Count numbers. Recursive solution
#
# See https://wlmb.github.io/2021/08/20/PWC126/#task-1-count-numbers
use warnings;
use strict;
use v5.12;
use POSIX qw(floor);
die "Usage: ./ch-1.pl N1 N2... to count numbers up to Ni with no 1's"
unless @ARGV;
foreach(@ARGV){
my $N=floor($_); # check non-negative integer arguments
warn("Expected natural: $_"), next unless $N>=0 and $N==$_;
say "Input: $_\nOutput: ", $N>1?count(split '',$N)-1:0;
}
sub count {
state @m1=(0,1,1..8);
state @m2=(1,0,(1)x8);
my ($first,@rest)=@_;
return 1 unless defined $first;
return $m1[$first]*9**@rest+$m2[$first]*count(@rest); #$first>1
}
```

Example:

```
./ch-1.pl 15 25 1000
```

Results:

```
Input: 15
Output: 8
Input: 25
Output: 13
Input: 1000
Output: 728
```

Thus it seems to work.

Large example:

```
time (./ch-1.pl 1e8) 2>&1
```

Results:

```
Input: 1e8
Output: 43046720
real 0m0.044s
user 0m0.032s
sys 0m0.012s
```

In this case this solution is about a thousand times faster than the straightforward solution. Thus I can go for much larger inputs

```
time (perl -MPOSIX=INT_MAX -E 'say INT_MAX," ", 4194304*INT_MAX'|xargs ./ch-1.pl ) 2>&1
```

Results:

```
Input: 2147483647
Output: 430467209
Input: 9007199250546688
Output: 1648855015035686
real 0m0.043s
user 0m0.037s
sys 0m0.007s
```

So the total time for 16 digit numbers is less than five
hundredths of a second. The last input I tested is the largest multiple
of `INT_MAX`

for which there was no floating point conversion. I
don’t know why this conversion takes place before I reached `LONG_MAX`

, which is about a
thousand times larger.

# Task 2: Minesweeper Game

```
Submitted by: Cheok-Yin Fung
You are given a rectangle with points marked with either x or
*. Please consider the x as a land mine.
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
```

This problem is easily solved using the conv2d function of the
*Perl Data Language* `PDL`

. I first translate the input into a
matrix with 1’s for sites with mines and 0’s for sites without
mines. I make a convolution of that matrix with a 3x3 kernel,

```
1 1 1
1 -9 1
1 1 1
```

full of ones in the periphery with a large negative number in the middle, obtaining a matrix where each entry is the number of bombs in the neighborhood of the corresponding site, or a negative number if there is a bomb on the site. Finally, I format this matrix for output, replacing negative numbers by bomb indicators.

```
# Perl weekly challenge 126
# Task 1: Minesweeper game
#
# See https://wlmb.github.io/2021/08/20/PWC126/#task-2-mineseeper-game
use warnings;
use strict;
use v5.12;
use PDL;
use PDL::Image2D; # for conv2d
my $input=process_input();
my $kernel=pdl([1,1,1],[1,-9,1],[1,1,1]);
my $output=$input->conv2d($kernel, {Boundary=>'Truncate'});
# Make strings and format them
(my $input_str="$input")=~tr(01[])(*x)d; #translate and remove brackets
my $output_str="$output";
$output_str=~s/-\d+/ x/g; #identify sites with bombs
$output_str=~s/ +/ /g; #separate sites with single spaces
$output_str=~tr([])()d; #remove brackets
say "Input:$input_str\nOutput:$output_str";
sub process_input {
my $length;
my @input;
while(<>){ # read input from STDIN
chomp;
next if /^\s*$/; #ignore null lines
die "Only 'x' and '*' and spaces allowed: $_" unless m/^[x* \t]*$/;
tr(*x \t)(01)d;
my @line=split '';
die "All lines should have the same length: $_"
if defined $length and $length!=@line;
$length//=@line;
push @input, [@line];
}
pdl [@input];
}
```

Example:

```
./ch-2.pl <<" END"
x * * * x * x x x x
* * * * * * * * * x
* * * * x * x * x *
* * * x x * * * * *
x * * * x * * * * x
END
```

Results:

```
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
```