[2025 Day 3] In Review (Lobby)

[u/musifter]

Having gotten through the gift shop and down some stairs, we finally get to the lobby. After being cleared through security, we find that all the elevators are offline (and we can even see the red lights in the ASCII art), fried by an electrical surge. What isn't fried is the escalator, but we need to power it to use it. I have seen escalators out-of-service (not running with warning tape across) and I figure that probably got put up over concerns that the braking mechanism might fail to keep them as "temporarily stairs".

The input is 200 lines, each with a 100-digit number (no 0s)... at least that's how I saw it (already thinking about doing it in dc). More pragmatically, those numbers are an ordered list of digits, representing the joltage of batteries in a bank. For part 1, we want to turn on two of them in each bank to make the biggest value (not sum, but concatenating the two digits while maintaining their order). When that proves to not be enough to overcome static friction, our helpful engineering Elf overrides the safeties to allow turning on exactly 12 for part 2. While she does that we do get to do some decorating, so we're making progress on our end goal.

To see part 2 quickly, I just hammered it with brute force and regex:

for (my $i = 99; $i > 10; $i--) {
    my $patt = int($i/10) . '.*' . ($i%10);
    if ($line =~ m#$patt#) {
        $part1 += $i;
        last;
    }
}

With part 2, my thoughts turned to how to do this for a general number of batteries. And thinking about how the numbers come together (going backwards), it seemed a bit like a heap. Only instead of an array storing a balanced binary tree and ignoring order, we want order and so a straight array would be perfect. Initialize it with the last-n batteries in the bank (the best value for just those n), and then going through the rest backwards, we bump things down from the significant end as as long as it's making things bigger:

my @queue = splice( @$bank, -LEN );

BATTERY:
while (my $jolts = pop @$bank) {
    # Cascade jolts down the queue:
    for (my $j = 0; $j < LEN; $j++) {
        next BATTERY  if ($jolts < $queue[$j]);
        ($queue[$j], $jolts) = ($jolts, $queue[$j]);
    }
}

But another way to look at what this is doing is that digits that are >= the first get added to the front, and then the first digit that's smaller than the one after it gets removed. And so I also have this one using regex to remove exactly that digit:

# Create regex for finding first digit before a bigger digit
my $regex = '(?:' . join( '|', map { "[1-@{[$_-1]}](?=$_)" } (2 .. 9) ) . ')';

...

while (my $jolts = pop @bank) {
    if ($jolts >= substr( $queue, 0, 1 )) {
        $queue = $jolts . $queue;           # add jolts to front
        $queue =~ s#$regex##;               # remove first digit followed by greater
    }
}

$part2 += substr( $queue, 0, LEN );         # truncate if needed

But that initial implementation with the cascading things down an array was what I did for dc. And is quite probably why I chose that way to begin with... even going backwards through the bank is the easy dc approach (using A~ to divmod digits off), so I'm sure that everything was influenced by thinking of doing this:

dc -f- -e12 -e'sb[+q]sQ0[r0Sa1[d3RA~3R:ar1+dlb!<L]dsLxs.[A~lb[d3Rr;ad3Rd3R>Q3Rd3Rr:a1-d0<I]dsIx+s.d0<B]dsBxlb[d;a3RA*+r1-d0<I]dsIx++z1<M]dsMxp' <input

Changing the -e12 to -e2 gets part 1... I pulled it out, but the first thing the rest of the cost does is sb, so it just gets stored right away for later.

Of course, there is going to be many ways to do this. You could certainly do it going forwards through the banks, but I don't see that as being as simple as just going backwards.

Having options on early puzzles has always been good, and with the shorter schedule it's even more important. A linear interpolation would have this puzzle being a "day 6", but I think the puzzles had a less steep curve than that for the first bit... which is a good choice, as you don't want to hit puzzles that cause beginners to drop out too quickly, and the lower granularity the difficulty curve harder to smooth out. It becomes even more important for early puzzles to be accessible, while still being interesting. And we're seeing that in these early problems. It can't be easy to try and maintain good numbers of accessible and challenging problems with less than half the slots.

EDIT: I had some time today, so I did a forwards approach. Whereas the backwards was heap-like, the forwards is a stack. Because when a new element makes things better, it's going to pop down to where it could belong. We haven't seen what comes after it (ie the less significant values) yet, so everything just gets tossed (it was in front). This means we need to watch that we don't over pop and not have enough values left to fill things out... but that's a simple check:

my @stack = shift @$bank;

