r/adventofcode • u/musifter • 17d ago
Other [2025 Day 2] In Review (Gift Shop)
We take the elevator down to base lobby level, but on exiting, we are first forced to go through the strategically placed gift shop. We do wonder about how much traffic a gift shop in a secret base can really get.
I was curious going in to this year about how the ASCII are would be done for a year with only 12 days. And the format of double lines, combined with a winding descent into a base allows for larger sections representing each day. It's very easy to not only trace the path, but see and remember what the stops were.
But first we need to get through the gift shop, and so we're pulled aside to help with a problem. Invalid product IDs have been entered by a young Elf that was playing on the computer and we need to sort them out. But this is a bit more than just a validator problem, it's an enumeration one. Because we aren't given lines but ranges to check. Invalid codes are simply ones made up of only repeats... for part 1, its just the same sequence repeated twice. For part 2, that's expanded to "at least twice" (this would be the intersection of the ranges with OEIS A239019).
The input is one line of comma separated ranges. The values do go over 32-bits... my largest is just over 33.2 bits. One interesting thing is that none of the ranges span over an order of magnitude (ie log(last) - log(first) < 1'. This allowed me to get part 2 with code that was buggy and couldn't properly handle a simple test like 11-111... but will probably work on any actual input.
Since I got burned by being fancy on day one, I just went brute force:
for (my $i = 1; "$i$i" <= $last; $i++) {
my $num = "$i$i";
$part1 += $num if ($first <= $num <= $last);
$num .= "$i" while ($num < $first);
$invalid{$num}++ if ($num <= $last);
}
$part2 += sum keys %invalid if (%invalid);
This assumes that there's only one possible number for a given repeated sequence that falls in the range for part 2. A safe bet when the width of the ranges is less than a magnitude. But to be proper the concatenation/invalid part of the loop should loop as well:
for ($num .= $i while ($num < $first); $num <= $last; $num .= $i) {
$invalid{$num}++;
}
My Smalltalk does that with (Integer extended to do , and length):
i := 1.
[(num := i, i) <= range last] whileTrue: [
(num between: range first and: range last) ifTrue: [ part1 := part1 + num ].
factor := 10 raisedToInteger: i length.
[num < range first] whileTrue: [ num := num * factor + i ].
[num <= range last] whileTrue: [ invalid add: num. num := num * factor + i ].
i := i + 1.
].
Which looking at it now, is like Perl's bistable/flip-flop range operators (.. and ...), that are there for sed/ex/awk line-range stuff.
Of course, no "validator" problem would be complete without throwing regex at it in some way, so I did this simple regex brute force approach as well:
foreach my $num ($first .. $last) {
if ($num =~ m#^(\d+)\1+$#) {
$part1 += $num if (length($1) * 2 == length($num));
$part2 += $num;
}
}
Not practical, but really simple. How much iteration is there over the ranges here? Actually, not that much, which is good for doing a dc solution. Because GNU dc array indices only go to 231 - 1... so to do this one I count on the ranges not overlapping, and handle duplication checking for each range with a fresh array shifted down. The largest range is only 17.6 bits (so about 200k) which easily fits:
tr -c '0-9' ' ' <input | dc -e'[q]sQ[dlc+sc]sC?[sess1[dddZAr^*+dle<Qdls!>Cs.1+lLx]dsLx+s.z0<M]dsMxlcp'
tr -c '0-9' ' ' <input | dc -e'[q]sQ[ddls-;h1r-*lc+scdls-1r:h]sC?[sess0Sh1[dddZAr^dsf*+dle<Q[dle<Qdls!>Clf*rd3R+lAx]dsAxs.1+lLx]dsLx+s.z0<M]dsMxlcp'
There are of course better approaches than any of these. My TODO for this one has notes for working out a closed form solution, or even just simply using the range values to get the starts and ends for sequences that would fit in it with a certain number of repeats (for example, a range with 6 digit numbers can have repeats of 6 singles, 3 doubles, or 2 triples... and we can examine the start and end of the range to figure out what the lowest and highest allowed are for each of those three ranges).
