Day 3 part 2 asks us to find only numbers adjacent to * characters, and only when exactly two numbers are adjacent to * characters.
I could trivially update my flood fill to prime the stencil only with * characters and then it would find only numbers adjacent to them; but I’d still have to write new code to count the quantity of numbers adjacent to * characters; and by the time I’ve done that, I might as well use it in the main loop also.
Because
..123...
...*....
456.....
that star has a whole lot of digits adjacent to it but only two numbers.
New approach: Look for stars; find adjacent digits; immediately find the full string of digits and cache it; flag every position filled by those digits so it’s not picked up again in this particular scan for neighbors; count the cache length.
I’m no longer using subroutines prime and iterate nor a separate @dst array. The code to read the input is unchanged from part 1.
Debugging Output
my $debug = 0;
...
if ($debug) { print join("", @{$_}), "\n" foreach @input; print "\n"; }
I’ve added debugging, which perhaps Perl has developed a more elegant or idiomatic way to do since I learned it sometime around 1992. If I’ve turned on debugging, then dump the input back out by iterating through each line of the array, joining all of the characters of the line, and printing that, plus an extra blank line. This is handy during testing because I haven’t memorized the input and today I’m working on a single laptop screen.
Loop Through Cells
my $sum;
foreach my $row (0 .. $h - 1) {
foreach my $col (0 .. $w - 1) {
next unless $input[$row][$col] eq "*";
print "($row, $col)\n" if $debug;
Loop through the rows of the grid and the columns of each row. If the cell doesn’t contain a *, move on. If debugging, print the coordinates of the current cell (after finding that it has a *).
Loop Through Neighbors
my (@neighboringnums, %seen);
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;
Declare a list to hold neighboring numbers that we find and a hash to flag cells containing digits that are part of numbers we’ve already got and shan’t examine again.
As before, loop through the coordinates of neighbor offsets, ensuring that they don’t fall outside the grid.
next if $seen{$rtst}{$ctst};
next unless isdigit($input[$rtst][$ctst]);
If we’ve flagged this neighbor cell as part of a number that we’ve already seen adjacent to this *, then skip it.
If it’s not a digit, then skip it.
Extract the Number
# Found an adjoining digit that we haven't seen yet.
# Extract the whole number. First, find its left edge.
my $nx = $ctst;
-- $nx while $nx > 0 && isdigit($input[$rtst][$nx - 1]);
print "\t($nx, $col)\n" if $debug;
($ctst, $rtst) are the coordinates of a newly-discovered digit adjacent to a *. Get the whole number that it’s part of.
Set the number’s x coordinate $nx to the x coordinate of the digit we just found. Now decrement that position (move left) as long as we’re not passing the left edge of the array and as long as the cell to our left contains a digit.
Once we get there, if debugging, print these coordinates of the left edge of this number (string of digits), one tab indented.
# Now build the number and mark it seen by this gear.
my $num;
do {
$num .= $input[$rtst][$nx];
++ $seen{$rtst}{$nx};
} while $nx < $w - 1 && isdigit($input[$rtst][++$nx]);
print "\t\t[$num]\n" if $debug;
push @neighboringnums, $num;
We're at the beginning of a string of one or more digits, at least one of which is adjacent to a *. Accumulate those digits into the string $num and mark their positions not to be examined again while searching neighbors of this *.
Append the current digit to $num. Mark this position as already used ... and although I narrate here in (x, y) coordinates, maintain the (row, column) convention used by @input's indices even in the %seen hash. Keep appending cells as long as we're not past the right edge of the grid and the next character to the right is another digit.
If debugging, print the resulting number string, two tabs indented.
Push that number on the list of numbers (not just digits) found neighboring this *.
Two Neighboring Numbers?
$sum += $neighboringnums[0] * $neighboringnums[1] if
@neighboringnums == 2;
If we found two neighboring numbers, add their product to our running sum.
Here, the array-to-scalar context of @neighboringnums is caused by the scalar comparison to the scalar 2 and scalar context needn't be specified explicitly. It's idiomatic in Perl only to specify context explicitly when the array is in an array-or-scalar context (argument to a multi-argument function like print) or when the code is so dense that the meaning would be unclear.
Coulda Done Part 1 This Way
Obviously. Search for neighbors of symbols and extract full numbers immediately. Move %seen outside the outermost cell loop so that each number only gets picked up once.
Full Program
#!/usr/bin/perl
use warnings;
use strict;
sub isdigit; # missing from POSIX on my system ?!
my @input;
my @neighbor = ( [-1, -1], [0, -1], [1, -1],
[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0] );
my $debug = 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";
if ($debug) { print join("", @{$_}), "\n" foreach @input; print "\n"; }
my $sum;
foreach my $row (0 .. $h - 1) {
foreach my $col (0 .. $w - 1) {
next unless $input[$row][$col] eq "*";
print "($row, $col)\n" if $debug;
my (@neighboringnums, %seen);
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;
next if $seen{$rtst}{$ctst};
next unless isdigit($input[$rtst][$ctst]);
# Found an adjoining digit that we haven't seen yet.
# Extract the whole number. First, find its left edge.
my $nx = $ctst;
-- $nx while $nx > 0 && isdigit($input[$rtst][$nx - 1]);
print "\t($nx, $col)\n" if $debug;
# Now build the number and mark it seen by this gear.
my $num;
do {
$num .= $input[$rtst][$nx];
++ $seen{$rtst}{$nx};
} while $nx < $w - 1 && isdigit($input[$rtst][++$nx]);
print "\t\t[$num]\n" if $debug;
push @neighboringnums, $num;
} # neighbor
$sum += $neighboringnums[0] * $neighboringnums[1] if
@neighboringnums == 2;
} # col
} # row
print "sum is $sum\n";
sub isdigit {
return $_[0] =~ /^\d$/;
}