day12
| -rw-r--r-- | src/lib.rs | 180 |
1 files changed, 108 insertions, 72 deletions
@@ -29,86 +29,122 @@ hint_assert_unchecked )] mod util; -pub mod day11 { +pub mod day12 { use super::util::prelude::*; - pub fn part1(i: &str) -> impl Display { - const LUT: [u32; 10000000] = unsafe { - std::mem::transmute::<[u8; 10000000 * 4], _>(*include_bytes!("../beeg2-larger-basic")) - }; - p8(i) - .map(|stone| C! { LUT[stone as usize] }) - .into_iter() - .sum::<u32>() - } + const SIZE: usize = 140; + #[no_mangle] + pub fn part2(i: &str) -> impl Display { + fn explore( + (x, y): (usize, usize), + handled: &mut [[bool; 140]; 140], + char: u8, + get: &mut impl FnMut(usize, usize) -> Option<u8>, + tot: &mut u32, + count: &mut u32, + ) { + if get(x, y) == Some(char) && handled[y][x] == false { + handled[y][x] = true; + // αbβ + // a.c + // γdδ + let α = get(x.wrapping_sub(1), y.wrapping_sub(1)) != Some(char); + let β = get(x.wrapping_add(1), y.wrapping_sub(1)) != Some(char); + let γ = get(x.wrapping_sub(1), y.wrapping_add(1)) != Some(char); + let δ = get(x.wrapping_add(1), y.wrapping_add(1)) != Some(char); - fn nat<const N: usize>(x: [&u8; N]) -> u32 { - x.into_iter().fold(0, |acc, x| acc * 10 + (x - b'0') as u32) - } + let a = get(x.wrapping_sub(1), y) != Some(char); + let b = get(x, y.wrapping_sub(1)) != Some(char); + let c = get(x.wrapping_add(1), y) != Some(char); + let d = get(x, y.wrapping_add(1)) != Some(char); + fn u(a: bool) -> u32 { + a as u32 + } + // *tot += u(a) + u(b) + u(c) + u(d); - pub fn part2(i: &str) -> impl Display { - static mut lut: [u64; 10000000] = unsafe { - std::mem::transmute::<[u8; 10000000 * 8], _>(*include_bytes!("../beeg-basic")) + *tot += u(a & b) + u(b & c) + u(c & d) + u(a & d); + *tot += u(!a & !b & α) + u(!b & !c & β) + u(!c & !d & δ) + u(!a & !d & γ); + *count += 1; + + explore((x.wrapping_sub(1), y), handled, char, get, tot, count); + explore((x + 1, y), handled, char, get, tot, count); + explore((x, y + 1), handled, char, get, tot, count); + explore((x, y.wrapping_sub(1)), handled, char, get, tot, count); + } + } + + let grid = unsafe { i.as_bytes().as_chunks_unchecked::<{ SIZE + 1 }>() }; + let handled = &mut [[false; SIZE]; SIZE]; + let mut get = |x: usize, y: usize| { + unsafe { core::hint::assert_unchecked(grid.len() == SIZE) }; + (x < SIZE && y < SIZE).then(|| grid[y][x]) }; - p8(i) - .map(|stone| C! { lut[stone as usize] }) - .into_iter() - .sum::<u64>() + (0..SIZE) + .flat_map(move |y| (0..SIZE).map(move |x| (x, y))) + .filter_map(|(x, y)| { + let mut sides = 0; + let mut area = 0; + (!handled[y][x]).then(|| { + let char = C! { grid[y][x]}; + explore((x, y), handled, char, &mut get, &mut sides, &mut area); + area * sides + }) + }) + .sum::<u32>() } - - fn p8(i: &str) -> [u32; 8] { - let mut i = &i.as_bytes()[..i.len() - 1]; - use std::mem::MaybeUninit as MU; - let mut arr = [const { MU::<u32>::uninit() }; 8]; - for j in 0..7 { - arr[j].write(match i { - [一, b' ', rest @ ..] => { - i = rest; - nat([一]) - } - [一, 二, b' ', rest @ ..] => { - i = rest; - nat([一, 二]) - } - [一, 二, 三, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三]) - } - [一, 二, 三, 四, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三, 四]) - } - [一, 二, 三, 四, 五, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三, 四, 五]) - } - [一, 二, 三, 四, 五, 六, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三, 四, 五, 六]) - } - [一, 二, 三, 四, 五, 六, 七, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三, 四, 五, 六, 七]) - } - [一, 二, 三, 四, 五, 六, 七, 八, b' ', rest @ ..] => { - i = rest; - nat([一, 二, 三, 四, 五, 六, 七, 八]) + #[no_mangle] + pub fn part1(i: &str) -> impl Display { + fn explore( + (x, y): (usize, usize), + handled: &mut [[bool; 140]; 140], + char: u8, + get: &mut impl FnMut(usize, usize) -> Option<u8>, + tot: &mut u32, + count: &mut u32, + ) { + if get(x, y) == Some(char) && handled[y][x] == false { + handled[y][x] = true; + // αbβ + // a.c + // γdδ + let a = get(x.wrapping_sub(1), y) != Some(char); + let b = get(x, y.wrapping_sub(1)) != Some(char); + let c = get(x.wrapping_add(1), y) != Some(char); + let d = get(x, y.wrapping_add(1)) != Some(char); + fn u(a: bool) -> u32 { + a as u32 } - _ => shucks!(), - }); + *tot += u(a) + u(b) + u(c) + u(d); + + // *tot += u(a & b) + u(b & c) + u(c & d) + u(a & d); + // *tot += u(!a & !b & α) + u(!b & !c & β) + u(!c & !d & δ) + u(!a & !d & γ); + *count += 1; + + explore((x.wrapping_sub(1), y), handled, char, get, tot, count); + explore((x + 1, y), handled, char, get, tot, count); + explore((x, y + 1), handled, char, get, tot, count); + explore((x, y.wrapping_sub(1)), handled, char, get, tot, count); + } } - arr[7].write(match i { - [一] => nat([一]), - [一, 二] => nat([一, 二]), - [一, 二, 三] => nat([一, 二, 三]), - [一, 二, 三, 四] => nat([一, 二, 三, 四]), - [一, 二, 三, 四, 五] => nat([一, 二, 三, 四, 五]), - [一, 二, 三, 四, 五, 六] => nat([一, 二, 三, 四, 五, 六]), - [一, 二, 三, 四, 五, 六, 七] => nat([一, 二, 三, 四, 五, 六, 七]), - [一, 二, 三, 四, 五, 六, 七, 八] => nat([一, 二, 三, 四, 五, 六, 七, 八]), - _ => shucks!(), - }); - unsafe { MU::array_assume_init(arr) } + + let grid = unsafe { i.as_bytes().as_chunks_unchecked::<{ SIZE + 1 }>() }; + let handled = &mut [[false; SIZE]; SIZE]; + let mut get = |x: usize, y: usize| { + unsafe { core::hint::assert_unchecked(grid.len() == SIZE) }; + (x < SIZE && y < SIZE).then(|| grid[y][x]) + }; + (0..SIZE) + .flat_map(move |y| (0..SIZE).map(move |x| (x, y))) + .filter_map(|(x, y)| { + let mut sides = 0; + let mut area = 0; + (!handled[y][x]).then(|| { + let char = C! { grid[y][x]}; + explore((x, y), handled, char, &mut get, &mut sides, &mut area); + area * sides + }) + }) + .sum::<u32>() } } |