Advent of Code 2021 - Day 8: Seven Segment Search (Original)

seven_segment_search.rs

fn count(notes: Vec<(Vec<&str>, Vec<&str>)>) -> usize {
    notes
        .iter()
        .flat_map(|(_, output)| {
            output
                .iter()
                .filter(|digit| [2, 4, 3, 7].contains(&digit.len()))
        })
        .count()
}
  
const P0: u8 = 0b1110111;
const P1: u8 = 0b0010010;
const P2: u8 = 0b1011101;
const P3: u8 = 0b1011011;
const P4: u8 = 0b0111010;
const P5: u8 = 0b1101011;
const P6: u8 = 0b1101111;
const P7: u8 = 0b1010010;
const P8: u8 = 0b1111111;
const P9: u8 = 0b1111011;
const P_ALL: u8 = 0b1111111;

fn decode(notes: Vec<(Vec<&str>, Vec<&str>)>) -> u64 {
    let possible_patterns: HashMap<usize, u8> = HashMap::from([
        (2, P1),
        (3, P7),
        (4, P4),
        (5, P2 | P3 | P5),
        (6, P0 | P6 | P9),
        (7, P8),
    ]);

    let mut total = 0;

    for note in &notes {
        let (patterns, _) = note;

        let mut letters: HashMap<char, u8> = HashMap::from([
            ('a', P_ALL),
            ('b', P_ALL),
            ('c', P_ALL),
            ('d', P_ALL),
            ('e', P_ALL),
            ('f', P_ALL),
            ('g', P_ALL),
        ]);

        for &pattern in patterns {
            for c in pattern.chars() {
                *letters.get_mut(&c).unwrap() &= possible_patterns[&(pattern.len())];
            }
        }

        for _ in 0..2 {
            let mut groups = HashMap::new();
            for &value in letters.values() {
                *groups.entry(value).or_insert(0) += 1;
            }

            for (group, count) in groups {
                if group.count_ones() == count {
                    for (_, value) in letters.iter_mut() {
                        if *value != group {
                            *value &= !group;
                        }
                    }
                }
            }
        }

        let chars = vec!['a', 'b', 'c', 'd', 'e', 'f', 'g'];
        let mut assigned = Vec::new();

        total += search(&letters, &chars, &mut assigned, note).unwrap()
    }

    total
}

fn search(
    letters: &HashMap<char, u8>,
    unassigned: &[char],
    assigned: &mut Vec<char>,
    note: &(Vec<&str>, Vec<&str>),
) -> Option<u64> {
    if assigned.len() == 7 {
        return check_permutation(assigned, note);
    }

    let mask = 1 << assigned.len();

    for &c in unassigned {
        if letters[&c] & mask != 0 {
            assigned.push(c);
            if let Some(result) = search(
                letters,
                &unassigned
                    .iter()
                    .filter(|&&ic| ic != c)
                    .copied()
                    .collect::<Vec<_>>(),
                assigned,
                note,
            ) {
                return Some(result);
            }
            assigned.pop();
        }
    }

    None
}

fn check_permutation(chars: &[char], note: &(Vec<&str>, Vec<&str>)) -> Option<u64> {
    let valid_patterns: HashMap<u8, u64> = HashMap::from([
        (P0, 0),
        (P1, 1),
        (P2, 2),
        (P3, 3),
        (P4, 4),
        (P5, 5),
        (P6, 6),
        (P7, 7),
        (P8, 8),
        (P9, 9),
    ]);

    let (patterns, values) = &note;

    let chars: HashMap<char, u8> =
        HashMap::from_iter(chars.iter().enumerate().map(|(i, &c)| (c, 1 << i)));

    for &pattern in patterns {
        let mut digit = 0;
        for c in pattern.chars() {
            digit |= chars[&c]
        }

        if !valid_patterns.contains_key(&digit) {
            return None;
        }
    }

    let mut total: u64 = 0;

    for &value in values.iter() {
        let mut digit = 0;
        for c in value.chars() {
            digit |= chars[&c];
        }

        total *= 10;
        total += valid_patterns[&digit];
    }

    Some(total)
}