mirror of
https://github.com/Smaug123/advent-of-code-2017
synced 2025-10-08 13:08:39 +00:00
43 lines
2.3 KiB
Markdown
43 lines
2.3 KiB
Markdown
# advent-of-code-2017
|
|
Solutions to the 2017 Advent of Code (https://adventofcode.com/2017/), in Rust.
|
|
Trying to strike a balance between performance and ease-of-writing, erring on the side of performance where necessary.
|
|
|
|
Simple to use: just `cargo test --release` or `cargo test -p day_1`, for example.
|
|
Some crates have Criterion benchmarks: `cargo bench`, or `cargo bench -p day_1`, for example.
|
|
|
|
I'm certainly no expert in Rust; don't assume I've done anything in a sane way.
|
|
|
|
# Day-specific notes
|
|
|
|
## Day 3
|
|
|
|
This one I put quite a lot of time and effort into choosing a fast solution.
|
|
That means, for example, a constant-time answer to part 1, and a cache-friendly implementation for part 2.
|
|
This came at the cost of a lot of code complexity!
|
|
|
|
## Day 7
|
|
|
|
This was the first recursive data structure I've attempted in Rust.
|
|
After fighting the borrow checker repeatedly (and grudgingly coming to admit that while I knew what I wanted to do was safe, there was no possible way even in principle that I could demonstrate it to Rust without some kind of dependent types), I ended up going for a slotmap.
|
|
It felt a bit odd, given that I always think of creating the slotmap as the easy part of constructing a tree from a list of edges; but that's probably just my inner garbage-collector speaking.
|
|
|
|
## Day 9
|
|
|
|
I attempted this one chronologically after Day 7, so I was already primed to consider using a slotmap.
|
|
However, this time, I arranged things from the very beginning on the assumption that I would be using a catamorphism for all queries against my tree structure.
|
|
That meant I was psychologically happy to make the internals weird, because the user is only ever going to use the cata.
|
|
|
|
## Day 12
|
|
|
|
This one I didn't really bother reifying into a "proper" data structure, because I already knew what tasks were involved in Part 1 and Part 2.
|
|
|
|
## Day 13
|
|
|
|
I know there's a proper answer to this question, one which uses the Chinese remainder theorem to get a solution in time linear in the number of constraints.
|
|
I honestly just couldn't be bothered, so I put in a slight optimisation (namely putting in the more effective "can I rule out this number" checks first) but just left it at that.
|
|
|
|
## Day 18
|
|
|
|
Actually really enjoyed this one!
|
|
There's probably lots and lots of scope for a nice design which actually reifies the channel between the machines, but I didn't start thinking about that.
|