Day 5 part 2 reveals that the seed list does not actually denote individual seed values; it is pairs of numbers denoting ranges of seeds. Run each range through the translations and find the lowest value in any resulting range.
After the way I wrote the first program, this made me feel like Obi-Wan just told me to go home and rethink my life. I could enumerate each range of seeds and run them all through the translations … for certain values of “could” that include more processing power, electricity, and time than I have remaining in my years on this planet.
It was obvious that I was going to have to treat ranges as data structures, intersect them with ranges in translation rules, translate them accordingly, and be prepared to split seed ranges that overlapped translation ranges to apply the translation to only a portion of the input range. Afflicted with a serious case of I don’t wanna, I pretended to be too busy with other things to get around to writing this yesterday.
But early this morning I cured my case of I don’t wanna in the way I’ve learned to cure any case related to programming: Write the utilitarian loops that do the boring work of the program; and once they’re done, there’s so little of the program left to write that I’m ready to go ahead and do it.
20231207 edit: I omitted handling one way that intervals can intersect and it was accidental that my program handles that case correctly. More below.
Read the Seed Ranges
In part 1, I iterated through seeds, applying consecutive translations to each. For part 2, I iterate through mapping tables, applying each to all seed ranges / translated seed ranges.
$_ = <>;
chomp;
my @ranges = /(\d+)/g if /^seeds/;
So start by grabbing all of the seed ranges. Don’t bother parsing them into (start, length) pairs yet.
Read a Translation Map
# Loop through mapping rules, applying each to our list of seed ranges.
while (<>) {
# Parse the map, saving destination, start, length, end, and offset.
my @map;
foreach (grep { ! /map/ } split /\n/) {
my @n = split /\s+/;
push @map, { D => $n[0], S => $n[1], L => $n[2],
E => $n[1] + $n[2] - 1, O => $n[0] - $n[1] };
}
Each remaining input record is a translation map. I totes forgot to chomp here and I suspect that split on whitespace (A) matches newlines as whitespace and (B) discards empty trailing fields, but don’t quote me on that without you test it yourself first.
So … split the paragraph into individual lines. Discard the line that has map in it. For the remaining lines, split into whitespace-delimited fields. Create an anonymous hash and push its reference onto the array of this map. I went all out here and precomputed every value I thought I might want later, stuffing them all into the hash: Dest, Source, and Length were provided; and I also calculated End and Offset here because I was going to use them multiple times later and because I was more likely to write an off-by-one error later than when I was paying attention here.
Checking Current Range for Translation Intersection
# Apply this transformation to our list of number ranges,
# building a list of resulting number ranges.
my @newranges;
range: while (@ranges) {
my $s = shift @ranges; my $l = shift @ranges; my $e = $s + $l - 1;
For this set of map rules, loop through all of our current set of ranges of interest. Within each, break out the (start, length) pair and for convenience, also calculate the end of the range.
# Check whether the current range intersects any map range.
maprule: foreach my $href (@map) {
# If this range doesn't intersect this map rule, try the next.
next maprule if $e < $$href{S} || $$href{E} < $s;
Loop through the mapping rules. For each, first check whether the current range of interest doesn't even intersect with the range of this map rule -- the end of the range of interest is less than the start of the map range, or the end of the map range is less than the start of the range of interest. If no intersection with this map rule, go on and try the next.
# If this range is completely enclosed in this map rule, apply.
if ($$href{S} <= $s && $e <= $$href{E}) {
$s += $$href{O};
push(@newranges, $s, $l);
next range;
}
Maybe this range of interest is a subset of the range of the map rule? If so, apply the map rule's translation (offset) to the start of the range, then push the translated (start, length) pair onto the list of new ranges to be used in the next mapping, and move on to the next range of interest.
# This range intersects but is not fully enclosed in
# this map rule. Split, apply the transformation to the
# intersection, and push the leftover back onto this pass.
if ($s < $$href{S}) { # overlaps start of map rule
my $s1 = $s;
my $e1 = $$href{S} - 1;
my $l1 = $e1 - $s1 + 1;
unshift(@ranges, $s1, $l1);
my $s2 = $$href{S};
my $e2 = $e;
my $l2 = $e2 - $s2 + 1;
push(@newranges, $s2 + $$href{O}, $l2);
next range;
If we've fallen through the logic to this point, then the range of interest does overlaps this mapping rule's range (and is not simply a subset). Does the range of interest overlap the beginning of the map rule (or the end)?
Either way, break this range of interest into two ranges of interest. In the case of overlapping the beginning of the map range, the first new range of interest is passed back into the list of ranges for the current round (because another map rule might apply to it) with no translation and the second is passed forward for the next round with this translation rule's offset applied. Clearly all of this could have been written in a single line; but breaking it out into variables makes it very clear what I'm doing, is easier for me to avoid more off-by-one errors, costs me next to nothing, and is probably even optimized away.
unshift pushes values onto the beginning of a list (array); push pushes values onto the end. I'm putting the unprocessed leftovers from this cut back onto the beginning of the current list and the translated range from this cut onto the end of next time's list.
And then move on to the next range of interest.
The code for a range of interest that overlaps the end of this mapping rule's range is very similar.
20231207 edit: As I was drafting notes about intervals in preparation for programming, I included the case where a map rule range was completely enclosed within a range of interest, splitting the range of interest into three intervals; but I forgot about that when coding.
My code accidentally handles it correctly because the case for a range of interest overlapping the start of a map range splits at the beginning of the map range and pushes the latter part back into the current queue. When it comes up again, it gets handled by the code for overlapping the end of a map rule.
Very lucky and very sloppy.
# No intersection, so current range is untouched.
push(@newranges, $s, $l);
}
# Save the resulting list of ranges for next time.
@ranges = @newranges;
If we fall through the loop of testing all of the mapping rules without having matched one and nexted on to the next range of interest, then this range of interest has no translation in this map and is preserved intact for the next round.
Find the Minimum Translated Value
# Find the minimum range start after all processing.
my $min;
while (@ranges) {
my $s = shift @ranges; shift @ranges;
$min = $s if !defined $min || $s < $min;
}
In my approach to part 1, the minimum was captured as a running value along the way; but in part 2, I need to go back and find it myself.
@ranges is (still) an unstructured list of (start, length) pairs and I don't remember if there's a cool-kid way to select alternating values from a list; so I iterate through the list, looking for the minimum range start (which will be the lowest value in any range).
Full Program
#!/usr/bin/perl
use warnings;
use strict;
# Get seed list; trust that it's first.
$/ = "\n\n";
$_ = <>;
chomp;
my @ranges = /(\d+)/g if /^seeds/;
# Loop through mapping rules, applying each to our list of seed ranges.
while (<>) {
# Parse the map, saving destination, start, length, end, and offset.
my @map;
foreach (grep { ! /map/ } split /\n/) {
my @n = split /\s+/;
push @map, { D => $n[0], S => $n[1], L => $n[2],
E => $n[1] + $n[2] - 1, O => $n[0] - $n[1] };
}
# Apply this transformation to our list of number ranges,
# building a list of resulting number ranges.
my @newranges;
range: while (@ranges) {
my $s = shift @ranges; my $l = shift @ranges; my $e = $s + $l - 1;
# Check whether the current range intersects any map range.
maprule: foreach my $href (@map) {
# If this range doesn't intersect this map rule, try the next.
next maprule if $e < $$href{S} || $$href{E} < $s;
# If this range is completely enclosed in this map rule, apply.
if ($$href{S} <= $s && $e <= $$href{E}) {
$s += $$href{O};
push(@newranges, $s, $l);
next range;
}
# This range intersects but is not fully enclosed in
# this map rule. Split, apply the transformation to the
# intersection, and push the leftover back onto this pass.
if ($s < $$href{S}) { # overlaps start of map rule
my $s1 = $s;
my $e1 = $$href{S} - 1;
my $l1 = $e1 - $s1 + 1;
unshift(@ranges, $s1, $l1);
my $s2 = $$href{S};
my $e2 = $e;
my $l2 = $e2 - $s2 + 1;
push(@newranges, $s2 + $$href{O}, $l2);
next range;
} else { # overlaps end of map rule
my $s1 = $s;
my $e1 = $$href{E};
my $l1 = $e1 - $s1 + 1;
push(@newranges, $s1 + $$href{O}, $l1);
my $s2 = $$href{E} + 1;
my $e2 = $e;
my $l2 = $e2 - $s2 + 1;
unshift(@ranges, $s2, $l2);
next range;
}
}
# No intersection, so current range is untouched.
push(@newranges, $s, $l);
}
# Save the resulting list of ranges for next time.
@ranges = @newranges;
}
# Find the minimum range start after all processing.
my $min;
while (@ranges) {
my $s = shift @ranges; shift @ranges;
$min = $s if !defined $min || $s < $min;
}
print "\nminimum location $min\n";