I Sweep For No One

Wherein we plot a course through treacherous waters to a land no one is allowed to remain within…

THE WEEKLY CHALLENGE – PERL & RAKU #126

---

episode one:
“No One Belongs Here”

---

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.

Method

To only compute the count, and not the numbers themselves, we can construct a very compact expression to do the job. I suppose I could have made a one-liner, but I’m not particularly fond of them, to be honest. They serve well when required, of course, and there are a few aliased in my dot files. But I suppose they just don’t often fit my workflow. It’s no big deal, but there you are.

To produce our value, we do a little bit of functional list processing: starting on the right we create a list of values starting at 2 (of course) up to the target. We hand that list to a grep statement, which applies the block as a filter, allowing elements through that do not match with the number 1. Continuing leftward we determine the scalar value of the remaining list, telling us the number of elements that pass the test.

Then we print this quantity, which is the value requested.

Easy-peasy.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


say scalar grep { ! /1/ } (2..shift @ARGV) ; 

raku solution

In Raku we get to chain functions forward, so the order is (mostly) left-to-right. Starting with our list we again filter it and then find the size of the remaining array. We could have put the say as a method at the end, as

.say;

but I generally find that formatting buries the main verb. The speakers of languages who, at the end of the sentence the verb put, may disagree, but I find it clearer this way; to say: “say this”, and then describe what “this” is, rather than say: “Take this and do this and that to it and then say the result”. It gives you a reasoning for the whole context, and lets you know at the start why you’re here.

In related news, I always enjoy formatting Raku code, and thinking about formatting Raku code, and in general how to present code in such a way to make it as readable as possible. So of the code I read — well, some stylistic decisions I honestly do not understand. Not the code in itself mind you, rather just the formatting, but the formatting choices are certainly not helping matters. Are spaces so precious we’re rationing them?

I once heard it explained that when operating from a dumb terminal over a 1200 baud line every character would take a noticeable amount of time to send down the wire, and so it made sense to use one-character variable names and remove all space around brackets and operators. Later perhaps this trend continued where memory was contemplated in kilobytes. But the 1980s were a long time ago.

I think of it as good manners.

unit sub MAIN ( $number = 5 ) ;

say (2..$number).grep({ !/1/ })
                .elems;

---

episode two:
“A Clean Sweep”

---

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

theory

Well let me say I thought at first we’d been tasked with actually making a minesweeper game. I mean, on thinking it through it wouldn’t be particularly difficult or anything; just take coordinate coded input and reprint the updated map. Or even provide terminal blanking tricks to make a proper ascii gui of sorts.

Really the hard part would be thinking up and implementing all the fiddly details that go into an effort like that more than the core logic.

I get the feeling someone will go the extra distance and do it; we may more likely get several versions to play arond with.

Me, on the other hand I think I’ll stick with the request as written. Perhaps when I’m done rooting through all the other rabbit holes permeating my life this week I’ll have time to come back and fancy it up.

Not likely though. I wouldn’t wait up.

So we have a request for the minesweeper interface map, rather than the game. This map is an important and necessary subtask to creating the game, for determining the information revealed to the user with every move made. The ultimate goal of the game is to reveal the entirely of this map, position by position, without ever testing a square with a mine in it.

What we start with is the secret map of the minefield, which the player never directly sees. The player moves to a coordinate position, and the number of mines surrounding that square is revealed. By combining this information from a number of directions inferences can be made and the locations, in theory, of the individual mines can then be determined.

What we’re being tasked to construct here is the map of the neighboring mine counts for each square that isn’t a mine itself. If the player picks one of those squares — the ones containing a mine — the mine goes off, terrible things happen and the game is over, so as far as proximity data goes we need never compute those positions.

implementation

We could go about this in one of two ways. We could either loop through the array, and for each cell scan the surrounding 8 cells, augmenting a count to each if the current cell contains a mine; or alternately loop through each cell and search the surrounding area for active mines and count them up all at once that way. Either way involves a double iteration through the matrix, followed by another loop to encircle the candidate. However in the first strategy, if a cell does not contain a mine we can skip the surrounding scan, so we’ll use that one. When implementing the game we only need to precompute this step once so we needn’t worry too much about time complexity, but that doesn’t mean we should ignore it either.

Presenting the coordinate deltas to the surrounding cells as a list of arrays rather than generating them on the fly makes for less redundant processing, and we have no need to skip the no-op step of delta [0,0] as it’s never addressed.

