diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bin/day_22.rs | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/src/bin/day_22.rs b/src/bin/day_22.rs new file mode 100644 index 0000000..cadfac4 --- /dev/null +++ b/src/bin/day_22.rs @@ -0,0 +1,193 @@ +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 {} |