Lonely X


So… I entered into the Perl Weekly Challenge, I’ll describe some from my solution to Challenge 077.

After reading so much about it in the wonderful Perl Weekly, I decided to chip off some more of my scarce spare time to give it a try. Let’s see how it goes.

Challenge 077, much like the others I looked at, proposes two different problems. I’ll start with task #2 because the first one, while initially simpler, had a change in the specifications (which, I fear, was my fault 🤭) that proved to be a bit trickier than I anticipated. Anyway, we’ll take a look at it in due time.

Task #2 is similar to a lot of exercises that I did when studying computer science fundamentals (or another course on C whose name I forgot), so it gave me that tender sensation of when things were simpler and people smiled more… just to remember that life was not that simple at the time and people likely smiled just the same as today. But I’m digressing.

One thing that I find useful in addressing this kind of problems is to avoid having to deal with the boundaries, i.e. avoid putting a lot of special conditions just to make sure I’m not messing up with the boundary of the map I’m looking at. To this extent, the excellent Mohammad S Anwar already provided us with “boundary-like” characters for east and west limits, so it’s just a matter of adding some more for north and south.

The full solution is here: challenge-077/polettix/perl/ch-2.pl. It’s (maybe too) heavily commented, so we’ll just take a quick look at it here.

The main loop over the map is in sub count_solitaries, here’s a stripped down version (i.e. without comments):

 1 sub count_solitaries {
 2    my ($fh) = @_;
 3    my @lines;
 4    my @counts;
 5    my @zeros;
 6    my $n_solitaries = 0;
 8    while (<$fh>) {
 9       my @line = split m{\s+}mxs ;
11       if (! @zeros) {
12          @zeros = (0) x @line;
13          @counts = [@zeros];
14          @lines  = [('O') x @line];
15       }
17       push @counts, [@zeros];
18       push @lines,  \@line;
20       $n_solitaries += _count_solitaries(\@lines, \@counts);
21       shift @lines;
22       shift @counts;
23    }
25    return $n_solitaries + _count_solitaries(\@lines, \@counts);
26 }

Sweeping through the input (as a filehandle) should require us to avoid keeping too much stuff around. I mean, after we have seen input line 3, do we really need to keep lines number 1 and 2 around? I don’t think so!

Hence, the idea is to make the most out of the line we read in input, using it to complete our knowledge about the previous line, as well as put additional knowledge on the current line. We’ll then keep it around for when the next line will come in, if any.

To this extent:

  • @lines (line 3) keeps track of the previous and the current line (respectively in slots 0 and 1);
  • @counts (line 4) keeps track of the count of surrounding items for a specific slot;

The initialization injects a fake line that is all Os, so that will not be counted. Array @zeros is then reused at each iteration to initialize the counts for the current line.

Lines 20 and 21 get rid of the oldest line and prepare for the next iterator.

The actual counting happens in the workhorse sub _count_solitaries, which does a sweep through the characters in the line and will be described shortly. It is called during the loop and in line 25, to account for the last line (we avoid injecting a true “after the last line” here).

This is the workhorse sub:

 1 sub _count_solitaries {
 2    my ($lines, $counts) = @_;
 4    if (@$lines > 1) {
 5       for my $i (1 .. $#{$lines->[1]} - 1) {
 6          for my $j ($i - 1 .. $i + 1) {
 7             $counts->[1][$j]++ if $lines->[0][$i] eq 'X';
 8             if ($lines->[1][$i] eq 'X') {
 9                $counts->[0][$j]++;
10                $counts->[1][$j]++; # self-counting is OK
11             }
12          }
13       }
14    }
16    return scalar grep {
17       $lines->[0][$_] eq 'X' &&  # a solitaire is a 'X' character...
18       $counts->[0][$_] == 1;     # with a 1 count (i.e. only itself)
19    } 1 .. $#{$lines->[0]} - 1;
20 }

Lines 5 to 13 perform a sweep through the two lines to update the counts in the previous and the current counts. This sweeping is needed only for the central lines, and accounts for easily counting the last input line without injecting a fake final lines with all Os.

The counting happens for elements strictly inside the input (so we start $i from 1 and end one before the last) and accounts for the element on its left, position, and right. Hence, we’re including the specific location as a neighbor for simplicity, and we will have to remember that being a solitaire means that the count is exactly 1.

Lines 16 through 19 perform the actual counting of solitairs in the previous line (so we’re looking at index 0 in both array references). The condition for a solitaire is that it’s a location with an X (line 17) and that its count is 1 (because we’re counting itself too, line 18).

We’re using the nice side effect of grep to return the count of elements matching the condition when run in scalar context, which is the same as the number of solitaire elements in the line (line 16, note forcing the scalar context).

I guess it’s all!

Comments? Octodon, , GitHub, Reddit, or drop me a line!