use anyhow::{anyhow, bail, Error, Result};

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

// Today we'll do a bit of math converting ASCII characters to numbers.
// These constants are used in that math. For references, ASCII 'a' corresponds
// to a value of 97, and ASCII 'A' corresponds to a value of 65.
const LOWERCASE_OFFSET: u32 = 96; // 'a' -> 97 - 1 (priority of 'a') = 96
const CAPITAL_OFFSET: u32 = 38; // 'A' -> 65 - 26 (priority of 'A') = 38

/// A `Rucksack` represents a pack carried by an elf with two different,
/// separated sets of `Item`s.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Rucksack(ItemSet, ItemSet);

/// Attempt to convert a line from the input into a `Rucksack`
impl TryFrom<&str> for Rucksack {
    type Error = Error;

    fn try_from(s: &str) -> Result<Self, Self::Error> {
        // Because the input lines contain two equal-length strings of
        // characters representing `Item`s, we need the length of each
        // half.
        let compartment_len = s.len() / 2;

        // Split the line into two equal-length strings
        let (str1, str2) = s.split_at(compartment_len);

        // Convert each string into a set of `Item`s
        let compartment1 = ItemSet::try_from(str1)?;
        let compartment2 = ItemSet::try_from(str2)?;

        // Return a `Rucksack` with two sets of items
        Ok(Rucksack(compartment1, compartment2))
    }
}

/// An `ItemSet` represents the unique items held in each compartment of a
/// `Rucksack`. The goal is to provide functionality equivalent to a
/// `HashSet<Item>` (at least as much as we need) without the overhead
/// of an actual `HashSet`. This is accomplished by assigning each type of
/// `Item` to a particular bit in the inner `u64`.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
pub struct ItemSet(u64);

impl ItemSet {
    /// Insert an `Item` into an `ItemSet`.
    fn insert(&mut self, item: Item) {
        // Set the bit in the `ItemSet` that corresponds to the particular type
        // of `Item`.
        self.0 |= item.0;
    }
}

/// Attempt to convert a string slice into a set of `Item`s.
impl TryFrom<&str> for ItemSet {
    type Error = Error;

    fn try_from(value: &str) -> Result<Self, Self::Error> {
        // Start with an empty item set
        let mut item_set = ItemSet::default();

        // Convert each character in the input string into an `Item` and
        // insert each `Item` into the set
        for ch in value.chars() {
            let item = Item::try_from(ch)?;
            item_set.insert(item);
        }

        Ok(item_set)
    }
}

/// An `Item` represents a particular item carried by the elves. Because the puzzle
/// specifies that there are only 52 possible item types, each item can be uniquely
/// represented by a single set bit in a `u64` with 6 extra bits to spare. We'll set
/// bits in order of increasing priority, starting with 'a' at 2^1. This way, the
/// number of trailing zeros will be equal to priority. So, 'a' will be stored as
/// 2u64 with 1 trailing zero, and 'A' will be stored as 134217728u64 with 27 trailing
/// zeros.
///
/// Just for excessive clarity, 2u64 is represented in bits as:
/// 0b00000000000000000000000000000000000000000000000000000000000010
///
/// 134217728u64 is represented in bits as:
/// 0b00000000000000000000000000000000001000000000000000000000000000
#[derive(Debug, Clone, Copy)]
pub struct Item(u64);

/// Attempt to convert a single character into an `Item`
impl TryFrom<char> for Item {
    type Error = Error;

    fn try_from(value: char) -> Result<Self, Self::Error> {
        // Error if trying to make an `Item` out of any character that's not a letter
        if !value.is_alphabetic() { bail!("Cannot convert {value} to an Item!") }

        // Offset for ASCII range starts and priority offset.
        let offset = if value > 'Z' { LOWERCASE_OFFSET } else { CAPITAL_OFFSET };
        let priority = value as u32 - offset;
        let set_bit = 1 << priority; // One bit, shifted left by priority

        Ok(Item(set_bit))
    }
}

/// Read and parse the input
pub fn read() -> Vec<Rucksack> {
    // Attempt to convert each line into a `Rucksack` and return the
    // list of successful results.
    INPUT.lines().flat_map(Rucksack::try_from).collect()
}

use anyhow::{bail, Error, Result};

/// Solve Day 3, Part 1
pub fn solve(input: &Input) -> u32 {
    // For each `Rucksack`, identify the one item in common between the
    // compartments, calculate that item's priority, and return the sum
    // of all unique item priorities.
    input
        .iter()
        .flat_map(|r| r.one_in_common())
        .map(|i| i.priority())
        .sum::<u32>()
}

impl Rucksack {
    /// Attempt to identify the one `Item` in common between both compartments.
    fn one_in_common(&self) -> Result<Item> {
        self.0.intersect(self.1).try_into()
    }
}

impl ItemSet {
    /// Construct an `ItemSet` that contains only items in common between
    /// `self` and `other`. Just a bitwise _and_ on the underlying integers.
    fn intersect(&self, other: ItemSet) -> ItemSet {
        ItemSet(self.0 & other.0)
    }
}

/// Attempt to convert an `ItemSet` into a single `Item`.
/// Fails and returns an Error if the `ItemSet` contains more than one item.
impl TryFrom<ItemSet> for Item {
    type Error = Error;

    fn try_from(set: ItemSet) -> Result<Self, Self::Error> {
        if set.0.count_ones() > 1 {
            bail!("{set:?} contains more than one item!")
        }
        Ok(Item(set.0))
    }
}

impl Item {
    /// Calculate the priority of the `Item`. Recall each `Item` is represented
    /// by a single bit shifted left by priority, so priority is just the
    /// number of trailing zeros.
    fn priority(&self) -> u32 {
        self.0.trailing_zeros()
    }
}

use anyhow::Result;
use itertools::Itertools;

pub fn solve(input: &Input) -> u32 {
    let mut total = 0; // The sum of badge priorities

    // Convert each `Rucksack` to an `ItemSet` consisting of all its unique
    // `Item`s, as an iterator.
    let rucksack_sets = input.iter().map(|r| r.all_items());

    // For each chunk of three rucksack_sets in sequence...
    for chunk in &rucksack_sets.chunks(3) {
        // Produce an `ItemSet` that is the intersection of all three sets
        // in the chunk. If the chunk is empty, we get an empty `ItemSet` back.
        let intersect = chunk
            .reduce(|acc, i| acc.intersect(i))
            .unwrap_or(ItemSet(0));

        // Attempt to convert the `ItemSet` into a single Item. Panic if
        // the chunk contains more than one common item. The puzzle text
        // assures us this won't happen.
        let badge = Item::try_from(intersect).expect("{intersect:?} contains multiple Items!");

        // Add the priority of the badge to the total
        total += badge.priority();
    }

    total
}

impl Rucksack {
    /// Return an `ItemSet` comprised of the items in both compartments of
    /// the `Rucksack`. Recall that this is a set, so duplicates aren't counted.
    fn all_items(&self) -> ItemSet {
        ItemSet(self.0 .0 | self.1 .0)
    }
}