Expand description
Advent of Code 2022 Day 13: https://adventofcode.com/2022/day/13
I today’s prompt to be rather challenging. Not because the rules were
particularly complicated, but it took me a while to figure out how to
represent arbitrarily nested, mixed (list of more of self or numeric) data
types into a single vector that would capture each packet. In the end the
solution was to use an enum type (that I called Data) that can by the
T in a Vec<T> that is either another vector of Data items or a numeric
primitive. Note that I actually used a std::collections::VecDeque to
represent the list of other Data types as when doing the comparisons we
want to look at the front of the lists first. Using a Deque and then
mutating it to perform the comparisons is fundamentally the wrong approach
(sorting a list of elements shouldn’t also modify those elements) but it
does allow me to simply pop and element from both lists at the same time
and compare if I got back Some or None without needing to resort to
index and length checking before attempting to read each element. However,
this also caused problems in part two, as I couldn’t just run a normal
sort on an array of the packets, so instead I kept track of the original
string packet and then parsed it into the Data representation and ran its
order check on each pass of the loop inside of a custom insertion
sort loop. I chose insertion
sort as it’s easy to implement and even though it has a bad worst case
complexity the actual data set is small enough that I don’t expect properly
implementing quicksort or similar to make an actual difference.
Functions§
- The solution for the day thirteen challenge.