diff options
Diffstat (limited to '2021/rust/day10/src/main.rs')
| -rw-r--r-- | 2021/rust/day10/src/main.rs | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/2021/rust/day10/src/main.rs b/2021/rust/day10/src/main.rs new file mode 100644 index 0000000..ef8c8a7 --- /dev/null +++ b/2021/rust/day10/src/main.rs @@ -0,0 +1,236 @@ +use { + anyhow::{ + anyhow, + Context, + Result, + }, + std::{ + env::args, + fmt::{ + Display, + Formatter, + Result as FmtResult, + }, + fs::File, + io::{ + BufRead, + BufReader, + }, + path::Path, + }, +}; + +#[derive(Copy,Clone,Eq,PartialEq)] +enum Bracket { + RoundOpen, + RoundClose, + SquareOpen, + SquareClose, + WigglyOpen, + WigglyClose, + AngleOpen, + AngleClose, +} + +impl Display for Bracket { + fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult { + let c = match &self { + Bracket::RoundOpen => '(', + Bracket::RoundClose => ')', + Bracket::SquareOpen => '[', + Bracket::SquareClose => ']', + Bracket::WigglyOpen => '{', + Bracket::WigglyClose => '}', + Bracket::AngleOpen => '<', + Bracket::AngleClose => '>', + }; + write!(f, "{}", c) + } + +} + +struct BracketLine { + inner: Vec<Bracket>, +} + +impl BracketLine { + fn new<I>(init: I) -> Self + where I: IntoIterator<Item = Bracket> + { + let inner = init.into_iter().collect(); + Self { + inner, + } + } + + fn is_corrupt(&self) -> bool { + let mut stack = vec![]; + for c in &self.inner { + match c { + Bracket::RoundOpen | + Bracket::SquareOpen | + Bracket::WigglyOpen | + Bracket::AngleOpen => stack.push(c), + Bracket::RoundClose => if stack.pop() != Some(&Bracket::RoundOpen) { + return true; + }, + Bracket::SquareClose => if stack.pop() != Some(&Bracket::SquareOpen) { + return true; + }, + Bracket::WigglyClose => if stack.pop() != Some(&Bracket::WigglyOpen) { + return true; + }, + Bracket::AngleClose => if stack.pop() != Some(&Bracket::AngleOpen) { + return true; + }, + } + } + stack.is_empty() + } + + fn check_corrupt(&self) -> Option<usize> { + let mut stack = vec![]; + for c in &self.inner { + match c { + Bracket::RoundOpen | + Bracket::SquareOpen | + Bracket::WigglyOpen | + Bracket::AngleOpen => stack.push(c), + Bracket::RoundClose => if stack.pop() != Some(&Bracket::RoundOpen) { + return Some(3); + }, + Bracket::SquareClose => if stack.pop() != Some(&Bracket::SquareOpen) { + return Some(57); + }, + Bracket::WigglyClose => if stack.pop() != Some(&Bracket::WigglyOpen) { + return Some(1197); + }, + Bracket::AngleClose => if stack.pop() != Some(&Bracket::AngleOpen) { + return Some(25137); + }, + } + } + None + } + + fn fix_incomplete(&self) -> Option<usize> { + let mut stack = vec![]; + let mut points = 0; + for c in &self.inner { + match c { + Bracket::RoundOpen | + Bracket::SquareOpen | + Bracket::WigglyOpen | + Bracket::AngleOpen => stack.push(*c), + Bracket::RoundClose => if stack.pop() != Some(Bracket::RoundOpen) { + return None; + }, + Bracket::SquareClose => if stack.pop() != Some(Bracket::SquareOpen) { + return None; + }, + Bracket::WigglyClose => if stack.pop() != Some(Bracket::WigglyOpen) { + return None; + }, + Bracket::AngleClose => if stack.pop() != Some(Bracket::AngleOpen) { + return None; + }, + } + } + for c in stack.into_iter().rev() { + match c { + Bracket::RoundOpen => { + points *= 5; + points += 1; + // FIXME A real fixer should actually add the missing brackets, but this + // implementation only cares about collecting the points. + // self.inner.push(Bracket::RoundClose); + }, + Bracket::SquareOpen => { + points *= 5; + points += 2; + // self.inner.push(Bracket::SquareClose); + }, + Bracket::WigglyOpen => { + points *= 5; + points += 3; + // self.inner.push(Bracket::WigglyClose); + }, + Bracket::AngleOpen => { + points *= 5; + points += 4; + // self.inner.push(Bracket::AngleClose); + }, + Bracket::RoundClose | + Bracket::SquareClose | + Bracket::WigglyClose | + Bracket::AngleClose => return None, + } + } + Some(points) + } +} + +fn read_input<T: AsRef<Path>>(filename: T) -> Result<Vec<BracketLine>> { + let reader = BufReader::new(File::open(filename)?); + + reader.lines().map( + |v| { + let s = v?; + let bracket_row = s.chars().map(|c| match c { + '(' => Ok(Bracket::RoundOpen), + ')' => Ok(Bracket::RoundClose), + '[' => Ok(Bracket::SquareOpen), + ']' => Ok(Bracket::SquareClose), + '{' => Ok(Bracket::WigglyOpen), + '}' => Ok(Bracket::WigglyClose), + '<' => Ok(Bracket::AngleOpen), + '>' => Ok(Bracket::AngleClose), + invalid => Err(anyhow!("Invalid input: {}", invalid)), + }).collect::<Result<Vec<_>>>()?; + Ok(BracketLine::new(bracket_row)) + } + ).collect() +} + +fn part1<'a, I>(input: I) -> Result<usize> + where I: IntoIterator<Item = &'a BracketLine> +{ + let mut points = 0; + + for line in input { + if let Some(val) = line.check_corrupt() { + points += val; + } + } + Ok(points) +} + +fn part2<'a, I>(input: I) -> Result<usize> + where I: IntoIterator<Item = &'a BracketLine> +{ + let mut points = input.into_iter() + .filter(|line| !line.is_corrupt()) + .filter_map(|line| line.fix_incomplete()).collect::<Vec<_>>(); + points.sort_unstable(); + let contestant_count = &points.len(); + let winner = points.into_iter().nth(contestant_count/2) + .ok_or(anyhow!("Unable to find winner"))?; + + Ok(winner) +} + +fn main() -> Result<()> { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?; + let input = read_input(filename).context("Could not read input")?; + if do_part_1 { + let solution = part1(&input).context("No solution for part 1")?; + println!("Part1, solution found to be: {}", solution); + } + if do_part_2 { + let solution = part2(&input).context("No solution for part 2")?; + println!("Part2, solution found to be: {}", solution); + } + Ok(()) +} |