From f6995e330034d87473ed2d297f6a993b103b0556 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 1 Jan 2020 14:28:52 +0200 Subject: Day 22 part 1, modular shuffling --- inputs/day_22.txt | 100 ++++++++++++++++++++++++++++ src/bin/day_22.rs | 193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 293 insertions(+) create mode 100644 inputs/day_22.txt create mode 100644 src/bin/day_22.rs diff --git a/inputs/day_22.txt b/inputs/day_22.txt new file mode 100644 index 0000000..b61e760 --- /dev/null +++ b/inputs/day_22.txt @@ -0,0 +1,100 @@ +deal with increment 34 +deal into new stack +cut 1712 +deal into new stack +cut 1984 +deal with increment 62 +deal into new stack +deal with increment 13 +deal into new stack +deal with increment 67 +cut -5590 +deal with increment 63 +cut -1086 +deal with increment 52 +cut 7894 +deal with increment 71 +cut -864 +deal into new stack +cut 239 +deal with increment 17 +cut -7187 +deal with increment 62 +deal into new stack +cut -7380 +deal with increment 14 +cut 3842 +deal into new stack +cut -5258 +deal with increment 40 +deal into new stack +deal with increment 45 +cut -6026 +deal with increment 21 +cut 3600 +deal with increment 56 +cut 2329 +deal into new stack +deal with increment 13 +cut -2409 +deal with increment 49 +cut 294 +deal into new stack +cut 4776 +deal with increment 17 +cut 5801 +deal with increment 43 +cut 8999 +deal with increment 46 +cut -8527 +deal with increment 4 +deal into new stack +cut -6767 +deal into new stack +deal with increment 33 +cut -532 +deal with increment 29 +deal into new stack +deal with increment 56 +cut 6867 +deal with increment 70 +cut 4276 +deal into new stack +cut -5621 +deal with increment 56 +cut -2966 +deal with increment 70 +deal into new stack +deal with increment 51 +cut -4097 +deal with increment 42 +deal into new stack +cut -5180 +deal with increment 61 +deal into new stack +cut 5367 +deal with increment 50 +cut 3191 +deal with increment 75 +cut 915 +deal with increment 72 +cut -3893 +deal with increment 22 +cut -3405 +deal with increment 30 +cut -6509 +deal with increment 31 +cut -7220 +deal with increment 45 +cut 6489 +deal with increment 70 +cut -4047 +deal into new stack +deal with increment 75 +cut 3980 +deal with increment 10 +cut 9677 +deal into new stack +deal with increment 45 +cut -6969 +deal into new stack 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::(), "Parse error")) + .collect::>(); + + //eprintln!("{:?}", instructions); + + println!( + "{}", + Deck::new(opt.deck_size) + .shuffle(&instructions) + .find_position(opt.card) + ); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Clone)] +struct Deck { + zero: usize, + cards: Vector, +} + +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 = { + (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 { + 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::() + .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::() + .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::() + .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 {} -- cgit v1.2.3