DEV Community

Discussion on: AoC Day 5: Alchemical Reduction

Collapse
 
rpalo profile image
Ryan Palo

I originally had an iterative, while-loopy, pointer-based solution, and that ran OK, but like a lot of people, I realized that it's basically an extended version of the "Matching Parentheses" problem, and that a stack would let me iterate through the list more with less backward steps. Now it runs pretty quick!

Rust's lack of easy handling of upper- and lowercase characters kind of bummed me out.

Part 1

/// Day 5: Alchemical Reduction

use std::collections::HashSet;

// Part 1: How many units remain after fully reacting a polymer

/// Reduce down a polymer by dropping any mer pairs
/// 
/// A mer pair is any lowercase letter and its corresponding uppercase
/// letter, adjacent to each other
/// Optionally, provide a "drop_mer" to drop unconditionally, case insenitive
/// pair or not
pub fn reduce(polymer: &str, drop_mer: Option<char>) -> String {
    let mut result: Vec<char> = Vec::new();
    for c in polymer.chars() {
        if matches_drop_mer(c, drop_mer) { continue; }
        if result.last().is_some() && is_polymer_pair(*result.last().unwrap(), c) {
            result.pop();
        } else {
            result.push(c);
        }
    }
    result.into_iter().collect()
}

fn is_polymer_pair(first: char, second: char) -> bool {
    (first.is_lowercase() && second.is_uppercase() && 
        second.to_lowercase().next().unwrap() == first) ||
    (first.is_uppercase() && second.is_lowercase() &&
        second.to_uppercase().next().unwrap() == first)
}

fn matches_drop_mer(c: char, drop_mer: Option<char>) -> bool {
    drop_mer.is_some()
    && c.to_lowercase().next().unwrap() == drop_mer.unwrap().to_lowercase().next().unwrap()
}

Part 2

For part 2, I didn't iterate over all 26 letters of the alphabet no matter what, I used a set to figure out what characters were in the input and only loop over those. In this case, it doesn't help, because the input has all 26 anyhow. Oh well. I learned a lot about .collect() today.


// Part 2: Figure out which polymer, when removed, allows the most
// compacting, remove it, and return the length of the shortest polymer
// after compaction.

/// Optimizes a polymer by figuring out which *one* mer is inhibiting
/// reduction the most and removing it.  The reduced string is returned
pub fn optimize(polymer: &str) -> String {
    let possible_mers: HashSet<char> = polymer.to_lowercase().chars().collect();
    let mut result_candidates: Vec<String> = Vec::new();

    for mer in possible_mers.into_iter() {
        result_candidates.push(reduce(polymer, Some(mer)));
    }

    result_candidates.into_iter()
        .min_by_key(|candidate| candidate.len())
        .expect("No result candidates found.")
}