1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
# Perl Weekly Challenge #126
You can find more information about this weeks, and previous weeks challenges at:
https://perlweeklychallenge.org/
If you are not already doing the challenge - it is a good place to practise your
**perl** or **raku**. If it is not **perl** or **raku** you develop in - you can
submit solutions in whichever language you feel comfortable with.
You can find the solutions here on github at:
https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-126/james-smith/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`.***
## The solution
First pass - just do the simple `O(n)` thing which is to loop through all `$N` numbers and count those without `1`s.
```perl
sub get_no_one_count {
my $n = shift;
return scalar grep { ! m{1} } 2..$n;
}
```
If we look at a few numbers we see that for powers of 10 we see we have values 8, 80, 728, 6560, 59048, ... what we notices these are all of the form `9^$N-1`.... For multiples of these we see that for the total is `(n-1)*9^N`.
We see we can then add these up - with one exception if we find a 1 we stop the loop (or if working backwards) throw any calculations away - giving us the order `O(ln n)` solution:
```perl
sub get_no_one_count_9 {
my ( $n, $count, $pow_9 ) = ( shift, 0, 1 );
while($n) {
my $t = $n % 10; ## get last digit
$count = 0 if $t==1; ## Throw everything away we've found a 1
$count += $t ? ( $t == 1 ? ($pow_9-1) : ($t-1)*$pow_9 ) : 0;
## 0 it contributes nothing
## 1 contributes 9^X-1
## 2-9 contributes (n-1)9^X
$pow_9 *= 9; ## update power of nine
$n = ( $n - $t )/10; ## drop last digit
}
return $count;
}
```
## Comparison
Even for 2 digit numbers this speed up is good (72x), but as N increases
we see that gain gets higher and higher.. for 7 digit numbers the speed
up is 6 orders of magnitude.
| N | scan | opt | Speed-up |
| --------: | --------: | --------: | ---------: |
| 98 | 16,027 | 1,173,850 | 72 |
| 987 | 2,623 | 867,796 | 330 |
| 9,876 | 253 | 685,956 | 2,715 |
| 98,765 | 24.4 | 565,427 | 23,155 |
| 987,654 | 1.23 | 482,800 | 392,998 |
| 9,876,543 | 0.23 | 418,410 | 1,853,771 |
# Task 2 - Minesweeper Game
***You are given a rectangle with points marked with either `x` or `*`. Consider the `x` as a land mine. Write a script to print a rectangle with numbers and `x` as in the Minesweeper game.***
## Solution
```perl
sub solve {
my @res = ();
my @g = map { [ map { $_ eq 'x' ? 1 : 0 } split //, $_ ] } @_;
my( $h, $w ) = ( $#_, -1 + length $_[0] );
foreach my $y ( 0 .. $h ) {
push @res, join '', map {
$g[$y][$_] ? 'x' :
( $y ? ( $_ ? $g[$y-1][$_-1] : 0 ) +
$g[$y-1][$_ ] +
( $_<$w ? $g[$y-1][$_+1] : 0 )
: 0 ) +
( $_ ? $g[$y ][$_-1] : 0 ) +
$g[$y ][$_ ] +
( $_<$w ? $g[$y ][$_+1] : 0 ) +
( $y<$h ? ( $_ ? $g[$y+1][$_-1] : 0 ) +
$g[$y+1][$_ ] +
( $_<$w ? $g[$y+1][$_+1] : 0 )
: 0 )
} 0 .. $w;
}
return join "\n", @res;
}
```
There are two stages to this:
1. convert the strings into an array of `1`s and `0`s representing mines and spaces.
2. we compute the convulation - counting the number of mines in adjacent squares (or tagging with a "x" if the square is bomb).
Rather than using loops and if statements we use nested ternary operators in a single line
|
