//! # Day 15: Rambunctious Recitation
//!
//! You catch the airport shuttle and try to book a new flight to your vacation island. Due to the
//! storm, all direct flights have been cancelled, but a route is available to get around the storm.
//! You take it.
//!
//! While you wait for your flight, you decide to check in with the Elves back at the North Pole.
//! They're playing a **memory game** and are ever so excited to explain the rules!
//!
//! In this game, the players take turns saying **numbers**. They begin by taking turns reading from
//! a list of **starting numbers** (your puzzle input). Then, each turn consists of considering the
//! **most recently spoken number**:
//!
//! - If that was the **first** time the number has been spoken, the current player says **`0`**.
//! - Otherwise, the number had been spoken before; the current player announces **how many turns
//!   apart** the number is from when it was previously spoken.
//!
//! So, after the starting numbers, each turn results in that player speaking aloud either **`0`**
//! (if the last number is new) or an **age** (if the last number is a repeat).
//!
//! For example, suppose the starting numbers are `0,3,6`:
//!
//! - **Turn 1**: The `1`st number spoken is a starting number, **`0`**.
//! - **Turn 2**: The `2`nd number spoken is a starting number, **`3`**.
//! - **Turn 3**: The `3`rd number spoken is a starting number, **`6`**.
//! - **Turn 4**: Now, consider the last number spoken, `6`. Since that was the first time the
//!   number had been spoken, the `4`th number spoken is **`0`**.
//! - **Turn 5**: Next, again consider the last number spoken, `0`. Since it **had** been spoken
//!   before, the next number to speak is the difference between the turn number when it was last
//!   spoken (the previous turn, `4`) and the turn number of the time it was most recently spoken
//!   before then (turn `1`). Thus, the `5`th number spoken is `4 - 1`, **`3`**.
//! - **Turn 6**: The last number spoken, `3` had also been spoken before, most recently on turns
//!   `5` and `2`. So, the `6`th number spoken is `5 - 2`, **`3`**.
//! - **Turn 7**: Since `3` was just spoken twice in a row, and the last two turns are `1` turn
//!   apart, the `7`th number spoken is **`1`**.
//! - **Turn 8**: Since `1` is new, the `8`th number spoken is **`0`**.
//! - **Turn 9**: `0` was last spoken on turns `8` and `4`, so the `9`th number spoken is the
//!   difference between them, **`4`**.
//! - **Turn 10**: `4` is new, so the `10`th number spoken is **`0`**.
//!
//! (The game ends when the Elves get sick of playing or dinner is ready, whichever comes first.)
//!
//! Their question for you is: what will be the **`2020`th** number spoken? In the example above,
//! the `2020`th number spoken will be `436`.
//!
//! Here are a few more examples:
//!
//! - Given the starting numbers `1,3,2`, the `2020`th number spoken is `1`.
//! - Given the starting numbers `2,1,3`, the `2020`th number spoken is `10`.
//! - Given the starting numbers `1,2,3`, the `2020`th number spoken is `27`.
//! - Given the starting numbers `2,3,1`, the `2020`th number spoken is `78`.
//! - Given the starting numbers `3,2,1`, the `2020`th number spoken is `438`.
//! - Given the starting numbers `3,1,2`, the `2020`th number spoken is `1836`.
//!
//! Given your starting numbers, **what will be the `2020`th number spoken?**
//!
//! ## Part Two
//!
//! Impressed, the Elves issue you a challenge: determine the `30000000`th number spoken. For
//! example, given the same starting numbers as above:
//!
//! - Given `0,3,6`, the `30000000`th number spoken is `175594`.
//! - Given `1,3,2`, the `30000000`th number spoken is `2578`.
//! - Given `2,1,3`, the `30000000`th number spoken is `3544142`.
//! - Given `1,2,3`, the `30000000`th number spoken is `261214`.
//! - Given `2,3,1`, the `30000000`th number spoken is `6895259`.
//! - Given `3,2,1`, the `30000000`th number spoken is `18`.
//! - Given `3,1,2`, the `30000000`th number spoken is `362`.
//!
//! Given your starting numbers, **what will be the `30000000`th number spoken?**

use ahash::AHashMap;
use anyhow::{Context, Result};

pub const INPUT: &str = include_str!("d15.txt");

pub fn solve_part_one(input: &str) -> Result<u32> {
    Ok(solve(parse_input(input)?, 2020))
}

pub fn solve_part_two(input: &str) -> Result<u32> {
    Ok(solve(parse_input(input)?, 30_000_000))
}

fn parse_input(input: &str) -> Result<Vec<u32>> {
    input
        .lines()
        .next()
        .context("input is empty")?
        .split(',')
        .map(|d| d.parse().map_err(Into::into))
        .collect()
}

fn solve(input: Vec<u32>, final_turn: u32) -> u32 {
    let mut memory = AHashMap::default();
    let mut turn = 1;
    let mut last_number = 0;

    for i in input {
        memory.insert(i, turn);
        turn += 1;
    }

    while turn < final_turn {
        let number = if let Some(t) = memory.get(&last_number) { turn - t } else { 0 };
        memory.insert(last_number, turn);

        turn += 1;
        last_number = number;
    }

    last_number
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part_one() {
        assert_eq!(436, solve_part_one("0,3,6").unwrap());
        assert_eq!(1, solve_part_one("1,3,2").unwrap());
        assert_eq!(10, solve_part_one("2,1,3").unwrap());
        assert_eq!(27, solve_part_one("1,2,3").unwrap());
        assert_eq!(78, solve_part_one("2,3,1").unwrap());
        assert_eq!(438, solve_part_one("3,2,1").unwrap());
        assert_eq!(1836, solve_part_one("3,1,2").unwrap());
    }

    #[test]
    fn part_two() {
        assert_eq!(175_594, solve_part_two("0,3,6").unwrap());
        assert_eq!(2578, solve_part_two("1,3,2").unwrap());
        assert_eq!(3_544_142, solve_part_two("2,1,3").unwrap());
        assert_eq!(261_214, solve_part_two("1,2,3").unwrap());
        assert_eq!(6_895_259, solve_part_two("2,3,1").unwrap());
        assert_eq!(18, solve_part_two("3,2,1").unwrap());
        assert_eq!(362, solve_part_two("3,1,2").unwrap());
    }
}