/// Represnts a Packet. Packet data consists of lists and integer (that's what the
/// puzzle says, anyway).
#[derive(Debug, Clone, PartialEq, Eq)]
enum Packet {
    Integer(u8),
    List(Vec<Packet>),
}

/// Represents a pair of packets. Riveting stuff!
#[derive(Debug, Clone)]
struct PacketPair(Packet, Packet);

/// Here's where the magic happens. This module wraps the parsers for the list of
/// packet pairs presented in the input.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::{newline, u8},
        combinator::map,
        multi::{separated_list0, separated_list1},
        sequence::{delimited, separated_pair},
        Finish, IResult,
    };

    /// Nom parser for "2" -> Packet::Integer(2)
    fn integer(s: &str) -> IResult<&str, Packet> {
        map(u8, Packet::Integer)(s)
    }

    /// This is where the recursion happens. This parser parses lists of
    /// packet information into their appropriate packet representation.
    /// Parses all of the following:
    /// - "[]" -> Packet::List([])
    /// - "[5]" -> Packet::List([Packet::Integer(5)])
    /// - "[1, 2]" -> Packet::List([Packet::Integer(1), Packet::Integer(2)])
    /// - "[1, [2]]" -> Packet::List([Packet::Integer(1), Packet::List([Packet::Integer(2)])])
    fn list(s: &str) -> IResult<&str, Packet> {
        let list_contents = separated_list0(tag(","), packet);
        map(delimited(tag("["), list_contents, tag("]")), Packet::List)(s)
    }

    /// Packet data consists of lists and integers. This parser will parse a `Packet`
    /// from a list or things or from a single integer.
    fn packet(s: &str) -> IResult<&str, Packet> {
        alt((integer, list))(s)
    }

    /// Parses two packets separated by a newline into a `PacketPair`
    fn packet_pair(s: &str) -> IResult<&str, PacketPair> {
        let (s, (first, second)) = separated_pair(packet, newline, packet)(s)?;
        Ok((s, PacketPair(first, second)))
    }

    /// Parses a list of packet pairs separated by an empty line into a `Vec<PacketPair>`
    pub fn parse(s: &str) -> Result<Vec<PacketPair>> {
        let result = separated_list1(tag("\n\n"), packet_pair)(s).finish();
        let (_, pair_list) = result.map_err(|e| anyhow!("{e}"))?;
        Ok(pair_list)
    }
}

const INPUT: &str = include_str!("../../input/13/input.txt");

/// Parse that input!
fn read() -> Vec<PacketPair> {
    parser::parse(INPUT).unwrap()
}

use std::cmp::Ordering;

/// Solve Day 13, Part 1
fn solve(input: &Vec<PacketPair>) -> u32 {
    let mut total = 0; // The total index value of proper sorted pairs

    // For each pair of packets...
    for (idx, packet_pair) in input.iter().enumerate() {
        // If it's not sorted correctly, skip.
        if !packet_pair.is_sorted() {
            continue;
        }

        // Otherwise, add the value of its index to the total
        total += (idx as u32) + 1; // Packets are 1-indexed
    }
    total
}

impl PacketPair {
    /// Indicates if the first packet in a pair is less than the second
    /// packet in the pair.
    fn is_sorted(&self) -> bool {
        let Self(first, second) = self;
        first < second
    }
}

/// Partial ordering for `Packet`s. Defining this would be enough to use
/// `Packet` < `Packet`, but we won't be able to do a full sort without
/// implementing `Ord` as well.
impl PartialOrd for Packet {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Defines the result of comparing one `Packet` to another, used for ordinal
/// comparisons and sorting. Returns an enum that indicates whether `self` is
/// less than, greater than, or even equal to `other`.
impl Ord for Packet {
    fn cmp(&self, other: &Self) -> Ordering {
        use Packet::*; // For syntax
        match (self, other) {
            // When comparing two packet integers, just compare them by value
            (Integer(i1), Integer(i2)) => i1.cmp(i2),

            // When comparing a packet integer to a packet list, convert the integer
            // to a single item list and compare the two lists.
            (Integer(i), List(_)) => List(vec![Integer(*i)]).cmp(other),
            (List(_), Integer(i)) => self.cmp(&List(vec![Integer(*i)])),

            // When comparing two lists, compare item by item and return the first
            // result where the two items aren't equal. If one list has more items
            // than another and all the values up to the length of the shortest list
            // are equal, then we compare the length of the lists.
            (List(l1), List(l2)) => {
                for (first, second) in l1.iter().zip(l2.iter()) {
                    let result = first.cmp(second);
                    let Ordering::Equal = result else { return result; };
                }
                l1.len().cmp(&l2.len())
            }
        }
    }
}

/// Solve Day 13, Part 2
fn solve(input: &Vec<PacketPair>) -> u32 {
    use Packet::*; // For syntax

    // Define the two divider packets and put them in an array to add them
    // to the list of all the packets.
    let divider1 = List(vec![List(vec![Integer(2)])]);
    let divider2 = List(vec![List(vec![Integer(6)])]);
    let dividers = [divider1, divider2];

    // Flatten all the pairs of packets into a list of packets with the two
    // divider packets added to the end.
    let mut all_packets = input
        .iter()
        .cloned()
        .flatten()
        .chain(dividers.iter().cloned())
        .collect::<Vec<_>>();

    // Sort all the packets! No need to do any more work than that, since
    // by implementing Ord and PartialOrd, we've done all we need to
    // sort them.
    all_packets.sort_unstable();

    // Find the indices of the two divider packets and return their product.
    let mut total = 1;
    for (idx, packet) in all_packets.iter().enumerate() {
        if dividers.contains(packet) {
            total *= (idx as u32) + 1;
        }
    }
    total
}

// It's easier to flatten the packet pairs into a 1D list when we can
// iterate over the two packets contained in them.
impl IntoIterator for PacketPair {
    type Item = Packet;
    type IntoIter = std::array::IntoIter<Self::Item, 2>;

    fn into_iter(self) -> Self::IntoIter {
        let PacketPair(first, second) = self;
        [first, second].into_iter()
    }
}