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