Advent of Code 2018 Day 2 Part 2 Linear time solution

day2.rs

pub fn task2_linear() {
    let input = utils::read_file("input/day02.txt");

    // first order of business: create a tree where each input line is sorted
    // into every nodes same_prefix, if the path leading from the root to that
    // has that prefix.
    let mut root = Node::default();
    for id in input.lines() {
        add_id_to_tree(&mut root, &id);
    }

    // find a match..
    let result = find_some_match(&root);
    println!("{:?}", result);
}

fn find_some_match(node: &Node) -> Option<String> {
    if let Some(result) = check_children_for_match(&node) {
        return Some(result);
    } else {
        for child in node.outgoing.values() {
            if let Some(result) = find_some_match(&child) {
                return Some(result);
            }
        }
        None
    }
}

/// Checks all IDs that have the prefix of this node if they are a match.
/// For this first for every child we look at its collected IDs - those
/// are the potential candidates, e.g. an ID that is in the 'e' child and
/// one that is in the 'f' child, if both have the same suffix.
///
/// We know that there is a unique match. Therefore we can sort out all
/// suffixes that appear more than once in a child node. Then we look at
/// all possible suffixes from all child nodes. If one suffix appears exactly
/// twice, we have a match.
fn check_children_for_match<'a>(node: &Node<'a>) -> Option<String> {
    let edges: Vec<_> = node.outgoing.keys().collect();
    // create a set of candidate suffixes for each edge
    let suffix_candidates: HashMap<char, HashSet<&str>> = edges
        .iter()
        .map(|c| {
            let mut suffix_count = HashMap::<&str, HashSet<&str>>::new();
            let ref ids = node.outgoing.get(&c).unwrap().same_prefix;
            for id in ids {
                suffix_count
                    .entry(&id[node.depth + 1..])
                    .or_insert(HashSet::new())
                    .insert(id);
            }

            (
                **c,
                suffix_count
                    .iter()
                    .filter(|(_, count)| count.len() == 1)
                    .map(|(suffix, _)| *suffix)
                    .collect(),
            )
        }).collect();
    // go over all suffixes and count their occurences. If # = 2, match!
    let mut suffix_counter: HashMap<&str, usize> = HashMap::new();
    for suffix_set in suffix_candidates.values() {
        for suffix in suffix_set {
            *suffix_counter.entry(suffix).or_insert(0) += 1;
        }
    }
    if let Some(suffix) =
        suffix_counter
            .iter()
            .find_map(|(suffix, count)| if *count == 2 { Some(suffix) } else { None })
    {
        Some(format!("{}{}", node.prefix, &suffix))
    } else {
        None
    }
}

#[derive(Default, Debug)]
struct Node<'a> {
    depth: usize,
    prefix: &'a str,
    same_prefix: HashSet<&'a str>,
    outgoing: HashMap<char, Node<'a>>,
}

fn add_id_to_tree<'a>(root: &mut Node<'a>, id: &'a str) {
    let mut current = root;
    current.same_prefix.insert(&id);
    for (i, c) in id.chars().enumerate() {
        {
            let mut next = current.outgoing.entry(c).or_insert(Node::default());
            next.depth = i + 1;
            next.same_prefix.insert(&id);
            next.prefix = &id[..=i];
        }
        current = { current }.outgoing.get_mut(&c).unwrap();
    }
}