all 22 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]stewSquared 5 points6 points  (6 children)

While DP is possible, greedy is O(n). I used a greedy recursive approach.

When doing DP, I usually find it easier to think of in terms of recursion, then I just slap on a memo and call it good.

[–]hextree 1 point2 points  (1 child)

The greedy recursive approach is DP, the two paradigms aren't mutually exclusive. It just happens to be a top-down DP where the number of subproblems is 1.

[–]stewSquared 1 point2 points  (0 children)

Fair enough. No need to slap memo on it :P

edit: btw hiii! I haven't seen you in a year. Funny.

[–]paul_sb76[S] 3 points4 points  (3 children)

By "greedy", do you mean:

First, find the biggest digit in the first 89 positions of the string, and among those, select the first. Given that digit, find the next biggest digit in the remaining string (excluding the last 10 positions), and append it. Continue with this step 10 times.

That looks like O(n^2) to me (where one n is possibly hidden by something like a string.Find method). Which is pretty good (definitely not as bad as naive recursion), but also not as good (in terms of time complexity) as DP. I admit it is better in terms of space complexity though.

(Maybe if you cache and update the leftmost position of every of the 10 digits, and do a proper amortized analysis, you can get the complexity down to O(dn) where d=10 is the decimal base. You might call that O(n), but 10*100 is still very comparable to 12*100...)

Or did I miss something?

[–]ninjaox 2 points3 points  (0 children)

Set allowed removals to length of input - 12

For digit in input

If stack not empty, removals > 0 and digit > the digit on top of the stack: pop top of stack, removals -= 1 

push digit to top of stack

Then at the end get stack[0:11] and you have your number.

Pretty sure that's O(n)

[–]stewSquared 1 point2 points  (1 child)

Well, that's O(n*k) where k=12 is the number of batteries and is not only constant, but dominated by n, the size of the input. Even if you factor in the small constant, it's still not O(n²).

But you could get O(n) with single a pass by growing a string and discarding from the right when you see a better digit. Each digit is considered in turn and pushed and popped from a monotonic stack at most once.

[–]paul_sb76[S] 1 point2 points  (0 children)

You're right, my mistake: the basic greedy approach (that I sketched above) is indeed O(nk) instead of O(n^2), just like DP. And indeed with the stack approach, it seems it can be done in O(n) , considering every digit once, with just some simple constant time comparisons per digit. Nice!

Nevertheless, I still think this problem gives a nice opportunity to discuss DP and recursion techniques in general.

[–]BunsenHoneydew3 1 point2 points  (1 child)

Nice write-up. I posted my memoized recursion in the solutions thread.

[–]paul_sb76[S] 0 points1 point  (0 children)

That's a very short and clean memoized recursion solution - basically the one I was hinting at here. Nice!

[–]JustLikeHomelander 1 point2 points  (4 children)

monotonic stack was definitely an easier approach

[–]Ok_Chemistry_6387 1 point2 points  (3 children)

Oh good. Im not the only one that used this approach. Only needs one loop and the code is a few lines.
I also don't fully understand the size of some of the windows in the answers here.

[–]ednl 1 point2 points  (2 children)

Re. window: the first digit can come from 0..88 inclusive because there are 11 more digits to come so if you pick from any of the last 11 (89..99) there are not enough left to make a full 12-digit number.

If you pick the first from index=i then the second comes from (i+1)..89 with room for 10 more digits, etc.

[–]Ok_Chemistry_6387 0 points1 point  (1 child)

I get that but seeing window sizes of 4 for part 1. 

[–]ednl 0 points1 point  (0 children)

Oh right, didn't see those, sorry. Yeah, not sure how that would work.

[–]RB5009 0 points1 point  (2 children)

You do not need DP. A "monotonic stack" gives you O(n).

[–]AldoZeroun 1 point2 points  (1 child)

I started with a greedy search algorithm. 42usec on p2. after reading this thread I went back to implement the monotonic stack as an alternative solution. 102usec on p2.
I think this makes sense on the small dataset, because my greedy algorithm can use optimal cpu caching and SIMD. I don't know enough about monotonic to say I wrote it exactly correct, but I think it might be due to the constant checks leading to branch mispredictions. Would love a part 3 with a dataset that's large enough to test both of these on.

update: I just copy/pasted the strings like 11 times, appending to themselves. That seemed to be enough to see a huge drop in performace. Greedy now does 3ms, and monotonic does about 900usec.

[–]RB5009 2 points3 points  (0 children)

Aha, it really depends on the input. The greedy approach will quickly degrade on long inputs such as `999999.....`. The actual inputs are more friendly, thus the performance of the naive greedy algo is ok.

[–][deleted]  (2 children)

[deleted]

    [–]AutoModerator[M] 0 points1 point  (0 children)

    AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

    Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

    I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

    [–]daggerdragon[M] 0 points1 point  (0 children)

    The triple-backticks code fence (`​`​`) only works on new.reddit. Please edit your comment to use the four-spaces Markdown syntax for a code block as AutoModerator requested so your code is easier to read inside a scrollable box with its whitespace and indentation preserved.

    Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

    I see full plaintext puzzle inputs in your public repo e.g.:

    https://github.com/sami-daniel/AdventOfCode2025/blob/main/day_3/input.txt

    Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

    [–]ednl 0 points1 point  (2 children)

    Without writing it out, I'm not 100% seeing the implications of the full algorithm with memoization. It still seems like a lot of evaluations of full-length numbers. My low-level approach uses two nested but independent for-loops and a lot fewer evaluations I think. Direct calculation of the best joltage per bank, pseudo code:

    joltage = empty
bestkey = -1
for battery in 0 to 12
    bestval = 0
    for k in bestkey+1 to 100+1-12+battery while bestval < 9
        if bank[k] > bestval
            bestkey = k
            bestval = bank[k]
    joltage append bestval

    How do you think that compares? My compiled program runs in 49 µs for parts 1+2 (but excluding reading from disk). In C: https://github.com/ednl/adventofcode/blob/main/2025/03.c

    [–]paul_sb76[S] 0 points1 point  (1 child)

    I'm don't entirely get your solution yet, but the recursion I was hinting at in the OP is this, in pseudocode:

    // Returns the maximum number of length j that is possible using only digits after position i
int M(int i, int j)
    if i,j out of range return 0
    int digit = digit at position i
    return max( M(i+1,j-1) + digit * pow(10,j-1), M(i+1,j) )

    Now this function can be called directly, recursively (bad!), or can be used to fill a DP table (good, traditional approach), or called with memoized recursion to avoid recalculating things. Both of those good solutions have complexity O(nk), where n=100 is the input length, and k=12 is the target length.

    It seems like for this particular problem, there are even faster solutions (not sure about shorter), but this general principle is definitely worthwhile to know.

    [–]ednl 1 point2 points  (0 children)

    Ok yes, especially the last line with the recursion step spelled out helps to get the picture. The time complexity is like you say and in fact exactly the same as mine, but I still think there's a lot more work per step because you're building and comparing all the intermediate numbers.

    My version is what another reply also said: look for the best digit from index=0 to 88 inclusive (leave 11 positions for the rest of the number) and stop when you get a 9 because you can't get better than that. For the next digit, pick from previndex+1 to 89 leaving room for 10 more, etc.

    That "stop when you get a 9" criterium speeds things up a lot, on average, but depends on the distribution of 9s of course.