bendns' repos / aoc
heh
d15
Browse Source
bendn 2023-12-15
parent 2f6af2a · commit 62437c0
Diffstat
-rw-r--r--.gitignore3
-rw-r--r--Cargo.toml1
-rw-r--r--src/inp.txt101
-rw-r--r--src/main.rs139
-rw-r--r--src/util.rs24
5 files changed, 67 insertions, 201 deletions
diff --git a/.gitignore b/.gitignore
index 5f3f59c..15fe0ea 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,6 @@
+callgrind.*
+perf*
+flamegraph*
/target
Cargo.lock
before
diff --git a/Cargo.toml b/Cargo.toml
index 14af4b6..c5480b9 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -6,6 +6,7 @@ edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
+arrayvec = "0.7.4"
itertools = "0.12.0"
memchr = "2.6.4"
[profile.release]
diff --git a/src/inp.txt b/src/inp.txt
index d7b3e85..62f7ed0 100644
--- a/src/inp.txt
+++ b/src/inp.txt
@@ -1,100 +1 @@
-O.OO.#...#.O#...#...O..O.#O..O.##.....###O.O##O.O....OO.....##..##.#..O#.........O#..#..O...#O.....O
-.....###.O....#.#O.....##..O##O.......##......O..#..##.#.O#...O...O.O....#.###O.OO#.#O.#.#..O..OOO..
-OO......#.#..##O........O.###..#.#........O#..O....O#.#.##.OO.....O#.........###O......#..#.O..#....
-..#O...O....#.#.#O#....#.O#....OO.OO.O#...O##.O........O.#O.OO.O.....O.#.O.#....O.....O..OO.OO...O.#
-..#O...#.....O#O...###O......O#.##O..O#.O.O.#..#O#.O....O..O#...OO...O..#.O.......O.##OO.#...#...##.
-.#......O.OO#....O#O#OO.O..O......OOO..O....O....#OO....O...#.O.O.O..O...OOOO...#......O..#O..#O....
-..O.#.O.#..OO...........#..#......#.#...#...O...#...#...O##..O..#..O.#...O..#.O...#....#..OO..O..#.#
-.##..O..##O......#...##....#..#..O....#..##.#.O#....O#..#...O.O....O.O.........OO.#.OO......O.......
-..##O.O...O.O..O##OO..#.O..O.#...O..#..#.O...O....##...#O...O......#.....O##O#..O.#..#..O...#...#.O.
-O..##...##...#.#.OO#...OO#O..O...O.#O..#.O......O##......#O..O..OOOOOO..O.##.O...#O.....O##......OO.
-.........O..O#.....#...#......OO###OO.O.O#...#.O....O..##..O#.....O.#.##O.#......#.O.....OO#.#..##O.
-OO#O...#...OO.O####.OO.#.#.......O......O#..O#..#...#O....#.....OO#O......#O#...O#.OO......O....O#..
-.O.........#.#O#....#OO..#.........OO....O...#.O.O.O.OOO.O..O.....O.#....OOOO....OO.......#.#.O.##..
-....#.....#.O.#O...O#OO#...##.#.#..O.O.O....#O.#.#.O...#O#O.O#O...O..#OO..O###.OO..#.....OOO.#......
-#OOO..OO.O.O..O..O....#....O..O.#...O...O...##.O##..O...OOOOO#.........OOO##..#...OO#O#O.....O...##.
-.......O#..#OO.O.O..OO.O#..O.......##....OO#.O..O..O#...#..#...O.##.....#..........#.....#.O...#...O
-......O.#.O...O.......O#..O..OOO#...#........###.O..#....O.O#.OO.O..#.O#O.O.O.......O.##.OO......O.#
-O....O..........#....##.###..#...O#.O..O.##.O....O..O..O..##.O.O#OO...O.#.O##..#.#.......#.O..O..O.O
-..O#..O.#.##..O#..O#..O..O..O....OO...O##..#...O.OO..#.#.#.###O.O...#O.##..#.....#..#O.O.O...#O.O#..
-..O.##........OO.....OO.O..#.....OO.O..#...#..OOO..#....#....#.OO.#.#........OO...O.#O....##O..OOOO#
-.........#.#.OO.#O...#...O#........O..#.#........O......O#.OO..#..#....O##OO.......O..O.O.O.........
-#..O..#..OO.O.O....O..O.O.#.O.O#O...O.OO..#......OO.#..O....#.....#OOO#.OO#.OO........###....O.....O
-..O..O.O.O.....O..#.O..##.O..##..O###........O.O..#...O....OOO#.OO.#O...O..##....#.#O...#..O...O...#
-O#...O..O.#.#......O..O.#OO.....O..#.......O.##O........#O.OO..#..O.##..O.#...O...#O.....#.#..OO##..
-O.OO..O....O.#..O##O.#.O.O#O..##...O..##...#.O#.....O##.#O..O.O.....O....##..O.###......#........O..
-.....##.#.......O.OO....#..##............##..O..#.......O..O..#.O...O#..O.O.##..O..OO.O.....O...O...
-##.O.#....O..OO..OOO.OO.##..OO.OO.#...O#.....#...##...O#....OO..O.O...O...O.#....OO...#..#O#.##..#..
-........OOO....O...#.O...O..#......O....#O#.#O...O#.O........O.O...OO#....O..#.#.#O.O...OO....O.#O..
-OO...O...O..#.OO..O#.OO###..O.......#..O..O.####O....O.O.O#O.#..O..##OO..O..#....#..O#O....#..O...O.
-..O....#.O.O....O...#.........#..O#.#..OO....#...##.OO..OO.O...OOO..O..O#.###.......O#...#....OO...#
-.O...OO.O.O...#.......#.O.O.....O...OOOO.#O.O..O..OOO.OO...............#O...##O..OOO##....#O.O#.##..
-O....O...O.#...........#..#.#OO###O.O...#.O#..O.....O...O....O...#...O.OOO.OO#..OO...#..OOOO...#..#.
-....O...OO.#.O...O..#....O.O.#O..O....O..O..##O.#O....O..O.....O.......OO.......#OO#.##.O.#.O..#.##O
-#OO#.#....###O#..OO..#..O.......O.O...OO#.#O.....O.O##.O...#.##O#...O#......#..#..O#O.O.....OO.O#.O.
-...O#....O...O......#..O#O..OO.O#.OO.#.......#...O..O.....O.#O..O..O.....#OO#.O..#....#O.#O..#......
-..O.....O.......#O....O#...##.....#..O.#....#.#.#O#.#....O....#..O.O......OO....O.#OO#OO.....O......
-.#..O..#..O##...#O.#.##O#.#.#O....O#..###.OO..##..#..........O#O.#..#....O...##.......O.O.O##O#..#O.
-.#.....O..O.#..#..O....O...#.....#O.O.....OO.#..#......##........O.#.#......#...OO#....O#O.....#..O#
-#.....O.....O...O..##O.OO#OO......O#..O......O...O...#.....OO..#...O..#.....##.#.O...#..#O......OO.O
-.#..#.#.#...O#.......#.O....O..#.#.#.....O...................#.O...OOO#.....O.O.....O..O.#.....#.O.O
-O....O.....O.....O#O...O.O.O#O.#O..OO#OO..#OO.OO##.....##O#.O.O..#.....O..OO.##.#.......#...O..OO.O.
-.O#..O..#....##......O....#.#.#......#........##...#....#.......#.....O......##.#.....O.O....OO#.O..
-....OO.OO#...O..#O#O.#.O.#..OO...OOO...#O.#..#..#.#O...#O.#.O..##..O.##..O#.#.....#..O...#.O...O#.O#
-....O#....O.O#OOO...#.#.........O.O....#..O...#...#.....O.O.O.O....#.OO.##O.....#.#.#.#O..O#.O.#.OOO
-O#OO..O.#.......###..OO..O........O.##O.#O##..O...O.#OO.....#...O......O.OO...O..OO....O..O..#.#...O
-.#.O.O.O.#......O......##O...OO.....O....O#.....O#....#.......#O..#...##..O..#O.O.O..O....O.........
-...#.........OO..O.O#..O.#....#...OO##...O..OO.......#.#OO..#...#..##.#...OO#...#O.#...O.....O...#..
-#.....#O......O....O#.....#.#O.OO..........O.O...#....#.###O.O..O...#...#..#....O..O..O#.O.........#
-O.O.O...O...#.....#.#....O.O.O.....OO....#..OOO......O.O.......O#O...#.#O##O.####.........O#O.......
-O.O...........O#...OO..#O.O.O......O.......##.O...O..##...O.#OO...#OO...#...#O#.##O.#......O.##....O
-O..#...........O..O......OOO....#....OO.O...#O..O.O#......#...........#O...#O..O....#.#.#..#...#O...
-..O.....#...#...O.#.O..##.........O#..##.....#O.........................##...#.#..#.OO#O...#OOO#O.##
-OO..O.O.....O#.O....O##...O.O#.OO.#..O.....O...##.O#..O......OO..#..O.....##.....OO#OO...#O......O.O
-.OO...#....#O..#.....OO..O.O.......O#...O#..O#..#.O....#.O.#.O...O.#.O.#...#..OO.......O#....OO..O..
-O.OO..#.OOO.#.O#...#.#..O..O#.#.#.#.....#.O#..O....O..OO...O..#..#....OO#O.#......O#..##...O...O.#O.
-....#....#...OO#...O.O#OO.#.#OOO..O...OO.O..#.O#..#..O.O..#.#........OO#O.#.#.#.....OO......##.#.O..
-.#.O.OOO#OOO...##O#.#...#...##O.#...O.......###O#.##..O#..#.##...O..O.O.........O..#..O##......#.##.
-O...#..#....#O..##..O.O##..O.O###O.......O...#.O#.O#..O...#.#.O..#.....#.....O..O..OOO.OOO..O..OOO..
-...O#.O....O.O.#.O..#.O..####...OO......#OO....O#....O..O...O...OO..OO.OOO#....#..#.O.O..#..#.....O.
-O.O##O.O.O.#.O.#........#O......#O.##...##OO.......O#..#..#.O....OO........#.#O..#O.........OO.O#..O
-.......#.....O...O.O.#O##.O.OO#.....O.O#O....O.#.##.#.......##.O.O.###O...O.O#O##...#...#...O..#....
-.O#...#O...#....O##.O..........O.O.#..O.O..OOOOO.......OO.O#...O...O...#O###OOO.#OOO..............O#
-O.#.#.......OO..OO.#.O#.....#.O#O...#......O....O...O.O.....OO.#O.......#..O...O.....##OO#.....OO#.#
-...O#...#.....#..#O.#..O..O.#O#O.#...OO#O.O....O.#...#O#O....#......O..#O...#....O..O.O........#..#.
-.O.......#..O#...O....................#.##O......#.#......####..OO#...OO.##..#........#.OO..#OOO.###
-......O...O..O##.......O...O##O.O....#..#.##...#OO..##..........#..............##O.......O...#O###O.
-.........#..OO.#.......OO...O....#O.#.......O..##...###..O...#OO.O.O...#...#OO....##O.....#O.O..#...
-..#....O..O......#.#....OO#....#...O.#.OO.O#.....O#.#......O.#O.........O....O....#..O.........O....
-.OO.......#.....O.O..O#....O.#.....O..O#O...O#.....OOO....##..O.O..O#.OO...#....#...O..#..##..#..#.O
-O..#..OO##.#..OOO..#...#.OOO..O..##..O..##O.......O.O..O...#.O...#..###.#.#.#...#O..O......#.O#....#
-...O..#O..O..OO.#....#...##...O...#.......OOOO#...O.###.O.......#O.O#.##.##O..#...O...O.O..#....OO..
-OO.........OO...O.O............O....O.O...O.O.O.......O.OOO.O#....#O.O..#.....O#...#...#....#......O
-#.OO#........OO..#OO.....O.#...#..#O.O...O.....#..O.......O...O..O...O.O.O....##...O....O.OO.....#.O
-..O....#..O....O#.....#..#O......O......#...#O.......O.O...##O.#...O#..O#.#O###...#.OOO.#O...O#....O
-.#.#..OO.#..O###....O.#......O..OO...O.O..O.#.O....O.#..O.....O#....O....#.......O.O...O......OOO.#.
-...OO#.OO#O....O....O.O.#.O.#O..#.O#...###...#......#...OO##.#.#..O#...#....#.#.#.OO....O...OOOO...O
-..O.#..O...O...O#O......##.....O...O..O....#....O..#OO.#.O......#O.OOO.O.O..#........##...#O.#O...O.
-..O.OO.....O...#..O..#...O...O..#O..O#..##.....#....#.#O.#.......#O##....O.OOOOOOOO#.O...O.O#..#O##.
-O.OO.####..OO...OO.O........OO#.O.O...#....#..OO......O.O...O..#.##....O....O......#O........#O.O#..
-.#O.#...#.#...OO#.O.#O.....O##.O.OO.O..#..#O.....O...#.O.O#.....###.....#O.O.......O.#O.O#..#.O..#..
-.O......O........O...#O....##.....#O..OO.O..#.....O.#..O...#O#.#..##.#O..........O.O.O..#....#..#..#
-.OOO..O...#O.O#..#....O......O.O...O#O.....#..OO......OO.#O..O..O###......O.#.#.#.O....#...O........
-.##.....#OO#.##.....#....O..O.....OO..OO##...O...O#.##.OO#....#.......#...O.O.#.O........OO...OO....
-......OO#.....OO#OO......#.O....##..O.O#...O....#..O.O.#O.#...#.O..#.O.O#O....O.O..O.O.O.#OO.##.OO.#
-.O..OO##....O###......####.OO...O#..#..##.##.O..#..##OOO...#..#O##.#..#........#...#....O.......#.OO
-..O..O.O..#....#.#O.#.#OOO....O.##.....OO....#..O...#...#O.........O....O..#..........#.O..O.OO.O##O
-OO.......#...O#.#.......O...O.OO#.O.O.....O.....#...##..#....#.......O#.#O..O.O.......##...OO..#O...
-#O#....#.#.O..#...OO...##.#.#.O#O#...#........O..OO..#..O#..O..O.O.#O...#.....#O.#O.O#..OOO#.O.O..#.
-.#O...OO.##.#.....O...O#O................O.O..O#...#..O.#OO..O....OO...O.#...O#.#.O...O#....OO#.#...
-O#...###.OO.O...O.O#O#..O.O...O.#.....O......O...#...O.O....#...O...O#.#...##....O...........#O...#.
-.....#OO.#.OO...##.O....#OO#.....O..##...OO#.......O...##..#....#..#..##.#O.O##..O.#.O.#.O#OO.O.#.#O
-O##.#..O.OO..O.O.OOO.O...O..O.O..O.O.O..#.........#.....OO.#.......O#....#.......#O.#.O..#...O#..OOO
-.#....O.O..O##...#.OO#.O#..#OO..O.#...O....##.#O.O#O#...#.........O.#..#....OO..O.#........##O.##O..
-.....#....OO#...#.OO.O.O....O..#O.#.O#.O##.O..#.#O.#..O.#.O..O#.#.O.O.O#O....OO#...O......OO#..OO#O.
-O..O.#O..OOO..O...O...#.......#O.OO....O..#...O.....O.#.OO....#.O.OO...O#...OOO###.O..#.....O..O#.#.
-.OO......O#O.......OOO.......O..O...........O..##.....OO..##...O.O.O...O.O.O.....O..OO..O#....#.O..#
-O....#....#O.####.O...#....O....#O..#O...O.O....O.O#..O.........O#.......O....O..O...#.##..O.OO.OO..
-.O###O...#OO.OO........O.O#.O.O....O.O...##.O#..###..........#..O#.O..O.OO.O..#O#OO..O#.O.##.O.OOO##
-#.#O#..O.#...O#..#.......O#..#...#...#O..#.O.....O...O.......#O.#...#OO.O....OO..O...#.#....#O......
-..O.#O.O.O#..#.O...#.....#..O..##..O......O.OO.O.###.....#.O..O...OO#.OO.....#...OO#O..#..#O#...O..O
+rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7 \ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index ebea405..17c30a3 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,5 +1,6 @@
#![allow(confusable_idents, uncommon_codepoints, mixed_script_confusables)]
#![feature(
+ inline_const,
slice_flatten,
iter_collect_into,
let_chains,
@@ -15,112 +16,60 @@
)]
extern crate test;
pub mod util;
-
+use arrayvec::ArrayVec;
pub use util::prelude::*;
-pub fn p1(i: &str) -> usize {
- let mut mat = Vec::with_capacity(100);
- let mut i = i.as_bytes();
- for _ in 0..100 {
- mat.push(unsafe { <&[u8; 100]>::try_from(i.get_unchecked(..100)).unwrap() });
- i = unsafe { i.get_unchecked(100..) };
- if i.len() != 0 {
- i = unsafe { i.get_unchecked(1..) };
- }
- }
- let mut rows = [0u8; 100];
- for j in 0..100 {
- let mut count = 0;
- for i in 0..100 {
- if *unsafe { mat.get_unchecked(i).get_unchecked(j) } == b'O' {
- *unsafe { rows.get_unchecked_mut(count) } += 1;
- count += 1;
- } else if mat[i][j] == b'#' {
- count = i + 1;
- }
- }
- }
- rows.iter()
- .ι::<usize>()
- .map(|(&x, i)| (x.nat()) * (100 - i))
- .sum::<usize>()
+pub fn hash(s: impl AsRef<[u8]>) -> u8 {
+ s.as_ref()
+ .iter()
+ .fold(0u8, |acc, &x| acc.wrapping_add(x).wrapping_mul(17))
}
-fn pushhhh(mat: &mut Vec<[u8; 100]>) {
- for j in 0..100 {
- let mut count = 0;
- for i in 0..100 {
- let curr = C! { mat[i][j] };
- mat!(curr {
- b'O' => {
- C! { mat[i][j] = mat[count][j] };
- C! { mat[count][j] = curr };
- count += 1;
- },
- b'#' => count = i + 1,
- b'.' => {},
- });
+pub fn p2(i: &str) -> u32 {
+ let mut 品 = [const { ArrayVec::<_, 10>::new_const() }; 256];
+ for i in i.as_bytes().split(|&b| b == b',') {
+ match i.split_once(|&b| b == b'=').map(|x| x.mr(|x| x[0] - b'0')) {
+ None => {
+ let ι = &i[..i.len() - 1];
+ let h = hash(ι);
+ let β = &mut 品[h.nat()];
+ β.retain(|(α, _)| *α != ι);
+ }
+ Some((ι, κ)) => {
+ let h = hash(ι);
+ let bx = &mut 品[h.nat()];
+ if let Some((_, σ)) = bx.iter_mut().find(|(α, _)| *α == ι) {
+ *σ = κ;
+ } else {
+ unsafe { bx.push_unchecked((ι, κ)) };
+ }
+ }
}
}
+ 品.into_iter()
+ .ι1::<u32>()
+ .map(|(bx, i)| {
+ bx.iter()
+ .ι1::<u32>()
+ .map(|(&(_, x), j)| x as u32 * j)
+ .sum::<u32>()
+ * i
+ })
+ .sum::<u32>()
}
#[no_mangle]
-pub fn run(i: &str) -> impl Display {
- p2(i)
+pub fn p1(i: &str) -> impl Display {
+ i.as_bytes()
+ .split(|&x| x == b',')
+ .take(4000)
+ .inspect(|x| shucks!(if x.len() > 8))
+ .map(|x| hash(x) as u32)
+ .sum::<u32>()
}
-fn weigh(mat: &[[u8; 100]]) -> u32 {
- mat.iter()
- .ι::<usize>()
- .map(|(row, i)| (util::count::<100>(&row, b'O') * (100 - i)) as u32)
- .sum()
-}
-
-pub fn h(data: &[u8; 10000]) -> u16 {
- let mut buffer = 509;
- let mut data = &data[..];
- while data.len() > 16 {
- let (value, rest) = data.split_at(16);
- let [a, b]: [u64; 2] = unsafe { rint(<[u8; 16]>::try_from(value).unwrap()) };
- buffer ^= a.wrapping_mul(b) ^ a;
- data = rest;
- }
- (buffer ^ buffer.swap_bytes()) as u16
-}
-
-fn hash(x: &[[u8; 100]]) -> u16 {
- h(&unsafe { *x.as_ptr().cast() })
-}
-
-pub fn p2(i: &str) -> impl Display {
- let mut mat = Vec::with_capacity(100);
- let mut i = i.as_bytes();
- for _ in 0..100 {
- mat.push(unsafe { <[u8; 100]>::try_from(i.get_unchecked(..100)).unwrap() });
- i = unsafe { i.get_unchecked(100..) };
- if i.len() != 0 {
- i = unsafe { i.get_unchecked(1..) };
- }
- }
- let mut map = vec![(hash(&mat), weigh(&mat))];
- loop {
- for _ in 0..4 {
- pushhhh(&mut mat);
- let mut new = vec![[0; 100]; 100];
- for row in 0..100 {
- for col in 0..100 {
- C! { new[col][99 - row] = mat[row][col] };
- }
- }
- mat = new;
- }
- let c = hash(&mat);
- if let Some(y) = map.iter().position(|&(x, _)| x == c) {
- let c = map.len() - y;
- return C! { map[y + (1e9 as usize - y) % c] }.1;
- }
- map.push((c, weigh(&mat)));
- }
+pub fn run(i: &str) -> impl Display {
+ p1(i)
}
fn main() {
diff --git a/src/util.rs b/src/util.rs
index ee4eb7f..e2540c4 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -58,6 +58,22 @@ macro_rules! shucks {
unsafe { std::hint::unreachable_unchecked() }
}
};
+ ($fmt:literal $(, $args:expr)* $(,)?) => {
+ if cfg!(debug_assertions) {
+ unreachable!($fmt $(, $args)*);
+ } else {
+ unsafe { std::hint::unreachable_unchecked() }
+ }
+ };
+ (if $x:expr) => {
+ if $x {
+ if cfg!(debug_assertions) {
+ unreachable!();
+ } else {
+ unsafe { std::hint::unreachable_unchecked() }
+ }
+ }
+ };
}
pub(crate) use shucks;
@@ -277,7 +293,7 @@ impl Μ for &[u8] {
let i = self
.iter()
.position(|&x| x == d as u8)
- .unwrap_or_else(|| panic!("{} should split at {d} fine", self.p(),));
+ .unwrap_or_else(|| shucks!("{} should split at {d} fine", self.p()));
(&self[..i], &self[i + 1..])
}
@@ -307,7 +323,7 @@ impl Μ for &[u8] {
impl Μ for &str {
fn μ(self, d: char) -> (Self, Self) {
self.split_once(d)
- .unwrap_or_else(|| panic!("{self} should split at {d} fine"))
+ .unwrap_or_else(|| shucks!("{self} should split at {d} fine"))
}
fn μκ<T: FromStr>(self, d: char) -> impl Iterator<Item = (T, T)>
@@ -511,7 +527,6 @@ impl<T, I: Iterator<Item = T>> GreekTools<T> for I {
}
pub trait TupleUtils<T, U> {
- fn map<V, W>(self, f: impl FnOnce((T, U)) -> (V, W)) -> (V, W);
fn mr<W>(self, f: impl FnOnce(U) -> W) -> (T, W);
fn ml<V>(self, f: impl FnOnce(T) -> V) -> (V, U);
fn rev(self) -> (U, T);
@@ -551,9 +566,6 @@ impl<T> UnifiedTupleUtils<T> for (T, T) {
}
impl<T, U> TupleUtils<T, U> for (T, U) {
- fn map<V, W>(self, f: impl FnOnce((T, U)) -> (V, W)) -> (V, W) {
- f(self)
- }
fn mr<W>(self, f: impl FnOnce(U) -> W) -> (T, W) {
(self.0, f(self.1))
}