Thank you so much for your explanation! I kind of found some clues looking up perp dot products & other vector math things, but this breaks it down very nicely.
I implemented your solution in rust, and part 2 failed by +447,761,194,259 (this was using signed 64-bit integers, i64). When I changed it to use signed 64 bit floating-point f64 and checked that the solution for x produces a whole number it worked.
This is a really excellent, clean solution! Would you mind breaking down how the piece of linear algebra works (for a shmo like me who doesn't remember that stuff frum school heh π )
Plus one for posteo. I've used them for several years now and have had no issues
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?
Ugh. Spent way too long on today's. Should have just used my own grid structure from last year. I will likely refactor to use that. Even though it's likely a super slow implementation, the convenience of dealing with it is better than shoehorning in the grid::Grid<T> from that crate.
solution (no supporting code)
use grid::Grid;
use crate::shared::{
grid2d::{iter_diag_nesw, iter_diag_nwse, Point},
util::read_lines,
};
fn parse_grid(input: &[String]) -> Grid<u8> {
let cols = input.first().unwrap().len();
Grid::from_vec(
input
.iter()
.flat_map(|row| row.chars().map(|c| c as u8).collect::<Vec<u8>>())
.collect(),
cols,
)
}
fn part1(grid: &Grid<u8>) -> usize {
let mut xmas_count = 0;
let rows = grid
.iter_rows()
.map(|d| String::from_utf8(d.copied().collect()).unwrap());
let cols = grid
.iter_cols()
.map(|d| String::from_utf8(d.copied().collect()).unwrap());
for diag in iter_diag_nesw(grid)
.chain(iter_diag_nwse(grid))
.filter_map(|d| {
if d.len() >= 4 {
Some(String::from_utf8(d.clone()).unwrap())
} else {
None
}
})
.chain(rows)
.chain(cols)
{
xmas_count += diag.matches("XMAS").count() + diag.matches("SAMX").count()
}
xmas_count
}
fn part2(grid: &Grid<u8>) -> usize {
let mut xmas_count = 0;
let valid = [
[b'M', b'M', b'S', b'S'],
[b'M', b'S', b'S', b'M'],
[b'S', b'M', b'M', b'S'],
[b'S', b'S', b'M', b'M'],
];
for x in 1..grid.cols() - 1 {
for y in 1..grid.rows() - 1 {
if grid.get(y, x) == Some(&b'A')
&& valid.contains(
&(Point::new(x as isize, y as isize)
.diagonal_neighbors(grid)
.map(|i| i.unwrap_or(0))),
)
{
xmas_count += 1;
}
}
}
xmas_count
}
pub fn solve() {
let input = read_lines("inputs/day04.txt");
let grid = parse_grid(&input);
println!("Part 1: {}", part1(&grid));
println!("Part 2: {}", part2(&grid));
}
And here's a link to the Github if you care to see the gross supporting code :D
Didn't do anything crazy here -- ended up using regex like a bunch of other folks.
solution
use regex::Regex;
use crate::shared::util::read_lines;
fn parse_mul(input: &[String]) -> (u32, u32) {
// Lazy, but rejoin after having removed `\n`ewlines.
let joined = input.concat();
let re = Regex::new(r"mul\((\d+,\d+)\)|(do\(\))|(don't\(\))").expect("invalid regex");
// part1
let mut total1 = 0u32;
// part2 -- adds `do()`s and `don't()`s
let mut total2 = 0u32;
let mut enabled = 1u32;
re.captures_iter(&joined).for_each(|c| {
let (_, [m]) = c.extract();
match m {
"do()" => enabled = 1,
"don't()" => enabled = 0,
_ => {
let product: u32 = m.split(",").map(|s| s.parse::<u32>().unwrap()).product();
total1 += product;
total2 += product * enabled;
}
}
});
(total1, total2)
}
pub fn solve() {
let input = read_lines("inputs/day03.txt");
let (part1_res, part2_res) = parse_mul(&input);
println!("Part 1: {}", part1_res);
println!("Part 2: {}", part2_res);
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_solution() {
let test_input = vec![
"xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))".to_string(),
];
let (p1, p2) = parse_mul(&test_input);
eprintln!("P1: {p1}, P2: {p2}");
assert_eq!(161, p1);
assert_eq!(48, p2);
}
}
Solution on my github (Made it public now)
Seriously can't agree more. Whatever small utility LLMs offer (I haven't used them in my day-to-day work at all because a regular search works for me just fine, and I can create my own images), it's not worth the incredible amount of resources used to perform a single query. Maybe if we had fusion energy and there were no environmental implications to further researching the theoretical limits of LLMs their use could be justified--but we don't, there are, so it can't.
I realized after I posted π thanks for pointing it out! I will go make it public
Turned out alright, I am looking forward to seeing what 2d coordinate grid code I can cannibalize from last year's solutions π
+1 for Ferris!
I did run your code as-is in an ipython REPL to check. These were the results:
REPL session
If you're curious to check against my puzzle input, it's here
Thank you again for the back & forth, and for sharing your solution!