use num::bigint::BigInt;
use num::traits::identities::Zero;
use num::traits::sign::abs;
use std::fmt;
use std::io;
use std::io::prelude::*;
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: BigInt,
    /// At the end, query the position of card
    card: BigInt,
    /// Number of repetitions
    repetitions: usize,

    /// Prints the card in position n, rather than the position of card n
    #[structopt(short = "p")]
    position_mode: bool,
}

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);

    if opt.position_mode {
        println!(
            "{}",
            Card {
                position: opt.card,
                modulus: opt.deck_size
            }
            .shuffle_reverse(&instructions, opt.repetitions)
            .position
        );
    } else {
        println!(
            "{}",
            Card {
                position: opt.card,
                modulus: opt.deck_size
            }
            .shuffle(&instructions, opt.repetitions)
            .position
        );
    }
}

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 Card {
    position: BigInt,
    modulus: BigInt,
}

impl Card {
    fn shuffle(&self, instructions: &[Instruction], repetitions: usize) -> Card {
        (0..repetitions).fold(self.clone(), |acc, _| {
            instructions.iter().fold(acc, |card, instruction| {
                //eprintln!("{} :: {}", deck.zero, deck.cards);
                card.single_shuffle(instruction)
            })
        })
    }

    fn single_shuffle(&self, instruction: &Instruction) -> Card {
        match instruction {
            Instruction::DealIntoNewStack => Card {
                position: self.modulus.clone() - self.position.clone() - 1,
                modulus: self.modulus.clone(),
            },
            Instruction::Cut(n) => Card {
                position: mod_sub(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
            Instruction::ReverseCut(n) => Card {
                position: mod_plus(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
            Instruction::DealWithIncrement(n) => Card {
                position: mod_times(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
        }
    }

    fn shuffle_reverse(&self, instructions: &[Instruction], repetitions: usize) -> Card {
        (0..repetitions).fold(self.clone(), |acc, _| {
            instructions.iter().rev().fold(acc, |card, instruction| {
                //eprintln!("{} :: {}", deck.zero, deck.cards);
                card.single_shuffle_reverse(instruction)
            })
        })
    }

    fn single_shuffle_reverse(&self, instruction: &Instruction) -> Card {
        match instruction {
            Instruction::DealIntoNewStack => Card {
                position: self.modulus.clone() - self.position.clone() - 1,
                modulus: self.modulus.clone(),
            },
            Instruction::Cut(n) => Card {
                position: mod_plus(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
            Instruction::ReverseCut(n) => Card {
                position: mod_sub(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
            Instruction::DealWithIncrement(n) => Card {
                position: mod_divide(self.position.clone(), n.clone(), self.modulus.clone()),
                modulus: self.modulus.clone(),
            },
        }
    }
}

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

fn mod_sub(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt {
    (a + modulus.clone() - b) % modulus
}

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

fn mod_divide(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt {
    mod_times(a, mod_inverse(b, modulus.clone()), modulus)
}

// NB: This may give nonsense if modulus isn't coprime with a
fn mod_inverse(a: BigInt, modulus: BigInt) -> BigInt {
    (euclid_gcd_coefficients(a, modulus.clone()).0 + modulus.clone()) as BigInt % modulus
}

fn euclid_gcd_coefficients(a: BigInt, b: BigInt) -> (BigInt, BigInt) {
    fn euclid_gcd_coefficients_inner(
        r: BigInt,
        old_r: BigInt,
        s: BigInt,
        old_s: BigInt,
        t: BigInt,
        old_t: BigInt,
    ) -> (BigInt, BigInt) {
        if r.is_zero() {
            (old_s, old_t)
        } else {
            euclid_gcd_coefficients_inner(
                old_r.clone() - (old_r.clone() / r.clone()) * r.clone(),
                r.clone(),
                old_s - (old_r.clone() / r.clone()) * s.clone(),
                s,
                old_t - (old_r.clone() / r) * t.clone(),
                t,
            )
        }
    }

    assert!(a < b);

    euclid_gcd_coefficients_inner(b, a, 0.into(), 1.into(), 1.into(), 0.into())
}

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

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::<BigInt>()
                        .map_err(|_| ParseErr)
                        .map(|parsed| Instruction::ReverseCut(abs(parsed)))
                })
                .unwrap_or(Err(ParseErr))
        } else if s.starts_with("cut") {
            s.split(' ')
                .nth(1)
                .map(|val| {
                    val.parse::<BigInt>()
                        .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::<BigInt>()
                        .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 {}

#[test]
fn mod_inverse_of_13() {
    assert_eq!(mod_inverse(1.into(), 13.into()), 1.into());
    assert_eq!(mod_inverse(2.into(), 13.into()), 7.into());
    assert_eq!(mod_inverse(3.into(), 13.into()), 9.into());
    assert_eq!(mod_inverse(4.into(), 13.into()), 10.into());
    assert_eq!(mod_inverse(5.into(), 13.into()), 8.into());
    assert_eq!(mod_inverse(6.into(), 13.into()), 11.into());
    assert_eq!(mod_inverse(7.into(), 13.into()), 2.into());
    assert_eq!(mod_inverse(8.into(), 13.into()), 5.into());
    assert_eq!(mod_inverse(9.into(), 13.into()), 3.into());
    assert_eq!(mod_inverse(10.into(), 13.into()), 4.into());
    assert_eq!(mod_inverse(11.into(), 13.into()), 6.into());
    assert_eq!(mod_inverse(12.into(), 13.into()), 12.into());
}