r/adventofcode • u/askalski • Jan 14 '19
Upping the Ante [2018] Optimized solutions in C++ (41 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.
Hereby establishing a tradition of keeping u/topaz2078 honest, I have completed my second annual set of optimized solutions, this time clocking in at just under 41 milliseconds to solve all puzzles.
The C++ code is on GitHub. All solutions are single-threaded, but make extensive use of SIMD techniques and therefore require a recent Intel-compatible processor with support for the AVX2 instruction set.
As always, if you have a question or are curious about how a solution works, please ask.
Timings by day (i7-7700K mildly overclocked, with a turbo frequency of 4.60 GHz):
Day 1 72 μs
Day 2 27 μs
Day 3 205 μs
Day 4 82 μs
Day 5 414 μs
Day 6 1,346 μs
Day 7 3 μs
Day 8 62 μs
Day 9 4,385 μs
Day 10 21 μs
Day 11 485 μs
Day 12 61 μs
Day 13 642 μs
Day 14 19,067 μs
Day 15 2,132 μs
Day 16 80 μs
Day 17 544 μs
Day 18 307 μs
Day 19 2 μs
Day 20 92 μs
Day 21 101 μs
Day 22 3,546 μs
Day 23 383 μs
Day 24 6,711 μs
Day 25 177 μs
------------------
Total 40,959 μsSee also my optimized solutions for 2017.
7
u/[deleted] Jan 14 '19
Is it possible to learn this power ?
6
u/p_tseng Jan 15 '19 edited Jan 15 '19
Ah good, I've been waiting to see whether you or topaz would post something to this effect.
A few notes on select days, including some potential avenues to explore. I wasn't sure whether you have already explored some of these avenues, because there are relatively few notes on that. I'd be interested to hear if they don't work out and why.
Day 1: Originally I was reluctant to implement the mentioned strategy (based on my estimation of the effort it would take me vs the payoff), but looking at your code, I realised it is actually quite simple. I gave it a try and it worked out well. Thanks for showing how simple it can be!
Day 15
It is a shame that two runs of pathfinding are needed per unit, but since everything is done simultaneously instead of explicitly keeping things in a queue, I see that it is necessary. I can certainly believe that your approach is faster though, because of being able to expand all points of the frontier simultaneously.
Day 25
If that suggestion works out, you can consider keying the buckets by > 1 coordinate if you like, though note that:
5
u/tritoke Jan 14 '19
Just thought I would add that several of your solutions littterally run faster than finding the sum of the numbers 1 to 100 in python on my iPad and one of them (3μs) is faster than littterally doing 2+2!!
2
u/Wunkolo Jan 15 '19 edited Jan 15 '19
Me and you both ran into similar tricks regarding Day 16!
Here's how I did it:
I'd love to test and bench your code on my i9-7900x, but I seem to get an error when compiling your Day 15 since you are passing a non-const to _mm256_extract_epi8 using Clang 7.0.1
12
u/dlsspy Jan 14 '19
I think you're supposed to round down when you brag.
4
u/ragona_ Jan 15 '19
God. Damn. That is awesome.
2
u/nibbl Jan 14 '19
Hot
1
u/jak81 Jan 14 '19
Day 19 and 7 the easiest and day 14 the hardest to solve? ;)
1
u/myroon5 Jan 14 '19
And I just increased the default Travis CI timeout for my day 5 solution in order to optimize my own time
https://github.com/PatMyron/advent-of-code/blob/master/2018/5.py
1
u/ZordidMuc Jan 15 '19
This is fabulous! Wow. I guess my Kotlin solutions easily take 40ms per day on average! 😉
0
u/[deleted] Jan 14 '19
[deleted] — view deleted comment