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