initial commit

1 files changed, 132 insertions, 0 deletions

diff --git a/2022/src/day13.rs b/2022/src/day13.rs
new file mode 100644
index 0000000..17b55eb
--- /dev/null
+++ b/2022/src/day13.rs
@@ -0,0 +1,132 @@
+mod utils;
+use std::{
+    cmp::Ordering,
+    iter::{once, Peekable},
+};
+
+extern crate nom;
+use nom::{bytes::complete::tag, character::complete::u32};
+use utils::read_input;
+
+fn main() {
+    let input = read_input();
+
+    let mut full: Vec<_> = input.lines().filter(|x| !x.is_empty()).collect();
+
+    println!(
+        "Part 1: {}",
+        full.iter()
+            .step_by(2)
+            .zip(full.iter().skip(1).step_by(2))
+            .map(|(left, right)| { compare(left, right) })
+            .enumerate()
+            .filter_map(|(i, cmp)| match cmp {
+                Ordering::Greater => None,
+                _ => Some(i + 1),
+            })
+            .sum::<usize>()
+    );
+
+    full.sort_by(|l, r| compare(l, r));
+
+    println!(
+        "Part 2: {}",
+        full.iter()
+            .enumerate()
+            .filter_map(|(i, val)| match *val {
+                "[[2]]" | "[[6]]" => Some(i + 1),
+                _ => None,
+            })
+            .product::<usize>()
+    );
+}
+
+fn compare(left: &str, right: &str) -> Ordering {
+    let mut left = Packet(left).peekable();
+    let mut right = Packet(right).peekable();
+    assert_eq!(left.next(), Some(PacketContents::StartList));
+    assert_eq!(right.next(), Some(PacketContents::StartList));
+    compare_lists(&mut left, &mut right)
+}
+
+fn compare_lists(
+    left: &mut Peekable<impl Iterator<Item = PacketContents>>,
+    right: &mut Peekable<impl Iterator<Item = PacketContents>>,
+) -> Ordering {
+    loop {
+        match (left.next().unwrap(), right.next().unwrap()) {
+            (PacketContents::EndList, PacketContents::EndList) => {
+                return Ordering::Equal;
+            }
+            (PacketContents::EndList, _) => {
+                while !matches!(right.next(), Some(PacketContents::EndList)) {}
+                return Ordering::Less;
+            }
+            (_, PacketContents::EndList) => {
+                while !matches!(left.next(), Some(PacketContents::EndList)) {}
+
+                return Ordering::Greater;
+            }
+            (PacketContents::StartList, PacketContents::StartList) => {
+                match compare_lists(left, right) {
+                    Ordering::Equal => (),
+                    x => return x,
+                }
+            }
+            (l @ PacketContents::Integer(_), PacketContents::StartList) => {
+                match compare_lists(
+                    &mut once(l).chain(once(PacketContents::EndList)).peekable(),
+                    right,
+                ) {
+                    Ordering::Equal => (),
+                    x => return x,
+                }
+            }
+            (PacketContents::StartList, r @ PacketContents::Integer(_)) => {
+                match compare_lists(
+                    left,
+                    &mut once(r).chain(once(PacketContents::EndList)).peekable(),
+                ) {
+                    Ordering::Equal => (),
+                    x => return x,
+                }
+            }
+            (PacketContents::Integer(l), PacketContents::Integer(r)) => match l.cmp(&r) {
+                Ordering::Equal => (),
+                x => return x,
+            },
+        };
+    }
+}
+
+#[derive(Debug, PartialEq, Eq)]
+enum PacketContents {
+    Integer(usize),
+    StartList,
+    EndList,
+}
+
+struct Packet<'a>(&'a str);
+
+impl Iterator for Packet<'_> {
+    type Item = PacketContents;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        loop {
+            if let Ok((i, _)) = tag::<_, _, (&str, nom::error::ErrorKind)>("[")(self.0) {
+                self.0 = i;
+                return Some(PacketContents::StartList);
+            } else if let Ok((i, _)) = tag::<_, _, (&str, nom::error::ErrorKind)>("]")(self.0) {
+                self.0 = i;
+                return Some(PacketContents::EndList);
+            } else if let Ok((i, x)) = u32::<_, (&str, nom::error::ErrorKind)>(self.0) {
+                self.0 = i;
+                return Some(PacketContents::Integer(x as usize));
+            } else if let Ok((i, _)) = tag::<_, _, (&str, nom::error::ErrorKind)>(",")(self.0) {
+                self.0 = i;
+            } else {
+                return None;
+            }
+        }
+    }
+}