Just read the damn problem

Safety protocols clearly indicate that new pages for the safety manuals must be printed in a very specific order. The notation X|Y means that if both page number X and page number Y are to be produced as part of an update, page number X must be printed at some point before page number Y.

The Elf has for you both the page ordering rules and the pages to produce in each update (your puzzle input), but can't figure out whether each update has the pages in the right order.

For example:

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

The first section specifies the page ordering rules, one per line. The first rule, 47|53, means that if an update includes both page number 47 and page number 53, then page number 47 must be printed at some point before page number 53. (47 doesn't necessarily need to be immediately before 53; other pages are allowed to be between them.)

The second section specifies the page numbers of each update. Because most safety manuals are different, the pages needed in the updates are different too. The first update, 75,47,61,53,29, means that the update consists of page numbers 75, 47, 61, 53, and 29.

To get the printers going as soon as possible, start by identifying which updates are already in the right order.

Let's approach this badly shall we?

Right, read a list of predicates, followed by some input data, and check all the predicates match... simples!

Reading the text carefully, we can probably simplify this all down. I was originally considering creating curried functions, and building a list of them, and then applying them to the input data.

But actually in this case, the test is always the same, for each number, find all the rules with the start number and then process all the successor numbers against the rules. If there's an error, break out and invalidate the row. We can hardcode the processing itself, so the data structure can almost certainly just be tuples for the pairs, and then a vector for each update.

pub fn input_generator(input: &str) -> GeneratorResult {
    // Right parsing, we're going to parse lines until an empty line, and then we parse the results separately.

    let left: Vec<(u32, u32)> = input
        .lines()
        .take_while(|line| line != &"")
        .map(|line| match line.split("|").collect::<Vec<&str>>() {
            pair => (
                pair[0].parse::<u32>().expect("Numbers only"),
                pair[1].parse::<u32>().expect("Numbers only"),
            ),
            _ => (0, 0),
        })
        .collect();
    let right = input
        .lines()
        .skip_while(|line| line != &"")
        .skip(1)
        .map(|line| {
            line.split(',')
                .map(|num| num.parse::<u32>().expect("Numbers only"))
                .collect()
        })
        .collect();
    (left, right)
}

Right, to do part one, there's a number of ways to do it. The easiest, but most inefficient, is to go through the input list, one at a time.

Because we're looking for rules that accidentally have the wrong order, for example 75,97 when there's a rule 97|75 we want to walk backwards through the pages, and check that no page number violates a rule that it must come after.

That however requires walking both lists repeatedly, which is horrribly inefficient.

We could possibly preprocess the rules into a map, which would mean we could look up the current number, and see all the antecedents allowed.

This would turn rules:

75|29
75|53
97|29
97|53
75|47
97|75
75|61
75|13

into something more like this:

75 -> 29,53,47,61,13 97 -> 29,53,75

This would mean that we walk the input list, and for each number, check whether anything after the input number is in the list of numbers that should be after.

That's cleaner and more efficient. I also have a feeling there must be a helper to build a map from pairs of numbers...

Update: Ok, HashMap::from can take a list of key,value, but what it will do is replace duplicates rather than append them, so we'll have to do that by hand

pub fn map_from_pairs(pairs: Vec<(u32, u32)>) -> HashMap<u32,Vec<u32>> {
    let mut lookuptable:HashMap<u32,Vec<u32>> = HashMap::new();
    for (key,value) in pairs {
        lookuptable.entry(key).or_default().push(value);
    }
    lookuptable
}

We implement that, and get our answer and move on...

pub fn find_valid<'a>(
    input: &'a Vec<Vec<u32>>,
    table: &HashMap<u32, Vec<u32>>,
) -> Vec<&'a Vec<u32>> {
    let correct_pages: Vec<&Vec<u32>> = input
        .iter()
        .filter(|update| {
            let mut candidate_iter = update.iter();
            while let Some(candidate) = candidate_iter.next() {
                // Check that this number(candidate) is followed by any numbers that must follow it
                let mut check_iter = candidate_iter.clone();
                while let Some(check) = check_iter.next() {
                    if !table.get(candidate).unwrap_or(&vec![]).contains(check) {
                        return false;
                    }
                }
            }
            return true;
        })
        .collect();
    return correct_pages;
}

Part 2 - I give this my best shot

For each of the incorrectly-ordered updates, use the page ordering rules to put the page numbers in the right order.

Oh boy! We now need to reorder the lists that are not already correctly ordered.

Oh my. Ok, so firstly, we'll invert find valid to get us just the invalid results. We then need to "fix_result" for a single result, which will put it in order.

I honestly don't know how to approach this one in any way that is even slightly efficient. We could go through as we did before, and when we find a number that doesn't fit, we push it to the back, and try the next number etc.

But I'm not convinced that will actually work, as it wont handle some weird situations.

For example, given [1,2,3,4,5] and {1:4,5}, {2:1,3,4,5}, {3:1,2,3,4,5}, {4:5}, {5:}

• It would see 1, not be able to place it and put it to the back, giving [2,3,4,5,1]
• It would see 2, and that would be fine to place, giving [3,4,5,1]
• It would see 3, and that would be fine to place, giving [4,5,1]
• It would see 4, which can't have 1 in, so would go to the back, giving [5,1,4]
• It would see 5, which it can't see giving [1,4,5]
• It would see 1, and that would be fine to place, giving [4,5]
• It would see 4, and that would be fine to place, giving [5]
• and it would see 5 and place it, for a total of 2,3,1,4,5

Huh, maybe it would work... Let's try that

I think the biggest issue is probably catching an infinite loop, so I wonder if we use two lists, candidates and rejected. It would iterate through candidates, pushing them to rejected if rejected. When placing a number, it would then combine candidates and rejected and go again. If candidates is ever empty with rejected not empty, then we need to panic and error?

In the face of failing tests, I check the internet

Ok, That's not working. I cheated and took a look at Jeffs solution

This gives me the thing I was not intuiting (although I'm pleased to see that while not exact, we mostly approached the part1 mostly the same.)

The thing Jeff intuited is that you can compare two numbers, a and b, and determine based on the rules that if rules[a] contains b, then a must be less than b, but if rules[b] contains a then b must be less than a. That's a function that compares two numbers and says which is less, which can be used to implement a sort function

Edit: This was blindingly obvious in retrospect, and I don't know why I missed it. The problem repeatedly talked about getting the pages in order, so of course the answer here was to apply a sorting algorithm and all the rules are telling you is how to compare any two numbers in the list.

This results in much much cleaner code:

fn fix_result(updates: &Vec<u32>, table: &HashMap<u32, Vec<u32>>) -> Vec<u32> {
   let mut sortable_updates = updates.clone();
   sortable_updates.sort_by(|a, b| {
       if table.get(a).unwrap_or(&vec![]).contains(b) {
           // If the rules for a contains B then a comes before b
           Ordering::Less
       } else if table.get(b).unwrap_or(&vec![]).contains(a) {
           // Otherwise ff the rules for b contains a then b comes before a
           Ordering::Greater
       } else {
           // Otherwise, they're about equal so probably shouldn't swap
           Ordering::Equal
       }
   });
   sortable_updates
}

Retrospect

I feel like I cheated on this one, but I was well down into trying to design a new algorithm for moving the numbers around in order. That's something I'll have to try to remember in future, whether we are selecting from a known good set of common algorithms or not. Also... read the problem, and read it again!