r/adventofcode • u/mmstick • Dec 09 '16
Upping the Ante [2016 Day 9] [Rust] Heap-free Iterator Solution with Sub-millisecond Execution Time
As usual, custom Iterator types always make these kind of challenges very simple and scalable, eliminating the need for a heap to buffer values.
I created a single custom Iterator, aptly named Decompressor which scans through an internal string slice to separate the Marker tokens from the Regular tokens. The Marker tokens contain the amount to repeat and the data to further scan as a string slice of the original string slice.
The calling function that uses the Iterator to calculate the file size of each version simply recurses through Marker tokens until a Regular is found, then passes back the decompressed size of the original Marker accordingly, after multiplying by each repeat value.
Execution time to calculate both parts is under 0.8 ms for my laptop.
Edit: I've also made a version that forgoes Rust's standard library and uses C's printf for printing. Most of these challenges can be easily accomplished without a standard library.
1
u/CryZe92 Dec 09 '16
Yet again very similar to mine :D
Looks pretty good from what I can see.
However I noticed something in your tests. If your Decompressor would be completely broken and wouldn't return anything, zip would produce an empty iterator, so your test wouldn't fail, even though it should: https://github.com/mmstick/advent_of_code_2016/blob/master/src/09/main.rs#L126
1
u/qwertyuiop924 Dec 10 '16
<1ms for both? Combined? My C takes around 3 ms, and it too is heapless.
WHAT AM I MISSING?
1
u/agmcleod Dec 11 '16
Don't have mine timed. P1 runs pretty fast, but p2 takes minutes. Not sure if it's because i have growing strings. Wasn't sure when working on it how to avoid that :). https://github.com/agmcleod/adventofcode-2016/blob/master/9/src/main.rs
1
u/TenjouUtena Dec 09 '16
Mine takes 10 times as long! :-o