Diffstat (limited to 'src/lib.rs')
| -rw-r--r-- | src/lib.rs | 242 |
1 files changed, 153 insertions, 89 deletions
@@ -29,109 +29,173 @@ hint_assert_unchecked )] mod util; -pub mod day22 { +pub mod day23 { use super::util; use super::util::prelude::*; - - pub fn mod10(a: u32) -> u32 { - const D: u32 = 10; - const M: u64 = (u64::MAX / D as u64) + 1; - (M.wrapping_mul(a as u64) as u128 * D as u128 >> 64) as u32 + #[no_mangle] + pub fn part2(x: &str) -> String { + let g = Graph::load(x); + let x = g.mxq(); + let mut i = 0; + const c: u8 = b','; + static mut out: [u8; 38] = [ + 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, c, 0, 0, + c, 0, 0, c, 0, 0, c, 0, 0, + ]; + for j in 0..WORDS { + let mut x = x[j]; + while x != 0 { + let bit = x.trailing_zeros(); + unsafe { + out[i + i * 2..i + i * 2 + 2] + .copy_from_slice(&C! { NAMES[64 * j + bit as usize] }) + }; + i += 1; + x &= !(1 << bit); + } + } + unsafe { String::from_utf8_unchecked(out.to_vec()) } } - fn next(mut x: u32) -> u32 { - x ^= (x * 64) & 16777215; - x ^= x / 32; - x ^= (x * 2048) & 16777215; - x + fn part1(x: &str) -> u32 { + let adj = Graph::load(x).adj; + let mut has = [false; 676]; + let mut sum = 0; + for computer in 494..=519 { + has[computer] = true; + let nbors = Graph::adj_on(adj[computer]); + for (&elem2, i) in nbors.iter().ι::<usize>() { + for &elem3 in &nbors[i..] { + if !has[elem2] && !has[elem3] && adj[elem2][elem3 / 64] & 1 << (elem3 % 64) != 0 + { + sum += 1; + } + } + } + } + sum } + struct Graph { + // vert: [[u8; 2]; SIZE], + adj: Box<[[u64; WORDS]; SIZE]>, + } + const SIZE: usize = 676; + const WORDS: usize = (SIZE + 63) / 64; + fn h([a, b]: [u8; 2]) -> usize { + a as usize + 26 * b as usize + } + const NAMES: [[u8; 2]; 676] = include!("../lut2"); - #[rustfmt::skip] -// 8051 -fn next2000(n: u32) -> u32 { - let n = n as u64; - let m = n | n << 24; - let r = (m & 0x61a765) ^ (m >> 1 & 0xc2f82d) ^ (m >> 2 & 0x286d53) ^ (m >> 3 & 0x44f679) - ^ (m >> 4 & 0x4d6be8) ^ (m >> 5 & 0x118005) ^ (m >> 6 & 0x5f19f2) ^ (m >> 7 & 0xf03667) - ^ (m >> 8 & 0xcea653) ^ (m >> 9 & 0xafa201) ^ (m >> 10 & 0xfd0d29) ^ (m >> 11 & 0x949200) - ^ (m >> 12 & 0x49a994) ^ (m >> 13 & 0x21673) ^ (m >> 14 & 0xb4c5bf) ^ (m >> 15 & 0x1e0aaf) - ^ (m >> 16 & 0x7cab00) ^ (m >> 17 & 0x95ba48) ^ (m >> 18 & 0x49f04c) ^ (m >> 19 & 0x9a8320) - ^ (m >> 20 & 0xb69d39) ^ (m >> 21 & 0x6a2085) ^ (m >> 22 & 0xd13c84) ^ (m >> 23 & 0x1c9e15); - r as u32 - -} - - fn batch((mut x, j): (u32, u16), map: &mut [u16; 130321], seen: &mut Vec<u16>) { - let 〇 = x; - let 一 = next(x); - let 二 = next(一); - let 三 = next(二); - let mut ⅰ; - let [mut ⅱ, mut ⅲ, mut ⅳ] = - [[〇, 一], [一, 二], [二, 三]].map(|[a, b]| (9 + mod10(b) - mod10(a)) as u32); + impl Graph { + fn load(content: &str) -> Self { + const INDEX: [u16; 3295] = { + let mut l = [0; 3295]; + include!("../lut"); + l + }; + let mut i = content.as_ptr(); + let mut adj = Box::new([[0u64; WORDS]; SIZE]); + for _ in 0..3380 { + unsafe { + let a = *(i as *const [u8; 2]); + let b = *(i.add(3) as *const [u8; 2]); + let ha = h(a); + let hb = h(b); + i = i.add(6); + let i = INDEX[ha] as usize; + let j = INDEX[hb] as usize; + *adj.get_unchecked_mut(i).get_unchecked_mut(j / 64) |= 1u64 << (j % 64); + *adj.get_unchecked_mut(j).get_unchecked_mut(i / 64) |= 1u64 << (i % 64); + } + } + Graph { adj } + } - x = 三; - let mut l = mod10(三); - for _ in 3..2000 { - x = next(x); - let p = mod10(x); - (ⅰ, ⅱ, ⅲ, ⅳ) = (ⅱ, ⅲ, ⅳ, (9 + p - l) as u32); - let i = (ⅰ * 19 * 19 * 19 + ⅱ * 19 * 19 + ⅲ * 19 + ⅳ) as usize; - if seen[i] != j { - map[i] += p as u16; - seen[i] = j; + fn print_mat(x: [u64; WORDS], l: [u8; 2]) { + let n = Self::adj_on(x); + print!("{}: ", l.p()); + for neighbor in n { + print!("{} ", NAMES[neighbor].p()); } - l = p; + println!(); } - } - static retval: std::sync::Mutex<[u16; 130321]> = std::sync::Mutex::new([0; 130321]); - #[inline(always)] - pub fn part2(x: &str) -> u16 { - let mut i = x.as_bytes(); - let ints = reading::Integer::<u32>::new(&mut i); - let mut chunks = ints.array_chunks::<128>(); - std::thread::scope(|scope| { - for chunk in chunks.by_ref() { - scope.spawn(move || { - let mut map = [0; 130321]; - let mut seen = vec![0; 130321]; - for elem in chunk.into_iter().ι1::<u16>() { - batch(elem, &mut map, &mut seen); - } - let mut upmap = retval.lock().ψ(); - for (a, b) in map.into_iter().zip(upmap.iter_mut()) { - *b += a; + fn first_2_bits(x: [u64; WORDS]) -> [usize; 2] { + let mut out = [0; 2]; + let mut index = 0; + for j in 0..WORDS { + let mut x = x[j]; + while x != 0 { + let bit = x.trailing_zeros(); + out[index] = 64 * j + bit as usize; + index += 1; + if index == 2 { + return out; } - - drop(upmap); - }); + x &= !(1 << bit); + } } + panic!() + } - let mut map = [0; 130321]; - let mut seen = vec![0; 130321]; - for elem in chunks.into_remainder().into_iter().flatten().ι1::<u16>() { - batch(elem, &mut map, &mut seen); - } - let mut upmap = retval.lock().ψ(); - for (a, b) in map.into_iter().zip(upmap.iter_mut()) { - *b += a; + fn adj_on(x: [u64; WORDS]) -> Vec<usize> { + let mut n = Vec::with_capacity(13); + for j in 0..WORDS { + let mut x = x[j]; + while x != 0 { + let bit = x.trailing_zeros(); + n.push(64 * j + bit as usize); + x &= !(1 << bit); + } } - }); - retval.lock().ψ().into_iter().max().ψ() - } + n + } - use std::simd::prelude::*; - #[inline(always)] - pub fn part1(x: &str) -> u64 { - let mut x = x.as_bytes(); - let mut i = reading::Integer::<u32>::new(&mut x).array_chunks::<8>(); - i.by_ref() - .map(|x| u32x8::from_array(x.map(next2000))) - .fold(u32x8::splat(0), |acc, x| acc + x) - .cast::<u64>() - .reduce_sum() - + i.into_remainder() - .map_or(0, |x| x.map(next2000).map(|x| x as u64).sum()) + fn mxq(&self) -> [u64; WORDS] { + 'out: for computer in 0..SIZE { + let neighbors = self.adj[computer]; + if neighbors == [0; 11] { + continue; + } + // neighbors[computer / 64] |= 1 << (computer % 64); + // self.print_mat(neighbors, *b"nh"); + for node in Self::first_2_bits(neighbors) { + let inter = (0..WORDS) + .map(|i| (self.adj[node][i] & neighbors[i]).count_ones()) + .sum::<u32>(); + // check that the current node has 11 neighbours in common with either its first or second neighbour + if inter == 11 { + let mut v = [0; 11]; + let mut pop = 0; + for j in 0..WORDS { + // self.print_mat(neighbors, *b"nh"); + let mut x = neighbors[j]; + while x != 0 { + let bit = x.trailing_zeros(); + let n = 64 * j + bit as usize; + let inter = (0..WORDS) + .map(|i| (self.adj[n][i] & neighbors[i]).count_ones()) + .sum::<u32>(); + // they all have 11 neighbours in common with the current node + if inter == 11 { + v[j] |= 1 << bit; + pop += 1; + } + x &= !(1 << bit); + } + } + // self.print_mat(v, *b"ot"); + if pop != 12 { + continue 'out; + } + v[computer / 64] |= 1 << computer % 64; + // v.push(computer); + // println!("whoa"); + return v; + } + } + } + panic!() + } } } |