Day 3′s first problem asks us to find numbers that are horizontally, vertically, or diagonally adjacent to symbols in input like this (with dots being blank space):
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
As the sample logic states, in the sample input, only 114 and 58 aren’t adjacent to any symbols.
I thought for a while about a couple of ways to do this and settled on a flood fill. This was an incorrect choice that happened to work on my particular input but is not a proper solution, so I got unreasonably lucky.
Flood filling is an algorithm, commonly used in computer paint programs (or at least it used to be), for filling a region of cells bounded by a closed curve of some marker condition with a new condition — in other words, filling the inside of a shape you just drew.
I use it here like this: Imagine covering that input grid with an opaque piece of paper. Punch holes in it where the symbols are and put it back on top of the grid; all you can see are symbols. Wiggle your stencil around and get a peek at what surrounds the symbols — anywhere you find a digit adjacent to a hole, punch out the stencil above that digit also and put it back over the grid. Then wiggle some more looking for digits adjacent to already-uncovered digits and punch holes over those. Keep repeating until you don’t see any more adjacent digits and don’t punch any more holes; then you’re done.
This will find digits that are adjacent to symbols and then “uncover” the rest of the numbers of which those digits are members.
It will also incorrectly find digits vertically and diagonally adjacent to other digits, even when the newly-found digits aren’t adjacent to a symbol:
.....1..
...234..
567...*.
........
Here, 1 and 567 shouldn’t be selected, but my flood fill will include them. That’s wrong; and that’s how my program works; and I find myself very surprised that the actual input didn’t contain any number placements that would trigger this error.
So … let’s talk about how I wrote this; and then in part 2 you can see that (for other reasons) I had to change my approach to something that would have been more appropriate here.
Subroutines
sub prime;
sub iterate;
sub isdigit; # missing from POSIX on my system ?!
I’m going to use some subroutines in this program. In Perl, you can call a subroutine without having defined it first by using the syntax &iterate; or you can define it first and use the syntax iterate. Today I felt like having a reminder of my list of subroutines and using the latter syntax, so I define them at the top.
The third subroutine definition bears some explanation. I’m going to want a quick way to check whether a character is a digit, and normally one would write:
use POSIX qw(isdigit);
if (isdigit($var)) { ... }
but the MacBook on which I wrote today’s programs says
"isdigit" is not exported by the POSIX module
???! So I made my own:
sub isdigit {
return $_[0] =~ /^\d$/;
}
Global Arrays
my (@input, @dst);
I’m going to store the input in a two-dimensional array and I need a second two-dimensional array for the flood-filled copy. I declare them here as global variables. Global variables aren’t normally a great programming practice but here I’m going to share them between multiple subroutines; and because that’s all these subroutines are doing, there’s no point in passing the arrays as parameters to the subs. Think of these as lexically-scoped variables shared among functions in foolib.c that aren’t defined-extern in foolib.h so they’re not visible from main.c, only here I haven’t bothered to make a separate foolib.c .
my @neighbor = ( [-1, -1], [0, -1], [1, -1],
[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0] );
I make a list of the (xoffset, yoffset) coordinates for the eight neighbors of a cell. @neighbor is an array of arrays — technically an array of array references, but in Perl we don’t talk about that as much as we have to in C(++). The ( ) presents a list to initialize @neighbor and each [ ] within it creates a list and returns its reference to become a member of @neighbor. Later we can access these as $neighbor[3][0] for the x offset and $neighbor[3][1] for the y offset.
Read the Input
# Slurp the entire input into a two-dimensional array.
chomp, push(@input, [ split(//) ]) while <>;
my $h = scalar @input; my $w = scalar @{$input[0]};
print "$w x $h\n\n";
Perl offers syntax variants to write very compact code that’s easily read by the fluent and which contributes to its reputation for unintelligibility among everyone else.
... while condition;
is equivalent to
while (condition) { ... }
– it executes the statement or block as long as the condition is true. The condition <>, which I use in every AoC program, is a built-in that reads the next line of input, stashes it in the special variable $_ that’s the default for operators that don’t specify a variable on which to operate, and returns true until eof and then returns false. So this will loop through the input, stashing each line in $_.
Each line of input has a newline at the end and split will blithely treat that like any other character, building it into my array. I don’t want that; so chomp discards any line-separator present in a string and doesn’t discard anything if no line separator is present.
Then split the line into separate characters (split(//) splits between characters; and without a parameter for which string to split, it defaults to splitting the current line of input, $_); encapsulate that as a list/array and return the array reference; and push that onto the end of the list of rows of input. The comma operator allows two (or more) operations in sequence and has a very poor order of precedence compared to arithmetic, logical, and list operators but higher than loop commands; so it allows me to chomp and push still using the one-line loop syntax.
Having read the entire input file into an array in one line of code, grab the height (number of rows) and width (number of elements of the first [zeroeth] row), then print those out as a reassurance that the program is doing something sane. scalar causes an arbitrary data type to be interpreted in scalar context and an array in scalar context returns the number of elements in the array. And an instance where we do have to worry about array references: $input[0] is an array ref, not an array; so we must cast it (rather than dereference as in C) to an array @{$arrayref} in order to apply the scalar cast to get its length.
Subroutine Calls
prime;
iterate;
Call the previously-defined subroutines to prime my flood fill and iterate my flood fill, whatever those may entail.
Calculate the Result
my $sum;
foreach my $row (@dst) {
$sum += $_ foreach join("", @{$row}) =~ /(\d+)/g;
}
print "sum is $sum\n";
For every row of the @dst destination array; and within that, for every something or other, add it to $sum, then print that.
From the inside out, $row is an array ref, not an array, so @{$row} cast it as an array. Join the elements of that array into a string with no field separators added. To that string, apply a regular expression that (\d+) looks for and saves strings of digits, /g as many of them as there may be in the string (regex modifier mnemonic: look again). Iterate through all of those saved results and for each one of them, add the intrinsic loop variable $_ to the sum.
Prime the Stencil
# Copy everything except digits from input array to destination array,
# leaving dots in all blank positions of both arrays.
sub prime() {
foreach my $row (0 .. $h - 1) {
foreach my $col (0 .. $w - 1) {
my $in = $input[$row][$col];
$dst[$row][$col] = isdigit($in) ? "." : $in;
$input[$row][$col] = "." unless isdigit($in);
}
}
}
I’m retaining the puzzle author’s selection of using dot to indicate a blank. For my flood fill, I’m going to destructively scan @input and move matching parts of it to @dst; so that starts here by “creating the initial stencil” — priming the initial contents of @dst.
Loop through all the cells of @input For each cell, if it’s a digit, don’t copy/move it to @dst; populate with a dot (blank space) instead. For any other character, move it over, replacing it in @input with a dot (which might be what was there to begin with).
Now @dst is primed with all of the symbols and nothing else.
Iterate Flood Filling
# Move digits from input array to destination array that are adjacent
# to anything in destination array until nothing more is moving.
sub iterate() {
my $changing;
do {
$changing = 0;
Recall that we’re going to keep “wiggling the stencil” looking for adjacent digits until we don’t find any more. I’m tracking that in the variable $changing, which needs to be defined outside the loop so it can be checked in the loop condition, and cleared at the beginning of each iteration of the loop. This outer loop is multiple iterations of “wiggling the stencil.”
foreach my $row (0 .. $h - 1) {
cell: foreach my $col (0 .. $w - 1) {
my $in = $input[$row][$col];
next unless isdigit($in);
Each time we wiggle the stencil, we need to look at whether any digits are adjacent to “holes” in the stencil. We can do this two ways: look at every digit in the grid and see whether it’s adjacent to a hole or look at every hole in the stencil and see whether it has digits adjacent to it. I chose the former.
So loop through the grid and skip on to the next cell if we’re not looking at a digit.
foreach my $n (@neighbor) {
my $rtst = $row + ${$n}[1];
next if $rtst < 0 || $rtst >= $h;
my $ctst = $col + ${$n}[0];
next if $ctst < 0 || $ctst >= $w;
Having found a digit in @input that we haven’t determined to be adjacent to a “hole in our template” and moved over to @dst yet, look at all of the cells surrounding our digit. Loop through the list of (xoffset, yoffset) pairs for all eight neighbor adjacencies; for each, add the offsets to the current coordinates to get the coordinates ($ctst, $rtst) of the @dst stencil cell that we want to test/examine. If the offsets take us out of bounds of the grid, skip this neighbor position and move on to the next.
if ($dst[$rtst][$ctst] ne ".") { # have neighbor
$dst[$row][$col] = $in;
$input[$row][$col] = ".";
++ $changing;
next cell;
}
For a neighbor position that’s within the grid, recall that the only things left behind in @input are digits that we don’t yet know are adjacent to symbols or other digits. So if a neighbor position is non-empty, then we’re interested in it and we want to move it from @input to @dst. Set the cell of @dst to that value; clear that cell of @input; note that we’ve experienced a change on this iteration of wiggling the stencil; and stop examining other neighbors of this digit because we’ve already vetted and moved it.
} # if neighbor
} # neighbor
} # col
} # row
} while $changing;
Keep looping through neighbors of the current maybe-digit cell, and columns of the row, and rows of @input, and iterations of wiggling the stencil, as long as we’re still finding new digits to move over.
Reminder That This Is Wrong; How to Fix
Again, this code picks up digits that it shouldn’t, due to inappropriate use of flood filling, specifically digits vertically and diagonally adjacent to other digits rather than symbols.
This could be remedied within a flood fill algorithm by renaming @neighbor to @symbolneighbor and then making a shorter @digitneighbor that only contains left and right offsets ( [-1, 0], [1, 0]). Then either:
- Retain the approach of scanning cells of
@inputfor remaining digits; scan their@symbolneighborneighbors for symbols; and scan their@digitneighborneighbors for digits. - Change to scanning
@dstfor populated cells; scan the@symbolneighborneighbors of symbols and the@digitneighborneighbors of digits in@dstfor digits in@input.
The latter strikes me as cleaner and more intelligible.
Full Program
#!/usr/bin/perl
use warnings;
use strict;
sub prime;
sub iterate;
sub isdigit; # missing from POSIX on my system ?!
my (@input, @dst);
my @neighbor = ( [-1, -1], [0, -1], [1, -1],
[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0] );
# Slurp the entire input into a two-dimensional array.
chomp, push(@input, [ split(//, $_) ]) while <>;
my $h = scalar @input; my $w = scalar @{$input[0]};
print "$w x $h\n\n";
prime;
iterate;
my $sum;
foreach my $row (@dst) {
$sum += $_ foreach join("", @{$row}) =~ /(\d+)/g;
}
print "sum is $sum\n";
# Copy everything except digits from input array to destination array,
# leaving dots in all blank positions of both arrays.
sub prime() {
foreach my $row (0 .. $h - 1) {
foreach my $col (0 .. $w - 1) {
my $in = $input[$row][$col];
$dst[$row][$col] = isdigit($in) ? "." : $in;
$input[$row][$col] = "." unless isdigit($in);
}
}
}
# Move digits from input array to destination array that are adjacent
# to anything in destination array until nothing more is moving.
sub iterate() {
my $changing;
do {
$changing = 0;
foreach my $row (0 .. $h - 1) {
cell: foreach my $col (0 .. $w - 1) {
my $in = $input[$row][$col];
next unless isdigit($in);
foreach my $n (@neighbor) {
my $rtst = $row + ${$n}[1];
next if $rtst < 0 || $rtst >= $h;
my $ctst = $col + ${$n}[0];
next if $ctst < 0 || $ctst >= $w;
if ($dst[$rtst][$ctst] ne ".") { # have neighbor
$dst[$row][$col] = $in;
$input[$row][$col] = ".";
++ $changing;
next cell;
} # if neighbor
} # neighbor
} # col
} # row
} while $changing;
}
sub isdigit {
return $_[0] =~ /^\d$/;
}