heh
*six hours later* d19p2
| -rw-r--r-- | src/main.rs | 124 | ||||
| -rw-r--r-- | src/util.rs | 99 |
2 files changed, 207 insertions, 16 deletions
diff --git a/src/main.rs b/src/main.rs index 1fa5884..f75e931 100644 --- a/src/main.rs +++ b/src/main.rs @@ -17,15 +17,26 @@ extern crate test; pub mod util; pub use util::prelude::*; +use util::Ronge; #[derive(Debug, Copy, Clone, PartialEq, Eq)] enum When { // m>N - Gt(What, u32), - Lt(What, u32), + Gt(What, u16), + Lt(What, u16), Always, } +impl std::fmt::Display for When { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + When::Gt(a, b) => write!(f, "{a:?}>{b}"), + When::Lt(a, b) => write!(f, "{a:?}<{b}"), + When::Always => Ok(()), + } + } +} + impl When { fn accepts(self) -> Option<What> { match self { @@ -34,11 +45,7 @@ impl When { } } - fn considers(self, w: What) -> bool { - matches!(self, Self::Gt(y, _) | Self::Lt(y, _) if w == y) | (self == Self::Always) - } - - fn test(self, w: u32) -> bool { + fn test(self, w: u16) -> bool { match self { Self::Gt(_, x) => w > x, Self::Lt(_, x) => w < x, @@ -48,14 +55,30 @@ impl When { } #[repr(u8)] -#[derive(Debug, Copy, Clone)] +#[derive(Debug, Copy, Clone, PartialEq, Eq)] enum Then<'a> { Go(&'a [u8]), Accept = b'A', Reject = b'R', } +impl Display for Then<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Then::Go(x) => write!(f, "{}", x.p()), + Then::Accept => write!(f, "A"), + Then::Reject => write!(f, "R"), + } + } +} + impl<'a> Then<'a> { + pub fn get<'b>(self, from: &'a [Workflow<'b>]) -> &'a Workflow<'b> { + mat!(self { + Then::Go(x) => from.iter().find(|w| w.name == x).α(), + }) + } + pub fn from(x: u8) -> Self { mat!(x { b'A' => Self::Accept, @@ -74,7 +97,7 @@ impl<'a> Then<'a> { #[repr(u8)] #[derive(Debug, Copy, Clone, PartialEq, Eq)] -#[allow(non_camel_case_types)] +#[allow(non_camel_case_types, dead_code)] enum What { x = b'x', m = b'm', @@ -83,7 +106,16 @@ enum What { } impl What { - pub fn select(self, [x, m, a, s]: [u32; 4]) -> u32 { + pub fn select<T>(self, [x, m, a, s]: [T; 4]) -> T { + match self { + What::x => x, + What::m => m, + What::a => a, + What::s => s, + } + } + + pub fn select_mut<T>(self, [x, m, a, s]: &mut [T; 4]) -> &mut T { match self { What::x => x, What::m => m, @@ -103,12 +135,18 @@ struct Rule<'a> { then: Then<'a>, } +impl Display for Rule<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}:{}", self.condition, self.then) + } +} + impl<'a> Rule<'a> { fn takes(self) -> Option<What> { self.condition.accepts() } - fn consider(self, x: u32) -> Option<Then<'a>> { + fn consider(self, x: u16) -> Option<Then<'a>> { self.condition.test(x).then_some(self.then) } } @@ -119,7 +157,7 @@ struct Workflow<'a> { } impl<'a> Workflow<'a> { - fn test(&self, x: [u32; 4]) -> Option<Then> { + fn test(&self, x: [u16; 4]) -> Option<Then> { for rule in &*self.rules { if let Some(x) = rule.takes().map(|y| y.select(x)) { if let Some(x) = rule.consider(x) { @@ -151,12 +189,12 @@ impl<'a> Workflow<'a> { if let Some((&[x], y)) = cond.split_once(|&x| x == b'<') { rules.push(Rule { - condition: When::Lt(What::from(x), y.λ::<u32>()), + condition: When::Lt(What::from(x), y.λ()), then: Then::from2(then), }) } else if let Some((&[x], y)) = cond.split_once(|&x| x == b'>') { rules.push(Rule { - condition: When::Gt(What::from(x), y.λ::<u32>()), + condition: When::Gt(What::from(x), y.λ()), then: Then::from2(then), }) } else { @@ -171,7 +209,61 @@ impl<'a> Workflow<'a> { } } -pub fn run(i: &str) -> u32 { +pub fn p2(i: &str) -> u64 { + let mut workflows = vec![]; + let mut i = i.行(); + for x in i.by_ref() { + if x == b"" { + break; + } + let (work, rules) = x.μ('{').mr(|x| x.μ0('}').split(|&x| x == b',')); + let flow = Workflow::new(work, rules); + workflows.push(flow); + } + let mut s = 0; + let h = Workflow { + name: b"", + rules: Box::new([]), + }; + util::iterg( + (Then::Go(b"in"), [Ronge::from(1..=4001); 4]), + &mut |(work, mut r): (Then<'_>, [Ronge; 4])| { + let work = match work { + Then::Reject => &h, // why are you like this + g => g.get(&workflows), + }; + work.rules.iter().map(move |x| { + let mut r2 = r; + match x.condition { + When::Gt(c, x) => { + c.select_mut(&mut r2).begin = x + 1; + c.select_mut(&mut r).end = x + 1; + } + When::Lt(c, x) => { + c.select_mut(&mut r2).end = x; + c.select_mut(&mut r).begin = x; + } + When::Always => (), + } + (x.then, r2) + }) + }, + &mut |(x, _)| x == Then::Accept, + &mut |(_, r)| { + s += r + .iter() + .map(|x| x.end.abs_diff(x.begin) as u64) + .product::<u64>() + }, + ); + s +} + +pub fn run(i: &str) -> impl Display { + p2(i) +} + +pub fn p1(i: &str) -> u32 { let mut workflows = vec![]; let mut first = None; let mut i = i.行(); @@ -200,7 +292,7 @@ pub fn run(i: &str) -> u32 { if let Some(x) = w.test(a) { match x { Then::Accept => { - acc += a.iter().copied().sum::<u32>(); + acc += a.iter().map(|&x| x as u32).sum::<u32>(); break; } Then::Go(y) => w = workflows.iter().find(|x| x.name == y).α(), diff --git a/src/util.rs b/src/util.rs index 8f2de97..1f3e405 100644 --- a/src/util.rs +++ b/src/util.rs @@ -5,6 +5,7 @@ use std::{ fmt::{Debug, Display, Write}, hash::Hash, mem::{swap, MaybeUninit}, + ops::RangeInclusive, str::FromStr, }; @@ -208,6 +209,19 @@ where } } +pub fn iterg<N: Debug + Copy, I: Iterator<Item = N>>( + start: N, + graph: &mut impl Fn(N) -> I, + end: &mut impl Fn(N) -> bool, + finally: &mut impl FnMut(N), +) { + if end(start) { + finally(start); + } else { + graph(start).map(|x| iterg(x, graph, end, finally)).Θ(); + }; +} + pub fn show<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>, D: Display>( graph: impl Fn(N) -> I, start: N, @@ -467,6 +481,91 @@ impl Ͷ for u64 { } } +#[derive(Copy, Clone, PartialEq, PartialOrd)] +pub struct Ronge { + pub begin: u16, + pub end: u16, +} + +impl Debug for Ronge { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}..{}", self.begin, self.end) + } +} + +impl Display for Ronge { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}..{}", self.begin, self.end) + } +} + +impl From<RangeInclusive<u16>> for Ronge { + fn from(value: RangeInclusive<u16>) -> Self { + Self { + begin: *value.start(), + end: *value.end(), + } + } +} + +impl PartialEq<RangeInclusive<u16>> for Ronge { + fn eq(&self, other: &RangeInclusive<u16>) -> bool { + self == &Self::from(other.clone()) + } +} + +impl Ronge { + pub fn len(self) -> u16 { + self.end - self.begin + } + + /// push up + pub fn pushu(&mut self, to: u16) { + self.begin = self.begin.max(to); + } + + /// push down + pub fn pushd(&mut self, to: u16) { + self.end = self.end.min(to); + } + + pub fn intersect(self, with: Self) -> Self { + Self { + begin: self.begin.max(with.begin), + end: self.end.min(with.end), + } + } + + pub fn news(&self, begin: u16) -> Self { + Self { + begin, + end: self.end, + } + } + + pub fn newe(&self, end: u16) -> Self { + Self { + begin: self.begin, + end, + } + } + + pub fn shrink(&mut self, with: Ronge) { + self.pushu(with.begin); + self.pushd(with.end); + } +} + +impl IntoIterator for Ronge { + type Item = u16; + + type IntoIter = std::ops::Range<u16>; + + fn into_iter(self) -> Self::IntoIter { + self.begin..self.end + } +} + pub trait Μ where Self: Sized, { |