pub fn y15d19p2(input: &str) -> u32Expand description
The solution for part two of the day nineteen challenge.
This was very challenging and I had to rely on inspiration from the
subreddit to figure out exactly how to solve this problem. As in part one
we start by parsing the problem input string to get our replacements and
molecule. Then we start a loop that we run until we reach e. The strategy
here is to work backwards from the end molecule to the start instead of
vice-versa as we’d need to implement a breadth-first-search or similar
which would quickly explode in how many checks that we need to do and how
long that it would take. Then we loop through all of the replacements
keeping track of how many times we’re able to make a substitution. When we
can’t make any more substitutions for that replacement (new == original)
then we move on to the next one. If, after processing all of the
replacements, the length of our “new” molecule after the replacements is
the same as the length of our “old” molecule before the replacements (i.e.,
we weren’t able to do any replacements) then we reset our molecule
replacement string back to the original, reset our substitution counter,
shuffle the replacements array, and try again. This is the insight that I
was able to get from the subreddit, it seems that many people took a
similar approach, but as I understand it, it is technically possible to get
a non-optimal solution however, it seems that based on many peoples’ inputs
there is actually only one path from e to the molecule so it should be
okay. Once we’ve reached e the loop ends and we can return the number of
substitutions that we made.
§Example
// probably read this from the input file...
let input = "e => A\ne => B\nA => BB\nB => AA\nB => AB\n\nAB";
assert_eq!(y15d19p2(input), 2);