# Perl Weekly Challenge 126.

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

``````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)✕9d-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 9d-1. The second term contributes the same count as the number bcd…, provided a≠1, suggesting the following recursive solution.

``````# Perl weekly challenge 126
# Task 1:  Count numbers. Recursive solution
#
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.

``````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
#
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
``````
Written on August 20, 2021