path: root/day13a/src/main.rs

#![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}");
}