Solutions for Advent of Code in Rust.
This year, my focus is not on short or cute, but raw performance. Goal is to measure individual parts in microseconds instead of milliseconds and to solve every problem with a total budget of 100 milliseconds.
All rows with solutions over a millisecond are marked with 😔, those with over 50 ms are marked with 😔😔. The days exceeding 500 ms are marked with 😔😔😔.
| Day | Solution | Part 1 | Part 2 | Notes |
|---|---|---|---|---|
| 1 | 01.rs | 33.44µs | 31.10µs | Process everything in single iteration, avoid sorting results in part 2 |
| 2 | 02.rs | 76.84µs | 59.15µs | Use suitable representations to allow using modular arithmetic for comparisons |
| 3 | 03.rs | 54.33µs | 51.12µs | Represent rucksack as a bitset |
| 4 | 04.rs | 69.46µs | 56.73µs | - |
| 5 | 05.rs | 40.67µs | 36.89µs | - |
| 6 | 06.rs | 5.00µs | 7.09µs | Calculate forward skips to avoid processing most of the input |
| 7 | 07.rs | 43.68µs | 60.68µs | Avoid actually building the tree |
| 8 | 08.rs | 78.85µs | 161.86µs | Precalculate maximums for each side to speed up part 1 |
| 9 | 09.rs | 352.48µs | 574.63µs | - |
| 10 | 10.rs | 5.37µs | 9.09µs | - |
| 11 | 11.rs | 25.28µs | 5.42ms | 😔 |
| 12 | 12.rs | 759.12µs | 869.94µs | Search using A*, use custom map for distances |
| 13 | 13.rs | 22.63µs | 17.51µs | Avoid building trees, parse data only as far as needed |
| 14 | 14.rs | 170.18µs | 365.68µs | Backtrack on the paths instead of starting all over |
| 15 | 15.rs | 456.34µs | 122.09ms | 😔😔 |
| 16 | 16.rs | 9.92ms | 6.53ms | 😔 |
| 17 | 17.rs | 221.94µs | 326.42µs | Keep previous states in cache to find the period of the process |
| 18 | 18.rs | 160.66µs | 437.68µs | Represent the set of points as a bit-set |
| 19 | 19.rs | 574.06ms | 941.26ms | 😔😔😔 Heuristics to direct the search, memoization, pruning against best result seen so far |
| 20 | 20.rs | 5.08ms | 53.33ms | 😔😔 |
| 21 | 21.rs | 325.30µs | 235.40µs | - |
| 22 | 22.rs | 139.31µs | 127.73µs | - |
| 23 | 23.rs | 916.03µs | 87.09ms | 😔😔 Keep three different data structures to make everything inside the loop O(1). Use suitable bit-representation for data. |
| 24 | 24.rs | 14.71ms | 26.31ms | 😔Search using A* with a smart heuristic. Represent each state in 32 bits. Use Vector instead of Map for g-scores. |
| 25 | 25.rs | 17.04µs | - | - |
In the end, days 15 and 19 blew the 100 ms budget by themselves while days 20 and 23 were over 50 ms. Ignoring those outliers, the total time for the rest of the 21 days is 69 ms, which is pretty decent, especially considering that only day 19 exceeded total runtime of one second and even that is under two seconds. That said, the total runtime for all days is 1.85 seconds, which almost 19 times more than the budgeted 100 ms.