complete day 13

1 files changed, 270 insertions, 0 deletions

diff --git a/day13a/src/main.rs b/day13a/src/main.rs
new file mode 100644
index 0000000..204d674
--- /dev/null
+++ b/day13a/src/main.rs
@@ -0,0 +1,270 @@
+#![feature(iter_array_chunks)]
+
+/// --- Day 13: Distress Signal ---
+///
+/// You climb the hill and again try contacting the Elves.  However, you instead receive a signal
+/// you weren't expecting: a distress signal.
+///
+/// Your handheld device must still not be working properly; the packets from the distress signal
+/// got decoded out of order.  You'll need to re-order the list of received packets (your puzzle
+/// input) to decode the message.
+///
+/// Your list consists of pairs of packets; pairs are separated by a blank line.  You need to
+/// identify how many pairs of packets are in the right order.
+///
+/// For example:
+///
+/// ```
+/// [1,1,3,1,1]
+/// [1,1,5,1,1]
+///
+/// [[1],[2,3,4]]
+/// [[1],4]
+///
+/// [9]
+/// [[8,7,6]]
+///
+/// [[4,4],4,4]
+/// [[4,4],4,4,4]
+///
+/// [7,7,7,7]
+/// [7,7,7]
+///
+/// []
+/// [3]
+///
+/// [[[]]]
+/// [[]]
+///
+/// [1,[2,[3,[4,[5,6,7]]]],8,9]
+/// [1,[2,[3,[4,[5,6,0]]]],8,9]
+/// ```
+///
+/// Packet data consists of lists and integers.  Each list starts with [, ends with ], and contains
+/// zero or more comma-separated values (either integers or other lists).  Each packet is always a
+/// list and appears on its own line.
+///
+/// When comparing two values, the first value is called left and the second value is called right.
+/// Then:
+///
+///     If both values are integers, the lower integer should come first.  If the left integer is
+///     lower than the right integer, the inputs are in the right order.  If the left integer is
+///     higher than the right integer, the inputs are not in the right order.  Otherwise, the
+///     inputs are the same integer; continue checking the next part of the input.
+///     If both values are lists, compare the first value of each list, then the second value, and
+///     so on.  If the left list runs out of items first, the inputs are in the right order.  If
+///     the right list runs out of items first, the inputs are not in the right order.  If the
+///     lists are the same length and no comparison makes a decision about the order, continue
+///     checking the next part of the input.
+///     If exactly one value is an integer, convert the integer to a list which contains that
+///     integer as its only value, then retry the comparison.  For example, if comparing [0,0,0]
+///     and 2, convert the right value to [2] (a list containing 2); the result is then found by
+///     instead comparing [0,0,0] and [2].
+///
+/// Using these rules, you can determine which of the pairs in the example are in the right order:
+///
+/// ```
+/// == Pair 1 ==
+/// - Compare [1,1,3,1,1] vs [1,1,5,1,1]
+///   - Compare 1 vs 1
+///   - Compare 1 vs 1
+///   - Compare 3 vs 5
+///     - Left side is smaller, so inputs are in the right order
+///
+/// == Pair 2 ==
+/// - Compare [[1],[2,3,4]] vs [[1],4]
+///   - Compare [1] vs [1]
+///     - Compare 1 vs 1
+///   - Compare [2,3,4] vs 4
+///     - Mixed types; convert right to [4] and retry comparison
+///     - Compare [2,3,4] vs [4]
+///       - Compare 2 vs 4
+///         - Left side is smaller, so inputs are in the right order
+///
+/// == Pair 3 ==
+/// - Compare [9] vs [[8,7,6]]
+///   - Compare 9 vs [8,7,6]
+///     - Mixed types; convert left to [9] and retry comparison
+///     - Compare [9] vs [8,7,6]
+///       - Compare 9 vs 8
+///         - Right side is smaller, so inputs are not in the right order
+///
+/// == Pair 4 ==
+/// - Compare [[4,4],4,4] vs [[4,4],4,4,4]
+///   - Compare [4,4] vs [4,4]
+///     - Compare 4 vs 4
+///     - Compare 4 vs 4
+///   - Compare 4 vs 4
+///   - Compare 4 vs 4
+///   - Left side ran out of items, so inputs are in the right order
+///
+/// == Pair 5 ==
+/// - Compare [7,7,7,7] vs [7,7,7]
+///   - Compare 7 vs 7
+///   - Compare 7 vs 7
+///   - Compare 7 vs 7
+///   - Right side ran out of items, so inputs are not in the right order
+///
+/// == Pair 6 ==
+/// - Compare [] vs [3]
+///   - Left side ran out of items, so inputs are in the right order
+///
+/// == Pair 7 ==
+/// - Compare [[[]]] vs [[]]
+///   - Compare [[]] vs []
+///     - Right side ran out of items, so inputs are not in the right order
+///
+/// == Pair 8 ==
+/// - Compare [1,[2,[3,[4,[5,6,7]]]],8,9] vs [1,[2,[3,[4,[5,6,0]]]],8,9]
+///   - Compare 1 vs 1
+///   - Compare [2,[3,[4,[5,6,7]]]] vs [2,[3,[4,[5,6,0]]]]
+///     - Compare 2 vs 2
+///     - Compare [3,[4,[5,6,7]]] vs [3,[4,[5,6,0]]]
+///       - Compare 3 vs 3
+///       - Compare [4,[5,6,7]] vs [4,[5,6,0]]
+///         - Compare 4 vs 4
+///         - Compare [5,6,7] vs [5,6,0]
+///           - Compare 5 vs 5
+///           - Compare 6 vs 6
+///           - Compare 7 vs 0
+///             - Right side is smaller, so inputs are not in the right order
+/// ```
+///
+/// What are the indices of the pairs that are already in the right order? (The first pair has
+/// index 1, the second pair has index 2, and so on.) In the above example, the pairs in the right
+/// order are 1, 2, 4, and 6; the sum of these indices is 13.
+///
+/// Determine which pairs of packets are already in the right order.  What is the sum of the
+/// indices of those pairs?
+use clap::Parser;
+use itertools::Itertools;
+use nom::branch::alt;
+use nom::bytes::complete::tag;
+use nom::character::complete::i8;
+use nom::combinator::{map, opt};
+use nom::error::{ContextError, ErrorKind as NomErrorKind, ParseError};
+use nom::multi::many1;
+use nom::sequence::{delimited, terminated};
+use nom::IResult;
+
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+use std::path::PathBuf;
+
+const FILEPATH: &'static str = "examples/input.txt";
+
+pub type Input<'a> = &'a str;
+pub type Result<'a, T> = IResult<Input<'a>, T, Error<Input<'a>>>;
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum ErrorKind {
+    Nom(NomErrorKind),
+    Context(&'static str),
+    Custom(String),
+}
+
+#[derive(Parser, Debug)]
+#[clap(author, version, about, long_about = None)]
+struct Cli {
+    #[clap(short, long, default_value = FILEPATH)]
+    file: PathBuf,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Error<I> {
+    pub errors: Vec<(I, ErrorKind)>,
+}
+
+#[derive(Clone, Debug)]
+enum ListEntry {
+    Value(Option<i8>),
+    List(Vec<ListEntry>),
+}
+
+impl<I> ParseError<I> for Error<I> {
+    fn from_error_kind(input: I, kind: NomErrorKind) -> Self {
+        let errors = vec![(input, ErrorKind::Nom(kind))];
+        Self { errors }
+    }
+
+    fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self {
+        other.errors.push((input, ErrorKind::Nom(kind)));
+        other
+    }
+}
+
+impl<I> ContextError<I> for Error<I> {
+    fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self {
+        other.errors.push((input, ErrorKind::Context(ctx)));
+        other
+    }
+}
+
+fn parse_list(input: &str) -> Result<ListEntry> {
+    alt((
+        map(i8, |v| ListEntry::Value(Some(v))),
+        map(tag("[]"), |_| ListEntry::Value(None)),
+        delimited(
+            tag("["),
+            map(many1(terminated(parse_list, opt(tag(",")))), |list| {
+                ListEntry::List(list)
+            }),
+            tag("]"),
+        ),
+    ))(input)
+}
+
+fn compare(lhs: &ListEntry, rhs: &ListEntry) -> Option<bool> {
+    use ListEntry::*;
+    match (lhs, rhs) {
+        (Value(lv), Value(rv)) => {
+            if lv == rv {
+                None
+            } else {
+                Some(lv < rv)
+            }
+        }
+        (Value(None), List(_)) => Some(true),
+        (Value(_), List(_)) => compare(&ListEntry::List(vec![lhs.clone()]), rhs),
+        (List(_), Value(None)) => Some(false),
+        (List(_), Value(_)) => compare(lhs, &ListEntry::List(vec![rhs.clone()])),
+        (List(lv), List(rv)) => lv
+            .iter()
+            .zip_longest(rv.iter())
+            .find_map(|pair| match pair {
+                itertools::EitherOrBoth::Both(l, r) => compare(l, r),
+                itertools::EitherOrBoth::Right(_) => Some(true),
+                itertools::EitherOrBoth::Left(_) => Some(false),
+            }),
+    }
+}
+
+fn main() {
+    let args = Cli::parse();
+
+    let file = File::open(&args.file).unwrap();
+    let reader = BufReader::new(file);
+
+    let res: i32 = reader
+        .lines()
+        .filter_map(|line| {
+            let s = line.unwrap();
+            if s.is_empty() {
+                return None;
+            }
+            Some(parse_list(s.as_str()).unwrap().1)
+        })
+        .array_chunks::<2>()
+        .zip(1..)
+        .filter_map(|(chunk, idx)| {
+            if compare(&chunk[0], &chunk[1]).unwrap() {
+                Some(idx)
+            } else {
+                None
+            }
+        })
+        .sum();
+
+    println!("{res}");
+}