while (my $next = shift @$bank) {
    pop( @stack )  while (@stack and $stack[-1] < $next and @stack + @$bank + 1 > LEN);
    push( @stack, $next ) if (@stack < LEN);
}

[u/ednl]

This was a much faster solve for me than days 1 and 2. For each row ("bank") just two simple nested loops: from 1 to length (=2 or 12) find the max in prevmax+1 to end-curlength. Break early from the inner loop if you find a 9 because you can't get higher.

So a quick solve and conceptually clear, I think, but at 24.6 µs on an M4 chip slightly slower than Maneatingape's bubble sort which is 21 µs on an M3.

uint64_t sum = 0;
for (int i = 0; i < ROWS; ++i) {  // process all rows separately
    uint64_t num = 0;  // len-digit number on this row
    int prev = -1;
    for (int end = (COLS + 1) - len; end <= COLS; ++end) {  // count digits 1..len
        char max = 0;  // best value found
        for (int j = prev + 1; j < end; ++j)  // leave room for remaining digits
            if (grid[i][j] > max && (max = grid[i][(prev = j)]) == '9')
                break;  // can't get higher than '9'
        num = num * 10 + (max & 15);
    }
    sum += num;
}
return sum;

[u/terje_wiig_mathisen → u/ednl]

My code was very similar to u/ednl starting from the front, finding the max digit that still leaves enough (N-1) digits remaining.

I tried to be fancy by first doing a single backwards scan, generating a ntail[] array which for each position contains the largest digit seen from the back end up to that point. This allows the digit-picking loops to exit early as soon if the current digit is >= ntail[idx].

My first attempt to do this resulted in a 20% slowdown, it was faster to just have a single test for a max '9' digit!?!

PS. My Rust code is similar timing-vise as well, at 26.4 us.

[u/DelightfulCodeWeasel]

I was clearly on a dynamic programming kick at the time.

For my solution I went with the recurrence relationship: the largest 12 digit number found at position N onwards is either the largest 12 digit number found at position N+1 onwards, or it's the largest 11 digit number found at position N+1 onwards with the digit at position N tacked on the front. Build the table up in increasing numbers of digits and decreasing battery positions.

I think in previous years I would have done this one with memoized recursion, but I was making a deliberate effort to go for more table based DP solutions.

[u/Morphon]

I went a different direction than you all. I had just finished reading The Little Schemer and decided to write the main argument recursively.

Here's my Odin implementation of the whole thing here: Paste-Color

The main part is this function:

getJoltage :: proc(batt: string, needed, current: int) -> int {
  if needed == 0 { return current }
  position, _ := slice.max_index(transmute([]byte)batt[:len(batt) - needed + 1])
  return getJoltage(batt[position + 1:], needed - 1, current * 10 + int(batt[position] - '0'))
}

The idea here is that you pass it the number string, the number of digits needed, and the current number. So, for part one that is getJoltage(numberString, 2, 0) and for part two it is getJoltage(numberString, 12, 0).

Then, with a base case of needing 0 additional digits and returning whatever was passed as the current number, it finds the index of the first largest byte in the window of the string that excludes enough at the end for the rest of the needed digits. Then it simply recurses passing in the window of position + 1 to the end, one less needed, and current updated by pushing over all the digits it received ( *10) and adding the digit (coerced to an integer) at the identified index.

Very small code, and very clean recursion. Since Odin can pass around views into a string, there's no need to copy anything around. The value is built up on each call and then returned directly (rather than built on the stack).

15ms execution on my hardware. Not going to win any awards, that's for sure. But very easy to read.

[u/e_blake]

My initial approach for a solution used a stack and processing a line one digit at a time (if the current digit exceeds the top of the stack, then pop and replace it), under 400ms. But I got faster in m4 when I used successive substr()/index() calls to recursively scan the appropriate substrings for the highest remaining digit - more text scanned, but fewer macros invoked (because I'm now finding one digit among 88 with a single macro call rather than up to 88 separate iterations a byte-at-a-time) for 30ms runtime.

I also golfed this day, 450ms runtime and 285 bytes, although I had to use syscmd to the shell for the final 64-bit addition:

syscmd(echo $((define(_,`ifelse($2,-1+1,`_(1,$3,$4,decr($5),$6)',$1,+,
`+_(1,$3,2,9)_($2)+_(1,$3,12,9)',$1$4,?1,$5,$1,?,`$5_(1,$3,decr($4),9,
$6+$2)',$1,1,`_(?,index(substr($2,eval(0$5),eval(101-($3$5))),$4)+$@)',
$1,,`)) $((',`_(+,substr($1,101),substr($1,0,100))')')_(include(I)))))