median blog

Advent of Code 2024 Day 5 - Rust

Part One

I'd say this was the first day that needed some planning. We got a list of constraints in the form of X|Y where X and Y are numbers, and X|Y says that in a list, X must come before Y. We were also given many lists that we needed to test against. If a list passes all of the constraints, the middle element of that list is added to a sum.

Another was to look at X must come before Y in a list is to say 'Y must never be before X in the list'. This is a minor rephrasing but one that makes this problem a little easier. Given that phrasing, for every constraint we get, we can store a list of values keyed on X that can never be earlier in the list. In more concrete terms we store things in HashMap<i32, Vec<i32>> where the key is X and all the values of Y we see across the constraints make up the Vec<i32>.

Beyond that we just need to switch over to parsing comma separated lists after we encounter a blank line.

    let mut constraints: HashMap<i32, Vec<i32>> = HashMap::new();
    let mut lists: Vec<Vec<i32>> = Vec::new();
    let mut parsing_contstraints = true;

    for line in content.lines() {
        if line.len() == 0 {
            parsing_contstraints = false;
            continue;
        }

        if parsing_contstraints {
            let (a, b) = line.split_once('|').unwrap();
            let a_p: i32 = a.parse().unwrap();
            let b_p: i32 = b.parse().unwrap();

            constraints
                .entry(a_p)
                .and_modify(|v| v.push(b_p))
                .or_insert(vec![b_p]);
        } else {
            lists.push(line.split(',').map(|x| x.parse().unwrap()).collect());
        }
    }

Once parsing is done, we can run through each list and its elements. As we go through, we look up the relevant constraints for the element we're up to and check that none of those values appear before it.

    let mut total = 0;

    for list in lists {
        let mut clean = true;
        for (i, item) in list.iter().enumerate() {
            let d = constraints.get(&item);
            if let Some(right) = d {
                for check in right {
                    if list[..i].contains(check) {
                        clean = false;
                        break;
                    }
                }
            }
            if !clean {
                break;
            }
        }
        if clean {
            let half = (list.len() as f32 / 2.0).floor();
            total += list[half as usize];
        }
    }

If we had a lot of constraints or really long lists, this would probably be a little slow, but it worked well enough here.

Part Two

For part B, we need to reorder failing lists. This was a good chance to use Rust's Ordering implementation. If we found a list that failed, we sorted it. There are three possible outcomes when comparing two elements, a and b. First, b appears in the constraint list for a, which implies a>b. Second, a appears in the constraint list for b, which implies b>a. Last, the elements are considered equal if neither of those two apply. Bad input data could theoretically break this logic, but as will all things advent of code, I optimised for the day's puzzle, not for perfection.

            // applied if the list wasn't 'clean'
            let mut sorted = list.clone();
            sorted.sort_by(|a, b| {
                // Check for Greater
                let d = constraints.get(a);
                if let Some(right) = d {
                    if right.contains(b) {
                        return Ordering::Greater;
                    }
                }

                // Check for Lesser
                let d = constraints.get(b);
                if let Some(right) = d {
                    if right.contains(a) {
                        return Ordering::Less;
                    }
                }

                Ordering::Equal
            });
            let half = (sorted.len() as f32 / 2.0).floor();
            b_total += sorted[half as usize];

The complete solution can be found here.