diff options
| -rw-r--r-- | src/day_12.rs | 188 | ||||
| -rw-r--r-- | src/lib.rs | 3 |
2 files changed, 140 insertions, 51 deletions
diff --git a/src/day_12.rs b/src/day_12.rs index 6b755c9..3f02c58 100644 --- a/src/day_12.rs +++ b/src/day_12.rs @@ -14,75 +14,114 @@ impl Solution for Day12 { type Answer2 = usize; fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { - let rows = input + Ok(input .lines() .map(std::str::FromStr::from_str) - .try_collect::<Vec<Row>>()?; - - Ok(rows + .try_collect::<Vec<Row<1>>>()? .into_iter() - .map(|row| { - row.permutations() - .into_iter() - .filter(|p| row.check_group(p)) - .count() - }) + .map(Row::solve) .sum()) } fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { - todo!() + Ok(input + .lines() + .map(std::str::FromStr::from_str) + .try_collect::<Vec<Row<5>>>()? + .into_iter() + .map(Row::solve) + .sum()) } } #[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] -struct Row { +struct Row<const REP: u8> { states: Vec<State>, groups: Vec<usize>, } -impl Row { - fn unknowns(&self) -> usize { - self.states.iter().filter(|&&s| s == State::Unknown).count() +impl<const REP: u8> Row<REP> { + fn new(states: Vec<State>, groups: Vec<usize>) -> Self { + let states = std::iter::repeat(states) + .take(REP as usize) + .intersperse(vec![State::Unknown]) + .flatten() + .collect::<Vec<_>>(); + + let groups = std::iter::repeat(groups) + .take(REP as usize) + .flatten() + .collect::<Vec<_>>(); + + Self { states, groups } } - fn permutations(&self) -> Vec<Vec<State>> { - (0..self.unknowns()) - .fold(vec![vec![]], |acc, _| { - acc.into_iter() - .flat_map(|mut p1| { - let mut p2 = p1.to_vec(); - p2.push(State::Bad); - p1.push(State::Good); - [p1, p2] + fn solve(mut self) -> usize { + self.states.push(State::Good); + + let mut groups = vec![Group::default()]; + + for state in self.states.into_iter() { + let mut next_groups = Vec::new(); + + for Group { + seq, + index, + count, + prev, + } in groups + { + if state == State::Unknown || state == State::Bad { + next_groups.push(Group { + seq: seq + 1, + index, + count, + prev: Some(State::Bad), }) - .collect() - }) - .into_iter() - .map(|s| { - let mut iter = s.into_iter(); - let mut row = self.states.to_vec(); - for s in row.iter_mut() { - if let State::Unknown = s { - *s = iter.next().unwrap() - }; } - row - }) - .collect() - } - fn check_group(&self, states: &[State]) -> bool { - let mut counts = self.groups.iter(); + if state == State::Unknown || state == State::Good { + if prev != Some(State::Bad) { + next_groups.push(Group { + seq: 0, + index, + count, + prev: Some(State::Good), + }); + } else if self.groups.get(index).is_some_and(|s| *s == seq) { + next_groups.push(Group { + seq: 0, + index: index + 1, + count, + prev: Some(State::Good), + }); + } + } + } + + next_groups.sort(); + + groups = next_groups.into_iter().fold(Vec::new(), |mut acc, group| { + if let Some(last) = acc.last_mut() { + if last.seq == group.seq && last.index == group.index && last.prev == group.prev + { + last.count += group.count; + return acc; + } + } + acc.push(group); + acc + }); + } - states.group_by(|a, b| a == b).all(|group| { - group.iter().all(|s| *s == State::Good) - || counts.next().is_some_and(|n| *n == group.len()) - }) && counts.next().is_none() + groups + .into_iter() + .filter_map(|g| (g.index == self.groups.len()).then_some(g.count)) + .sum() } } -impl std::str::FromStr for Row { +impl<const REP: u8> std::str::FromStr for Row<REP> { type Err = anyhow::Error; fn from_str(s: &str) -> Result<Self, Self::Err> { @@ -98,7 +137,42 @@ impl std::str::FromStr for Row { .map(std::str::FromStr::from_str) .try_collect::<Vec<usize>>()?; - Ok(Self { states, groups }) + Ok(Self::new(states, groups)) + } +} + +impl<const REP: u8> std::fmt::Display for Row<REP> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + self.states + .iter() + .try_for_each(|s| write!(f, "{}", char::from(*s)))?; + + self.groups.iter().enumerate().try_for_each(|(i, n)| { + if i == 0 { + write!(f, " {n}") + } else { + write!(f, ",{n}") + } + }) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct Group { + seq: usize, + index: usize, + count: usize, + prev: Option<State>, +} + +impl Default for Group { + fn default() -> Self { + Self { + seq: 0, + index: 0, + count: 1, + prev: None, + } } } @@ -113,16 +187,25 @@ impl TryFrom<char> for State { type Error = anyhow::Error; fn try_from(value: char) -> Result<Self, Self::Error> { - use State::*; match value { - '.' => Ok(Good), - '#' => Ok(Bad), - '?' => Ok(Unknown), + '.' => Ok(State::Good), + '#' => Ok(State::Bad), + '?' => Ok(State::Unknown), c => Err(anyhow::format_err!("Unknown spring condition: {c}")), } } } +impl From<State> for char { + fn from(value: State) -> Self { + match value { + State::Good => '.', + State::Bad => '#', + State::Unknown => '?', + } + } +} + #[cfg(test)] mod tests { use super::*; @@ -140,4 +223,9 @@ mod tests { fn test_part_1() -> anyhow::Result<()> { Ok(assert_eq!(21, Day12::part_1(INPUT)?)) } + + #[test] + fn test_part_2() -> anyhow::Result<()> { + Ok(assert_eq!(525152, Day12::part_2(INPUT)?)) + } } @@ -4,7 +4,8 @@ array_windows, array_chunks, let_chains, - slice_group_by + slice_group_by, + iter_intersperse )] pub mod day_01; |