Lonely X — The Weekly Challenge 77, Task 2

The second task of this week’s challenge sounds like this:

So, there’s a matrix, and you need to find the Xs which are surrounded by Os. Let me illustrate a couple of examples:

My solution simplifies the task in two aspects. First, I assume that the matrix is square (as in the demonstrated examples). Second, I do not print 0 if nothing found (as many Unix command-line tools would do). Nevertheless, I am striving for showing the code.

my @matrix =
    < O O X >,
    < X O O >,
    < X O O >; # square matrix

my @neighbours = ([X] (-1, 0, 1) xx 2).grep(*.all != 0);

for ^@matrix X ^@matrix -> @coord {
    next if @matrix[@coord[0]][@coord[1]] eq 'O';

    @coord.put if all((@neighbours.map(* <<+>> @coord)).grep(0 <= *.all <= @matrix.end).map({        
        @matrix[$_[0]][$_[1]] eq 'O';
    }));
}

I believe I wanted to use as many non-standard things as I could, and I am sure there is still room to pack the loops or the checks to even more of similar constructions. On the other hand, I think the result is mostly worth examining rather than entering the daily programming practice.

OK, let’s see how this program works.

The @matrix is an array that contains three lists. Use the dd routine to see the types:

dd @matrix;
# Array @matrix = [("O", "O", "X"), ("X", "O", "O"), ("X", "O", "O")]

dd @matrix[0];
# List @matrix = $("O", "O", "X")

Then, I want to make a plan to visit all the neighbours. On an infinite board, there are nine neighbours for every cell. So, I am making a map of movements:

my @neighbours = ([X] (-1, 0, 1) xx 2).grep(*.all != 0);

To visit the neighbours, we need to change one or both of the x and y coordinates to +1 or −1. The construct [X] (-1, 0, 1) xx 2 gives us the following directions:

((-1 -1) (-1 0) (-1 1) (0 -1) (0 0) (0 1) (1 -1) (1 0) (1 1))

To exclude the current cell (0, 0), a restriction is added: .grep(*.all != 0).

OK, next, I am visiting all the cells of the original matrix. The loop scans all the cells as ^@matrix X ^@matrix, which for the sample case means ^3 X ^3, which is:

((0 0) (0 1) (0 2) (1 0) (1 1) (1 2) (2 0) (2 1) (2 2))

On each iteration, I am taking a pair of coordinates from this sequence in the @coord array and immediately skip the loop body if the current cell does not keep X:

next if @matrix[@coord[0]][@coord[1]] eq 'O';

Then, from a given position @coord, let’s visit the neighbours. So, we need to compute their coordinates too:

@neighbours.map(* <<+>> @coord)

This construction produces the coordinates of the neighbouring cells. For example, for the central position (1, 1), the result is the following:

((0 0) (0 1) (0 2) (1 0) (1 2) (2 0) (2 1) (2 2))

For the cells on the border or in the corners, the coordinates of the neighbours will be either negative or bigger than the size of the matrix. So, let’s filter them out: .grep(0 <= *.all <= @matrix.end).

So, we now have a list of all existing neighbours, so let’s see if they contain 0:

.map({        
    @matrix[$_[0]][$_[1]] eq 'O';
}));

Almost there. Now, surround what we have with all(. . .) and print the result only if all of the neighbours pass the condition: @coord.put if . . ..

And that’s it. Run the program with different matrices and see what it prints. For the examples displayed on the image in the beginning of this post, the program prints:

$ raku ch-2.raku 
0 2

$ raku ch-2.raku 
0 2
2 3

* * *

Update: Explore my other solutions in C++, XSLT, JavaScript, Python, and Perl in the next post.

* * *

→ GitHub repository
→ Navigation to the Raku challenges post series