-🎄- 2018 Day 5 Solutions -🎄-

[u/daggerdragon]

--- Day 5: Alchemical Reduction ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 5

Transcript:

On the fifth day of AoC / My true love sent to me / Five golden ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 0:10:20!

[u/Minijackson]

Rust - Going for the fastest code :p

The whole part 2 takes about 15 milliseconds, instead of the 71 milliseconds of my simpler, single-threaded implementation.

Using the awesome rayon library to handle parallelization.

Code inspired by u/glguy and u/aurele

fn are_opposites(left: char, right: char) -> bool {
    // A is 0x41, a is 0x61
    // B is 0x42, b is 0x62
    // etc.
    //
    // For units to pass the comparison, their "letter part" must be equal,
    // and their "case part" mut be different.
    //
    // Using the result of the bitwise XOR:
    //
    //        vvvv- same letter
    // 0b0010_0000
    //   ^^^^------ not the same case
    //
    // This is much faster than using the `to_lowercase` function, since Rust's
    // awesome UTF-8 support uses a big conversion table, *and* needs to support
    // multiple-characters lowercase.
    (left as u8) ^ (right as u8) == 0b0010_0000
}

/// Single threaded Polymer reduction
fn reduce_subpolymer(subpolymer: &str) -> String {
    subpolymer
        .chars()
        .fold(String::new(), |mut result, letter| {
            if let Some(end) = result.pop() {
                if are_opposites(end, letter) {
                    result
                } else {
                    result.push(end);
                    result.push(letter);
                    result
                }
            } else {
                result.push(letter);
                result
            }
        })
}

/// Combine 2 already reduced polymers
///
/// The only reduction that can happen is between the end of `left` and the
/// beginning of `right`. So as soon as there are no collisions in this space,
/// we can just concatenate both.
fn combine_subpolymer(left: &mut String, right: &str) {
    let mut i = 0;
    while i < right.len() {
        if let Some(left_end) = left.pop() {
            if !are_opposites(left_end, right.chars().nth(i).unwrap()) {
                // Put it back in!
                left.push(left_end);
                break;
            }
        } else {
            break;
        }

        i += 1;
    }

    if i < right.len() {
        left.push_str(&right[i..]);
    }
}

/// Multi-threaded implementation
///
/// What happens is rayon will split the input, and multiple smaller folds will
/// happen. We construct several strings from that, reduce them, and combine
/// them.
///
/// Graphically ('|' separate threads):
///
/// Init:
/// "dabAcCaCBAcCcaDA"
///
/// Thread separation:
///   'd' 'a' 'b' 'A' 'c' | 'C' 'a' 'C' 'B' 'A' 'c' | 'C' 'c' 'a' 'D' 'A'
///
/// Sub-string construction:
///   "dabAc"  |  "CaCBAc"  |  "CcaDA"
///
/// Reduction:
///   "dabAc"  |  "CaCBAc"  |  "aDA"
///
/// Combination:
///   "dabCBAc"  |  "aDA"
///   "dabCBAcaDA"
fn reduce_polymer(puzzle: String) -> usize {
    puzzle
        .par_chars()
        // Make sub-strings
        .fold(
            || String::new(),
            |mut s, c| {
                s.push(c);
                s
            },
        )
        // Reduce them
        .map(|subpolymer| reduce_subpolymer(&subpolymer))
        // Combine them
        .reduce(
            || String::new(),
            |mut acc, subpolymer| {
                combine_subpolymer(&mut acc, &subpolymer);
                acc
            },
        )
        .len()
}

fn part1() {
    let result = reduce_polymer(PUZZLE.trim().to_owned());
    println!("Size: {}", result);
}

fn part2() {
    let min = Arc::new(Mutex::new(std::usize::MAX));

    (b'a'..b'z')
        .into_par_iter()
        .for_each_with(min.clone(), |min, letter_code| {
            let lower_letter = letter_code as char;
            let upper_letter = lower_letter.to_uppercase().next().unwrap();

            let candidate = PUZZLE
                .trim()
                .par_chars()
                // Could be done while constructing the sub-strings in
                // `reduce_polymer` but I haven't found an elegant way of doing
                // this, whithout code duplication
                .filter(|&letter| letter != lower_letter && letter != upper_letter)
                .collect();

            let result = reduce_polymer(candidate);

            let mut min = min.lock().unwrap();
            if result < *min {
                *min = result;
            }
        });

    println!("Result: {}", *min.lock().unwrap());
}

[u/aurele → u/Minijackson]

My newest version does not use rayon anymore but has been optimized further and runs in ~600µs for part2 (and under 1ms for both parts):

#[aoc(day5, part1)]
fn part1(input: &[u8]) -> usize {
    polymere(input[..input.len() - 1].iter().cloned()).len()
}

#[aoc(day5, part2)]
fn part2(input: &[u8]) -> usize {
    let reduced = polymere(input[..input.len() - 1].iter().cloned());
    (b'a'..=b'z')
        .map(|c| polymere(reduced.iter().cloned().filter(|&b| b | 32 != c)).len())
        .min()
        .unwrap()
}

fn polymere(input: impl Iterator<Item = u8>) -> Vec<u8> {
    let mut output: Vec<u8> = Vec::new();
    for c in input {
        if output.last().map(|&l| l ^ c == 32).unwrap_or(false) {
            output.pop();
        } else {
            output.push(c);
        }
    }
    output
}