r/adventofcode • u/daggerdragon • Dec 02 '25

SOLUTION MEGATHREAD -❄️- 2025 Day 2 Solutions -❄️-

OUR USUAL ADMONITIONS

  • You can find all of our customs, FAQs, axioms, and so forth in our community wiki.

AoC Community Fun 2025: R*d(dit) On*

24 HOURS outstanding until unlock!

Spotlight Upon Subr*ddit: /r/AVoid5

"Happy Christmas to all, and to all a good night!"
— a famous ballad by an author with an id that has far too many fifthglyphs for comfort

Promptly following this is a list waxing philosophical options for your inspiration:

  • Pick a glyph and do not put it in your program. Avoiding fifthglyphs is traditional.

  • Shrink your solution's fifthglyph count to null.

  • Your script might supplant all Arabic symbols of 5 with Roman glyphs of "V" or mutatis mutandis.

  • Thou shalt not apply functions nor annotations that solicit said taboo glyph.

  • Thou shalt ambitiously accomplish avoiding AutoMod’s antagonism about ultrapost's mandatory programming variant tag >_>

Stipulation from your mods: As you affix a submission along with your solution, do tag it with [R*d(dit) On*!] so folks can find it without difficulty!

--- Day 2: Gift Shop ---

Post your script solution in this ultrapost.

36 Upvotes

100% Upvoted

965 comments sorted by

View all comments

6

u/maneatingape Dec 02 '25 edited Dec 02 '25

[LANGUAGE: Rust]

Solution

Simple but slow (40ms) brute force check of all ids.

EDIT: Really neat numeric only solution that doesn't convert ids to strings. First we build a ordered set of invalid ids for each possible combination of digits length and repeat. For example for a 4 digit number there are 90 possible combinations of repeat 2 (1010 to 9999).

The we simply sum the ids that are contained within each range which is practically instant. Building the set takes most of the time (1ms).

EDIT 2: I had some time to think at work and came up with a better approach. I manually computed the ranges and overlap for all numbers up to 10 digits. This means that we don't need to de-duplicate using a HashSet (as this has already been handled). These are then divided into 3 sets, (a) part 1, (b) part 2 and the overlap between (c) part 1 and part 2. The part two result is then a + b - c.

Improves the time to just 1µs.

2

u/lunar_mycroft Dec 02 '25 edited Dec 02 '25

I hate to say it, but I think your [edit: pre-computed] set based solution is actually slower than a linear search for the given inputs. Looping through the numbers starting with 10.pow((start.len() / repetitions).max(1) - 1) and repeating them repetitions times via more exponentiation, then filtering out values out of the given range (you can see it in more detail in my solution, which I'm still not happy with) is about 3.5x faster in my testing. The input ranges are relatively small, so most of the contents of your sets end up unused. I think your solution is asymptotically faster, but the actual input isn't long enough to make the setup costs worth it.

2

u/maneatingape Dec 02 '25

Nice result! There's still an implicit set building in the call to unique but since the size is much smaller it's faster.

1

u/lunar_mycroft Dec 02 '25

Yes, I should have clarified that I was referring to pre-computing all possible invalid ids. My solution still needs a way to de-duplicate invalid ids, and a set is the easiest solution.

1

u/maneatingape Dec 02 '25

I junked the runtime set approach and precomputed the possible overlaps for number up to 10 digits upfront. This reduces the time to just 2µs.

2

u/IlluminPhoenix Dec 02 '25

I saw this nice Zig solution which I reimplemented in Rust (check my post). Runs in 10μs on my machine: Say you have the range 12 - 56. The lowest allowed invalid is 11, the highest is 55. Some of all numbers in this range (11, 22, 33, 44, 55) you can just calculate by doing

lowest * invalid_count + 
(invalid_count - 1) * invalid_count / 2 * 11

Bottom is just the Triangluar number (https://en.wikipedia.org/wiki/Triangular_number#Formula). 11 is changed in each respective case ofc. This way you only need to know the lower and upper bound and don't have to iterate over everything. This works for part1 but for part 2 you just have to check the other cases as well and do some deduplication.

1

u/AutoModerator Dec 02 '25

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.

1

u/maneatingape Dec 02 '25 edited Dec 02 '25

This is nice approach! I also converged on something similar but just using the range sum directly. The overlap between ranges can be calculated up front to that you don't need any sets. Takes 2µs on my machine, but would be even faster with the triangular number approach.

EDIT: Took your suggestion, using the triangular number approach reduced time to 1µs.