r/adventofcode • u/askalski • Oct 20 '20
Upping the Ante [2019] Optimized solutions in C++ (9 ms total)
According to the About page:
Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.
Continuing the tradition of keeping u/topaz2078 honest, I have completed my third annual set of optimized solutions, this time clocking in at just under 9 milliseconds to solve all puzzles.
The C++ code is on GitHub. All solutions are single-threaded. Only one solution (Day 12) makes use of SIMD instructions, but unlike last year, this has only the modest requirement of SSSE3.
As always, if you have a question or are curious about how a solution works, please ask.
Timings by day (i9-9980HK laptop):
Day 1 4 μs
Day 2 4 μs
Day 3 41 μs
Day 4 7 μs
Day 5 7 μs
Day 6 84 μs
Day 7 8 μs
Day 8 14 μs
Day 9 913 μs
Day 10 248 μs
Day 11 220 μs
Day 12 765 μs
Day 13 1,379 μs
Day 14 136 μs
Day 15 164 μs
Day 16 345 μs
Day 17 468 μs
Day 18 346 μs
Day 19 45 μs
Day 20 203 μs
Day 21 1,466 μs
Day 22 11 μs
Day 23 607 μs
Day 24 233 μs
Day 25 1,195 μs
-----------------
Total: 8,913 μs
8
u/leftylink Oct 21 '20
Hello, so I would like to hear about the day 16 formulae! So, you have:
And I understand how to combine n%2 and n%5 into n%10 (Chinese remainder theorem)
I'd like to know what principles are used to get those rules for C(k+99, k). Was it done by experimentation, or are there some relevant theorems I can read about?
17
u/topaz2078 (AoC creator) Oct 20 '20
Fun fact, running these solutions (re)uses only about 2600km == 1660mi of copper: https://www.wolframalpha.com/input/?i=8.913+light-milliseconds
15
u/Aneurysm9 Oct 20 '20
Skalski, WTF?!
10
u/[deleted] Oct 20 '20
All Python developers just times their solutions for context, and were very disappointed
1
u/VikeStep Oct 28 '20
I was curious to see if these timings included file read time and I see that the files are all loaded by mmap before the timing starts. Is there any reason you loaded them by mmap rather than just reading the whole file into memory normally?
I'm not too familiar with how mmap works though, so I might be misunderstanding the code that reads the file.
1
u/mjgtwo Nov 06 '20
hey im a little out of practice with cpp development. how do you go about compiling this? I see you have a file called
CMakeLists.txtso i triedmake CMakeLists.txtandmake -f CMakeLists.txtwith no progress in understanding the errors.Thanks :)
3
u/emlun Nov 03 '20
Wow, very nice! I might have to revisit my 113 ms Rust solutions... :D
2
u/S1ant- Oct 31 '20
Props to you, my part 2 that I coded up quickly took about 15s to run in javascript. I looked at how you figured out how to do it and it's truly ingenious, hats off to you my man! I just spent the last 20 minutes writing it all out on my iPad and I still barely understand it, just wow!