/// Represents a gust from the jets of gas, either to the left or right.
#[derive(Debug, Clone, Copy)]
enum Gust {
    Left,
    Right,
}

/// An iterator that produces gusts of gas in an repeating cycle
#[derive(Debug, Clone)]
struct GasJetIter {
    iter: Vec<Gust>,
    pub idx: usize,
}

/// Iterator implementation for `GasJetIter`. Just returns the values contained
/// in a repeating cycle.
impl Iterator for GasJetIter {
    type Item = Gust;

    fn next(&mut self) -> Option<Self::Item> {
        let result = Some(self.iter[self.idx]);
        self.idx = (self.idx + 1) % self.iter.len();
        result
    }
}

/// Convert a list of `Gust`s into a `GasJetIter`
impl From<Vec<Gust>> for GasJetIter {
    fn from(iter: Vec<Gust>) -> Self {
        GasJetIter {
            iter,
            idx: Default::default(),
        }
    }
}

/// Module to wrap the parsing functions for today's puzzle
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        character::complete::char,
        combinator::{map, value},
        multi::many1,
        Finish, IResult,
    };

    /// Nom parser for '<' -> Gust::Left
    fn push_left(s: &str) -> IResult<&str, Gust> {
        value(Gust::Left, char('<'))(s)
    }

    /// Nom parser for '>' -> Gust::Right
    fn push_right(s: &str) -> IResult<&str, Gust> {
        value(Gust::Right, char('>'))(s)
    }

    /// Nom parser for a Gust in either direction
    fn push(s: &str) -> IResult<&str, Gust> {
        alt((push_left, push_right))(s)
    }

    /// Nom parser for a list of Gusts
    fn pushes(s: &str) -> IResult<&str, Vec<Gust>> {
        many1(push)(s)
    }

    /// Nom parser to map a GasJetIter to a list of Gusts
    fn gas_jet_iter(s: &str) -> IResult<&str, GasJetIter> {
        map(pushes, GasJetIter::from)(s)
    }

    /// Main parsing function, attempts to parse the input into a GasJetIter and 
    /// return it.
    pub fn parse(s: &str) -> Result<GasJetIter> {
        let (_, result) = gas_jet_iter(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

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

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

/// Solve Day 17, Part 1
fn solve(input: &GasJetIter) -> u32 {
    // We need an owned copy of the iterator so we can use it in both parts
    let mut gas_jets = input.to_owned();
    let total_rocks = 2022;

    // Since the maximum height of any rock is 4, a chamber than can hold
    // up to rocks * 4 levels will be plenty big enough.
    let mut chamber = Chamber::with_capacity(total_rocks * 4);

    // Produce rocks of the appropriate shape in a cycle, up to `total_rocks`
    // times.
    for rock in Rock::all().iter().cycle().take(total_rocks) {
        chamber.add_rock(&mut gas_jets, *rock);
    }

    // Repor the total height of the rocks in the chamber
    chamber.height() as u32
}

// You'll note that we're storing rocks as u32 integers. This makes collision
// checking much easier, as well as adding rocks to the chamber. It does, however
// make _reading_ the code a bit more difficult. These are the 32-bit integers
// that represent the column just to the left of the left wall and the column
// just to the right of the right wall. If any part of our rock overlaps one of 
// those spaces and the wind tries to push it in the corresponding direction,
// it won't move over.
const LEFT_WALL: u32 = 0x40404040;
const RIGHT_WALL: u32 = 0x01010101;

/// Represents one of the rocks.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Rock(u32);

impl Rock {
    /// Produce a list of all five rock shapes, in order. This is what they look
    /// like in octal. Printed out in binary one byte at a time, with each byte 
    /// on a new line, they look like this (using . instead of 0 to make it easier
    /// to see):
    ///
    /// ...1111.  ....1...  .....1..  ...1....  ...11...
    /// ........  ...111..  .....1..  ...1....  ...11...
    /// ........  ....1...  ...111..  ...1....  ........
    /// ........  ........  ........  ...1....  ........
    const fn all() -> [Self; 5] {
        [
            Self(0x0000001E), // -
            Self(0x00081C08), // +
            Self(0x0004041C), // L
            Self(0x10101010), // |
            Self(0x00001818), // #
        ]
    }

    /// Try to move a rock over to the left or right from a gas jet
    /// within the chamber.
    fn shove(&mut self, push: Gust, levels: u32) {
        // Get a copy of the rock bits
        let mut pushed = self.0;

        match push {
            // If pushed to the left and not against the wall, move the rock
            // to the left.
            Gust::Left => {
                if self.0 & LEFT_WALL == 0 {
                    pushed = self.0 << 1
                }
            }

            // If pushed to the right and not against the wall, move the rock
            // to the right.
            Gust::Right => {
                if self.0 & RIGHT_WALL == 0 {
                    pushed = self.0 >> 1
                }
            }
        }

        // If the pushed rock isn't colliding with anything in the same levels
        // as it in the chamber, then update the rock's horizontal position.
        if pushed & levels == 0 {
            self.0 = pushed
        }
    }

    /// Check to see if this rock collides with another object. 
    fn collides(&self, other: u32) -> bool {
        self.0 & other > 0
    }

    /// Produce the bytes of the rock in order, skipping the empty bytes
    fn bytes(&self) -> impl Iterator<Item = u8> {
        self.0.to_le_bytes().into_iter().take_while(|b| *b > 0)
    }
}

/// Represents the chamber where the rocks are being dropped
#[derive(Debug, Default, Clone)]
struct Chamber(Vec<u8>);

impl Chamber {
    /// Create a new chamber with a set capacity
    fn with_capacity(n: usize) -> Self {
        Self(Vec::with_capacity(n))
    }

    /// Report the height of the rocks in the chamber
    fn height(&self) -> usize {
        self.0.len()
    }

    /// Add a new level (byte) to the chamber
    fn push(&mut self, level: u8) {
        self.0.push(level)
    }

    /// Get a 4-wide chunk of bytes from the chamber, starting at `level`.
    fn get_level_chunk(&self, level: usize) -> u32 {
        if level >= self.0.len() {
            return 0;
        }

        // Starting at `level`, take up to four bytes from the chamber, reverse
        // the production (so that the chunk is right-side up) of bytes, then 
        // convert the four bytes into a single u32 by shifting existing bits
        // left and adding each new byte to the first 8 bits after the shift.
        self.0
            .iter()
            .skip(level)
            .take(4)
            .rev()
            .fold(0, |acc, byte| (acc << 8) | *byte as u32)
    }

    /// Add a rock to the top of the chamber and allow it to fall until it
    /// comes to rest on another rock or the floor.
    fn add_rock(&mut self, gas_jets: &mut GasJetIter, mut rock: Rock) {

        // Start the rock out three levels above the top of chamber, which is
        // the top level with any rock parts.
        let mut level = self.height() + 3;

        // Until the rock comes to rest...
        loop {
            // Get the chunk of chamber levels starting at `level`
            let levels = self.get_level_chunk(level);

            // Get the next gust from the gas jets
            let jet = gas_jets.next().unwrap();

            // Attempt to shove the rock over
            rock.shove(jet, levels);

            // If the current level is above the highest level with a rock in it
            // in the chamber, drop the level and shove the rock again.
            if level > self.height() {
                level -= 1;
                continue;
            }

            // Now get the chunk of the chamber starting one level below where
            // we started. This simulates the rock dropping down one level.
            let levels = self.get_level_chunk(level.saturating_sub(1));

            // Check to see if the rock would collide with anything if it moved down.
            let collision = rock.collides(levels);

            // If we reached the floor or would collide with another rock...
            if level == 0 || collision {

                // Add the rock to the chamber, layer by layer. Where there's a
                // chamber level already there for the layer of rock we're adding,
                // just add the layer of rock to the level. Otherwise, push the 
                // layer to the top of the chamber's bytes.
                for byte in rock.bytes() {
                    if level < self.height() {
                        self.0[level] |= byte;
                    } else {
                        self.push(byte);
                    }
                    level += 1;
                }
                break;
            }

            // If the rock doesn't need to stop due to the floor or collision, keep
            // going, dropping the rock another level and going again.
            level -= 1;
        }
    }
}

use std::collections::HashMap;

/// Solve Day 17, Part 2
fn solve(input: &GasJetIter) -> u32 {
    // We need an owned copy of the iterator so we can use it in both parts
    let mut gas_jets = input.to_owned();
    let total_rocks = 1_000_000_000_000; // That's a _lot_ of rocks...
    let mut rocks_added = 0; // Number of rocks added to the chamber

    // Keep up with the states we've seen of the chamber before. The state includes
    // the top 8 levels of the chamber, the shape of the last rock added to the 
    // chamber, and the current internal index of the `gas_jets`.
    let mut seen = HashMap::with_capacity(2048);

    // Why use 2048 as the capacity now? It's larger than the repeat length of the
    // chamber. What repeat length? Well, as it turns out, typically when Advent of
    // Code asks you what the state of some data structure will be one bazillion
    // iterations later, there's probably a cycle in the state of the data structure
    // somewhere that can be used to calculate the final state without needing to
    // simulate each step. In my case, the state of the top layers of the chamber
    // repeated every 1700 rocks dropped or so.
    let mut chamber = Chamber::with_capacity(2048);

    // How much height has been accumulated so far?
    let mut accumulated_height = 0;

    // An iterator to produce rocks of the appropriate shape in a cycle.
    let mut rock_types = Rock::all().into_iter().cycle();

    // Until we've added all gajillion rocks...
    while rocks_added < total_rocks {

        // Get the next rock, add it to the chamber, account for it, and if the 
        // chamber has fewer than 8 levels, do it again. We're checking the state
        // based on the top 8 levels, so no checking until we have at least 8 levels.
        let rock = rock_types.next().unwrap();
        chamber.add_rock(&mut gas_jets, rock);
        rocks_added += 1;
        if chamber.height() < 8 {
            continue;
        }

        // Check to see if we've seen this state of the top 8 levels of the chamber
        // before. If so, time to use that cycle!
        let state = (chamber.skyline(), rock, gas_jets.idx);
        if let Some((prev_rocks_added, prev_height)) = seen.get(&state) {
            // The number of rocks added in each repeating cycle.
            let repeat_len: usize = rocks_added - prev_rocks_added;

            // The number of repeats left before we add the final rock.
            let repeats: usize = (total_rocks - rocks_added) / repeat_len;

            // Add all the rocks in all the repeating cycles between here and the end.
            rocks_added += repeat_len * repeats;

            // Add the chamber height of the cycle to the accumulated height
            accumulated_height += repeats * (chamber.height() - prev_height);

            // Clear the map of seen states. We don't want to do everything inside
            // this `if` block again on the next iteration, after all.
            seen.clear();
            continue;
        }

        // If we haven't seen this state before, add it to the map and keep going.
        seen.insert(state, (rocks_added, chamber.height()));
    }

    // Report the current height of the chamber and the accumulated height from all
    // the cycles. The chamber will contain all the rocks dropped up to the start
    // of the second repetition of the cycle, then all the rocks that would be
    // dropped after the last full cycle ended.
    (chamber.height() as u64 + accumulated_height as u64).into()
}

impl Chamber {
    /// Get the 'skyline' of the top of the chamber. Really, it's just a u64 with 
    /// bits representing the top 8 levels of the chamber.
    fn skyline(&self) -> Option<u64> {

        // If the chamber is less than 8 levels tall, we can't take a skyline
        if self.height() < 8 {
            return None;
        }

        // Take the top 8 levels of the chamber and fold them into a 64-bit integer.
        let result = self
            .0
            .iter()
            .rev()
            .take(8)
            .fold(0u64, |acc, byte| (acc << 8) | *byte as u64);
        Some(result)
    }
}