Day 22 part 1, modular shuffling

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 {}