bendns' repos / aoc
heh
Diffstat
-rw-r--r--src/main.rs124
-rw-r--r--src/util.rs99
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,
{