aoc/year2015/
day19.rs

1//! # Medicine for Rudolph
2//!
3//! Part one is a brute force search and replace of every possibility with two optimizations.
4//! Replacements that add the same number of extra molecules are grouped together, as different
5//! length strings can never match.
6//!
7//! Next replacement ranges are sorted into ascending order. Non-overlapping ranges can never match,
8//! so checking for other equals string only needs to consider ranges that intersect.
9//!
10//! Part two uses the analysis from `askalski` provided on the
11//! [Day 19 solution megathread](https://www.reddit.com/r/adventofcode/comments/3xflz8/day_19_solutions/).
12use crate::util::hash::*;
13
14type Input<'a> = (&'a str, Vec<(&'a str, &'a str)>);
15
16pub fn parse(input: &str) -> Input<'_> {
17    let (replacements, molecule) = input.rsplit_once("\n\n").unwrap();
18    (molecule, replacements.lines().map(|line| line.split_once(" => ").unwrap()).collect())
19}
20
21pub fn part1(input: &Input<'_>) -> usize {
22    let (molecule, replacements) = input;
23
24    let mut groups = FastMap::new();
25    let mut modified = Vec::new();
26    let mut result = 0;
27
28    // Group replacements of the same size together.
29    for &(from, to) in replacements {
30        let extra = to.len() - from.len();
31        groups.entry(extra).or_insert(Vec::new()).push((from, to));
32    }
33
34    for (_, group) in groups {
35        // Build list of all possible modified strings.
36        for (from, to) in group {
37            for (start, _) in molecule.match_indices(from) {
38                let end = start + from.len();
39                modified.push((start, end, to));
40            }
41        }
42
43        modified.sort_unstable_by_key(|&(start, ..)| start);
44
45        'outer: for (i, &(start, end, to)) in modified.iter().enumerate() {
46            for &(start2, _, to2) in &modified[i + 1..] {
47                // Stop checking early once ranges no longer overlap.
48                if start2 >= start + to.len() {
49                    break;
50                }
51
52                // Compare replaced sections for equality.
53                let first = to.bytes().chain(molecule[end..].bytes());
54                let second = molecule[start..start2].bytes().chain(to2.bytes());
55
56                if first.zip(second).all(|(a, b)| a == b) {
57                    continue 'outer;
58                }
59            }
60
61            result += 1;
62        }
63
64        modified.clear();
65    }
66
67    result
68}
69
70pub fn part2(input: &Input<'_>) -> usize {
71    let (molecule, _) = input;
72
73    let elements = molecule.bytes().filter(u8::is_ascii_uppercase).count();
74    let rn = molecule.matches("Rn").count();
75    let ar = molecule.matches("Ar").count();
76    let y = molecule.matches('Y').count();
77
78    elements - rn - ar - 2 * y - 1
79}
aoc/year2015/day19.rs

aoc/year2015/
day19.rs
