Add day10, 2021

3 files changed, 246 insertions, 1 deletions

diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml
index dd0516c..6015d2b 100644
--- a/2021/rust/Cargo.toml
+++ b/2021/rust/Cargo.toml
@@ -9,7 +9,7 @@ members = [
     "day07",
     "day08",
     "day09",
-#    "day10",
+    "day10",
 #    "day11",
 #    "day12",
 #    "day13",
diff --git a/2021/rust/day10/Cargo.toml b/2021/rust/day10/Cargo.toml
new file mode 100644
index 0000000..7f830ae
--- /dev/null
+++ b/2021/rust/day10/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day10"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
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(())
+}