summaryrefslogtreecommitdiffstats
path: root/day13a/src/main.rs
diff options
context:
space:
mode:
Diffstat (limited to 'day13a/src/main.rs')
-rw-r--r--day13a/src/main.rs270
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}");
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-16 16:30:13 +0000