In an actual game we’d just probably just roll this neighbor-data step into the map-generation phase, unless perhaps we wanted to present just the mines for display design, say at the end or when the player lost or such. But we won’t bother with that; we’re not actually designing a game, so let’s stick to our guns and not get caught up in the fiddly bits. In any case a simple minefield map generator is included, with parameters for height, width and % probability of a cell being a mine.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


my $mat = generate_map(10,10,30);
            
my @mat = map { [ map { $_ eq '*' ? 0 : $_ } $_->@* ] } $mat->@* ;
my @deltas = (  [-1,-1], [-1,0 ], [-1, 1], 
                [ 0,-1],          [ 0,1 ], 
                [ 1,-1], [ 1, 0], [ 1, 1]  );

for my $i ( 0..$#mat ) {
    for my $j ( 0..$mat[0]->$#* ) {
        next unless $mat->[$i][$j] eq 'x';
        for my $d ( @deltas ) {
            my $r = $i + $d->[0];
            my $c = $j + $d->[1];
            if ( @mat > $r >= 0 and $mat[0]->@* > $c >= 0 ) {
                next if $mat[$r][$c] eq 'x';
                $mat[$r][$c]++;
            }
        }
    }
}
say "\nInput:\n";
say "$_->@*" for $mat->@*;

say "\nOutput:\n";
say "$_->@*" for @mat;


sub generate_map ($r, $c, $pct) {
## height in rows, width in columns, % chance of cell being a mine
    my $mat = [];
    for my $row ( 0..$r ) {
        for my $col ( 0.. $c ) {
            $mat->[$row][$col] =  rand(100)-$pct < 0 
                                    ? 'x'
                                    : '*' ;
        }
    }
    return $mat;
}

The results, on a random 10×10 playing field:

Input:

* x x * x x x * * x x
* * * * x * * x * * *
* * * * * * x * * x *
x * * * * * x * * * *
* * * * * x x * * * *
* x * x * x * x * x *
x * * x * * * x * x *
x * * * * x x * * * *
* * * x x * * x * * *
* x * * * * x * * * x
* * * x x * x * * * *

Output:

1 x x 3 x x x 2 2 x x
1 2 2 3 x 5 4 x 3 3 3
1 1 0 1 1 3 x 3 2 x 1
x 1 0 0 1 4 x 3 1 1 1
2 2 2 1 3 x x 3 2 1 1
2 x 3 x 4 x 5 x 4 x 2
x 3 3 x 4 3 5 x 4 x 2
x 2 2 3 4 x x 3 3 1 1
2 2 2 x x 4 4 x 1 1 1
1 x 3 4 4 4 x 3 1 1 x
1 1 2 x x 3 x 2 0 1 1

Raku Solution

In Raku I went ahead and computed the coordinate deltas, using the cross-product operator, a grep, and a junction. In all honesty we were presumably better off inlining the eight pairs, but this was a fun exercise. I like using Raku’s cross-product operator, which we use again to give us the iterators to twice traverse the matrix, once in the main logic and also in the map generating subroutine.

To place the mines on the map we use a very literal way of selection, first constructing an intermediate array with 100 values: the percentage given in Xs, and the rest in asterisks. We can then use .roll to pick a value from this at random. Is it the best way? Maybe. I suppose we could construct something with a ternary operator and rand, but that would be kinda boring.

unit sub MAIN () ;


my $m = 3;
my $n = 3;
my $pct = 30;

my @mat = generate_map( $m, $n, $pct );
say "$_" for @mat;

my @map = @mat.map({ $_.map({ $_ eq '*' ?? 0 !! $_ }).Array });
say "$_" for @map;

my @range = -1, 0, 1;
my @deltas = (@range X @range).grep({all( $_ ) != 0});

sub generate_map ($m, $n, $pct) {
## height in rows, width in columns, % chance of cell being a mine
    my @mat;
    my @list = |('x' xx $pct), |('*' xx 100 - $pct);
    for (^$m X ^$n) -> ($r, $c) {
        @mat[$r][$c] = @list.roll;
    }
    return @mat;
}

for ^(@map.elems) X ^(@map[0].elems) -> ($i, $j) {
    next unless @map[$i][$j] eq 'x';
    for @deltas -> $d {
            my $r = $i + $d[0];
            my $c = $j + $d[1];
            if ( @map.elems > $r >= 0 and @map[0].elems > $c >= 0 ) {
                next if @map[$r][$c] eq 'x';
                @map[$r][$c] += 1;
            }
    }

}

say "$_" for @map;