use cached::cached;
use rpds::rbt_set;
use rpds::vector::Vector;
use rpds::RedBlackTreeMap;
use rpds::RedBlackTreeMapSync;
use std::fmt;
use std::io;
use std::io::prelude::*;
use std::iter;
use std::iter::FromIterator;
use std::process;
use std::str::FromStr;
use structopt::StructOpt;

#[derive(Debug, StructOpt)]
#[structopt(name = "Day 22: Slam Shuffle")]
/// Shuffles some cards.
///
/// See https://adventofcode.com/2019/day/22 for details.
struct Opt {
    /// The size of the deck
    deck_size: usize,
    /// At the end, query the position of card
    card: usize,
}

fn main() {
    let stdin = io::stdin();
    let opt = Opt::from_args();

    let instructions = stdin
        .lock()
        .lines()
        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
        .map(|x| exit_on_failed_assertion(x.parse::<Instruction>(), "Parse error"))
        .collect::<Vec<Instruction>>();

    //eprintln!("{:?}", instructions);

    println!(
        "{}",
        Deck::new(opt.deck_size)
            .shuffle(&instructions)
            .find_position(opt.card)
    );
}

fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
    match data {
        Ok(data) => data,
        Err(e) => {
            eprintln!("{}: {}", message, e);
            process::exit(1);
        }
    }
}

#[derive(Clone)]
struct Deck {
    zero: usize,
    cards: Vector<usize>,
}

impl Deck {
    fn new(deck_size: usize) -> Self {
        Deck {
            zero: 0,
            cards: (0..deck_size).collect(),
        }
    }

    fn shuffle(&self, instructions: &[Instruction]) -> Deck {
        instructions.iter().fold(self.clone(), |deck, instruction| {
            //eprintln!("{} :: {}", deck.zero, deck.cards);
            deck.single_shuffle(instruction)
        })
    }

    fn single_shuffle(&self, instruction: &Instruction) -> Deck {
        match instruction {
            Instruction::DealIntoNewStack => Deck {
                cards: (0..self.cards.len())
                    .map(|i| self.at(self.cards.len() - i - 1))
                    .collect(),
                zero: 0,
            },
            Instruction::Cut(n) => Deck {
                zero: mod_plus(self.zero, *n, self.cards.len()),
                ..self.clone()
            },
            Instruction::ReverseCut(n) => Deck {
                zero: mod_sub(self.zero, *n, self.cards.len()),
                ..self.clone()
            },
            Instruction::DealWithIncrement(n) => Deck {
                cards: (0..self.cards.len())
                    .map(|i| self.at(*layout_after_shift(*n, self.cards.len()).get(&i).unwrap()))
                    .collect(),
                zero: 0,
            },
        }
    }

    fn at(&self, index: usize) -> usize {
        self.cards[mod_plus(index, self.zero, self.cards.len())]
    }

    fn find_position(&self, value: usize) -> usize {
        mod_sub(
            self.cards.iter().position(|x| *x == value).unwrap(),
            self.zero,
            self.cards.len(),
        )
    }
}

fn mod_plus(a: usize, b: usize, modulus: usize) -> usize {
    (a + b) % modulus
}

fn mod_sub(a: usize, b: usize, modulus: usize) -> usize {
    (a + modulus - b) % modulus
}

fn mod_times(a: usize, b: usize, modulus: usize) -> usize {
    (a * b) % modulus
}

cached! {
    LAYOUT_AFTER_SHIFT;
    fn layout_after_shift(n: usize, modulus: usize) -> RedBlackTreeMapSync<usize, usize> = {
        (0..modulus).fold(RedBlackTreeMapSync::new_sync(), |acc, next| {
            acc.insert(mod_times(next, n, modulus), next)
        })
    }
}

#[derive(Debug)]
enum Instruction {
    DealIntoNewStack,
    Cut(usize),
    ReverseCut(usize),
    DealWithIncrement(usize),
}

impl FromStr for Instruction {
    type Err = ParseErr;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if s.starts_with("deal into new stack") {
            Ok(Instruction::DealIntoNewStack)
        } else if s.starts_with("cut -") {
            s.split(' ')
                .nth(1)
                .map(|val| {
                    val.parse::<isize>()
                        .map_err(|_| ParseErr)
                        .map(|parsed| Instruction::ReverseCut(parsed.abs() as usize))
                })
                .unwrap_or(Err(ParseErr))
        } else if s.starts_with("cut") {
            s.split(' ')
                .nth(1)
                .map(|val| {
                    val.parse::<usize>()
                        .map_err(|_| ParseErr)
                        .map(|parsed| Instruction::Cut(parsed))
                })
                .unwrap_or(Err(ParseErr))
        } else if s.starts_with("deal with increment") {
            s.split(' ')
                .nth(3)
                .map(|val| {
                    val.parse::<usize>()
                        .map_err(|_| ParseErr)
                        .map(|parsed| Instruction::DealWithIncrement(parsed))
                })
                .unwrap_or(Err(ParseErr))
        } else {
            Err(ParseErr)
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct ParseErr;

impl fmt::Display for ParseErr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Error parsing input")
    }
}

impl std::error::Error for ParseErr {}