advent-of-code-2021

Rust this time

Timings

Run with RUSTFLAGS="-C target-cpu=native" cargo run --release. All times in µs.

Day	Title	Parsing	Part 1	Part 2	Notes
1	Sonar Sweep	255	25	8	Sliding window.
2	Dive!	36	356	356	Time is both parts together.
3	Binary Diagnostic	378	20	686	`BitVec`; not working ideally for part 2.
4	Giant Squid	204	240	181	`ndarray`, but suboptimal iteration.
5	Hydrothermal Venture	666	1842	281	`ndarray`: Slices for part 1; index for part 2.
6	Lanternfish	57	17	2	State space model. `memcpy` faster than ptr move.
7	The Treachery of Whales	182	89	245	Part 1 median. Part 2 `iter().map()`.
8	Seven Segment Search	440	21	1503	Use `HashSet` for logic.
9	Smoke Basin	228	108	248	Manual `Matrix` class. Part 2 recursive.
10	Syntax Scoring	79	123	61	`Vec.pop()` to make a stack.
11	Dumbo Octopus	66	132	126	Manual `OctoMatrix` class. Line scan to update. `octo_emoji` writes 🐙/✨.
12	Passage Pathing	275	256	5866	Recursive DFS ignoring some nodes.
13	Transparent Origami	609	80	237	`HashSet` for paper.
14	Extended Polymerization	127	2440	440	Part 1: brute force + FM-index. Part 2: `BTreeMap` of 2-mers.
15	Chiton	209	1937	64008	Djikstra's algorithm from `BinaryHeap` docs.
16	Packet Decoder	226	122	4	`BitVec`, recusion and struct with children indexed in a `Vec`.
17	Trick Shot	370	638	5	Grid-search, using `.map()` over (x, y) pairs.

Other notes

Day 5

Seems slow. I've tried ndarray and nalgebra slices which are very similar and neat. Manual Matrix class is similar. I would guess a sparse matrix solution (like for d13) would be better.

Day 13

Originally I used Termion, but in many cases it was printing over other terminal output. HashSet slightly faster than BTreeSet.

Day 14

The part two solution is of course faster, but I tried using an FM-index to do the counts in part 1, which works easily enough (although of course these could have been computed on-the-fly).

Day 16

I was very frustrated by not being able to work out how to write a generic bv_to_int which would have been easy in C++. Writing let x: T = 0 fails to compile!
Not sure BitVec is quite what I think it is, need to check its underlying representation later. (Note: u8 and u64 template parameter made no difference to speed in this case).
Avoided using Rc to point to other nodes in the graph which might have been nice. Was easier to find a way of avoiding using smart pointers, which wasn't hugely satisfying.

Day 17

Regex is quite slow here.
Doing an operation on an .iter().map() e.g. .sum() or .max() is a little (10-20%) quicker than storing it all with .collect().

johnlees / advent-of-code-2021 Goto Github PK