Advent Of Code @programming.dev CameronDev @programming.dev 4w ago

🖨️ - 2024 DAY 5 SOLUTIONS - 🖨️

Day 5: Print Queue

Megathread guidelines

Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
Where do I participate?: https://adventofcode.com/
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

You're viewing a single thread.

56 comments

Rust

Real thinker. Messed around with a couple solutions before this one. The gist is to take all the pairwise comparisons given and record them for easy access in a ranking matrix.

For the sample input, this grid would look like this (I left out all the non-present integers, but it would be a 98 x 98 grid where all the empty spaces are filled with Ordering::Equal):

   13 29 47 53 61 75 97
13  =  >  >  >  >  >  >
29  <  =  >  >  >  >  >
47  <  <  =  <  <  >  >
53  <  <  >  =  >  >  >
61  <  <  >  <  =  >  >
75  <  <  <  <  <  =  >
97  <  <  <  <  <  <  =

I discovered this can't be used for a total order on the actual puzzle input because there were cycles in the pairs given (see how rust changed sort implementations as of 1.81). I used usize for convenience (I did it with u8 for all the pair values originally, but kept having to cast over and over as usize). Didn't notice a performance difference, but I'm sure uses a bit more memory.

Also I Liked the simple_grid crate a little better than the grid one. Will have to refactor that out at some point.

solution

use std::{cmp::Ordering, fs::read_to_string};

use simple_grid::Grid;

type Idx = (usize, usize);
type Matrix = Grid<Ordering>;
type Page = Vec<usize>;

fn parse_input(input: &str) -> (Vec<Idx>, Vec<Page>) {
    let split: Vec<&str> = input.split("\n\n").collect();
    let (pair_str, page_str) = (split[0], split[1]);
    let pairs = parse_pairs(pair_str);
    let pages = parse_pages(page_str);
    (pairs, pages)
}

fn parse_pairs(input: &str) -> Vec<Idx> {
    input
        .lines()
        .map(|l| {
            let (a, b) = l.split_once('|').unwrap();
            (a.parse().unwrap(), b.parse().unwrap())
        })
        .collect()
}

fn parse_pages(input: &str) -> Vec<Page> {
    input
        .lines()
        .map(|l| -> Page {
            l.split(",")
                .map(|d| d.parse::<usize>().expect("invalid digit"))
                .collect()
        })
        .collect()
}

fn create_matrix(pairs: &[Idx]) -> Matrix {
    let max = *pairs
        .iter()
        .flat_map(|(a, b)| [a, b])
        .max()
        .expect("iterator is non-empty")
        + 1;
    let mut matrix = Grid::new(max, max, vec![Ordering::Equal; max * max]);
    for (a, b) in pairs {
        matrix.replace_cell((*a, *b), Ordering::Less);
        matrix.replace_cell((*b, *a), Ordering::Greater);
    }
    matrix
}

fn valid_pages(pages: &[Page], matrix: &Matrix) -> usize {
    pages
        .iter()
        .filter_map(|p| {
            if check_order(p, matrix) {
                Some(p[p.len() / 2])
            } else {
                None
            }
        })
        .sum()
}

fn fix_invalid_pages(pages: &mut [Page], matrix: &Matrix) -> usize {
    pages
        .iter_mut()
        .filter(|p| !check_order(p, matrix))
        .map(|v| {
            v.sort_by(|a, b| *matrix.get((*a, *b)).unwrap());
            v[v.len() / 2]
        })
        .sum()
}

fn check_order(page: &[usize], matrix: &Matrix) -> bool {
    page.is_sorted_by(|a, b| *matrix.get((*a, *b)).unwrap() == Ordering::Less)
}

pub fn solve() {
    let input = read_to_string("inputs/day05.txt").expect("read file");
    let (pairs, mut pages) = parse_input(&input);
    let matrix = create_matrix(&pairs);
    println!("Part 1: {}", valid_pages(&pages, &matrix));
    println!("Part 2: {}", fix_invalid_pages(&mut pages, &matrix));
}

On github

*Edit: I did try switching to just using std::collections::HashMap, but it was 0.1 ms slower on average than using the simple_grid::Grid... Vec[idx] access is faster maybe?

I think you may have over thought it, I just applied the rules by swapping unordered pairs until it was ordered :D cool solution though
- Good old bubble sort
  
  Its called AdventOfCode, not AdventOfEfficientCode :D
Very cool approach. I didn't think that far. I just wrote a compare function and hoped for the best.

56 comments