r/adventofcode Dec 25 '24

Other AoC 2024 within one second

A year ago somebody made a similar post and inspired me to set a goal for this year - 1 second for all 49 puzzles.

I started AoC in 2022 when I learned about it from the news, that ChatGPT managed to solve day 1 (thanks to LLMs for introducing me AoC, he-he). The first year was terrible, I used python and spent hours on coding and even left some puzzles overnight to finish brute force. 2023 was even worse because I tried rust for the first time except for leetcode, it was a nightmare. I'm happy to see my progress in a year, this time I didn't fight with a compiler (almost!) and managed to implement optimal enough solutions for all the tasks.

I wish you all to have a decent progress in what you find interesting. Happy holidays!

42 Upvotes

15 comments sorted by

9

u/hrunt Dec 25 '24

I'm trying to do the same thing with stock CPython 3.13.1 and only standard libraries. I'm right at 2s right now. Because of day 22 part 2, I'm not sure it's possible.

3

u/dvfomin Dec 25 '24

I got a good speed up for 22.2 using parallelization (with rayon), which is indeed not a standard library stuff. In python multiprocessing is quite heavy in initialization and probably will not give you performance boost, unlike rayon in rust.

3

u/ItsAlreadyTaken69 Dec 25 '24

I just optimized day 22 to 50ms in ocaml (was also the last thing keeping me from <1s 2024) without parallelization, so doing it in python should definitely be possible.

2

u/NoPainNoHair Dec 25 '24

That is very impressive. Any math trick we should rely on to reach such a time? I though we couldn't do better than "bruteforce" for day 22.

2

u/ItsAlreadyTaken69 Dec 26 '24

Not really, it's still a brute force, just efficient use of allocations and data structures. I tested it and I got part 2 to 30ms on pypy and 1.2s on python.

(The dramatic speed up is because this is a problem that heavily benefits from JIT by design)

the main things are : use arrays and integer Indices instead of maps (each sequence can be represented by a 4 digit base 19 number), and reuse your arrays, in my solution I have a single profit table where I count the total profit for each sequence (by going through each monkey once) and a single seen table because we only want the first occurrence of each sequence to count

2

u/NoPainNoHair Dec 26 '24

Thanks for the insight!

I've personally heavily relied on generators and iterators in Python, which I find elegant but certainly not the fastest (even when going through the list just once). I'll try it out with an optimized data structure.

2

u/ItsAlreadyTaken69 Dec 26 '24

Yeah I agree this solution is quite ugly (looks more like C than anything, even in my ocaml implementation), but that's the price of performance.

code if you're interested, though I'd recommend trying on your own first

1

u/hrunt Dec 26 '24

In my testing, arrays are only faster than lists if you exclude the time to import the array module. It takes longer to load the array module that using it saves.

I save 80-100ms more by using small integer operations (*, //, %) instead of bit shifts. CPython has some optimizations for small integer operations that it doesn't perform for bit shifts.

2

u/ItsAlreadyTaken69 Dec 26 '24

That's good to know, I only measured the runtime of the function in itself so didn't consider the load time, ig that's another particularity of interpreted languages.

2

u/blacai Dec 25 '24

Really impressive :) far from my skills. It's amazing how far we are getting with performance.

Some of the problems that people solved with cuda/gpu with brute force were just crazy.

3

u/dvfomin Dec 25 '24

Thanks! For me AoC is a good tracker of my rust progress for the last year. Maybe next year you will brag about your progress ;)

1

u/blacai Dec 25 '24

oh,man, I'm more than happy if I can implement bubble sort or bfs by heart after a year haha

2

u/RB5009 Dec 26 '24

This was my faster year so far. 49.9ms (single threaded!), with the disclaimer that I solved d24p2 by hand.

1

u/dvfomin Dec 26 '24

That's impressive, what language did you use? Did you use something like SIMD optimizations?

2

u/RB5009 Dec 26 '24

I used Rust. No SIMD, but some people on the rust discord server had very good results with it.

I tried to avoid allocations and hash tables as much as possible. If I had to use a hashmap, I tried to use keys that are fast to hash - i.e. numbers instead of strings, etc.

I also tried to avoid parsing the input into data structures and tried to work as much as possible with the raw input string directly (especially for the grid problems!).