year2019/
day22.rs

1use utils::number::{mod_inverse, mod_pow};
2use utils::prelude::*;
3
4/// Composing card shuffles.
5#[derive(Clone, Debug)]
6pub struct Day22 {
7    part1_shuffle: Shuffle<PART1_DECK_SIZE>,
8    part2_shuffle: Shuffle<PART2_DECK_SIZE>,
9}
10
11#[derive(Copy, Clone, Debug)]
12enum Technique {
13    DealIntoNewStack,
14    Cut(i32),
15    DealWithIncrement(u32),
16}
17
18#[derive(Copy, Clone, Debug)]
19struct Shuffle<const DECK_SIZE: u64> {
20    multiplier: u64,
21    offset: u64,
22}
23
24const PART1_DECK_SIZE: u64 = 10_007;
25const PART1_CARD: u64 = 2_019;
26const PART2_DECK_SIZE: u64 = 119_315_717_514_047;
27const PART2_REPEATS: u64 = 101_741_582_076_661;
28const PART2_POSITION: u64 = 2_020;
29
30impl Day22 {
31    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
32        if input.is_empty() {
33            return Err(InputError::new(input, 0, "expected at least one technique"));
34        }
35
36        // The increment must be coprime with the deck size to reverse the shuffle for part 2.
37        // Both deck sizes are prime, and the part 2 size is larger than u32::MAX, so a u32 value
38        // only needs checking against the part 1 deck size.
39        let increment = parser::u32().map_res(|n| {
40            (!n.is_multiple_of(PART1_DECK_SIZE as u32))
41                .then_some(n)
42                .ok_or("expected increment to be coprime with the deck sizes")
43        });
44        let technique = parser::parse_tree!(
45            ("deal into new stack") => Technique::DealIntoNewStack,
46            ("cut ", n @ parser::i32()) => Technique::Cut(n),
47            ("deal with increment ", n @ increment) => Technique::DealWithIncrement(n),
48        );
49
50        let mut part1_shuffle = Shuffle::identity();
51        let mut part2_shuffle = Shuffle::identity();
52        for item in technique.with_eol().parse_iterator(input) {
53            let technique = item?;
54            part1_shuffle.apply_technique(technique);
55            part2_shuffle.apply_technique(technique);
56        }
57
58        Ok(Self {
59            part1_shuffle,
60            part2_shuffle,
61        })
62    }
63
64    #[must_use]
65    pub fn part1(&self) -> u64 {
66        self.part1_shuffle.apply_to(PART1_CARD)
67    }
68
69    #[must_use]
70    pub fn part2(&self) -> u64 {
71        self.part2_shuffle
72            .inverse()
73            .repeat(PART2_REPEATS)
74            .apply_to(PART2_POSITION)
75    }
76}
77
78// position(x) = (multiplier * x + offset) (mod DECK_SIZE)
79impl<const DECK_SIZE: u64> Shuffle<DECK_SIZE> {
80    fn identity() -> Self {
81        Self {
82            multiplier: 1,
83            offset: 0,
84        }
85    }
86
87    fn apply_technique(&mut self, technique: Technique) {
88        match technique {
89            Technique::DealIntoNewStack => {
90                self.multiplier = DECK_SIZE - self.multiplier;
91                self.offset = DECK_SIZE - self.offset - 1;
92            }
93            Technique::Cut(amount) => {
94                self.offset =
95                    (self.offset as i64 - i64::from(amount)).rem_euclid(DECK_SIZE as i64) as u64;
96            }
97            Technique::DealWithIncrement(increment) => {
98                self.multiplier = Self::mod_mul(increment as u64, self.multiplier);
99                self.offset = Self::mod_mul(increment as u64, self.offset);
100            }
101        }
102    }
103
104    fn apply_to(self, value: u64) -> u64 {
105        (Self::mod_mul(value, self.multiplier) + self.offset) % DECK_SIZE
106    }
107
108    fn inverse(mut self) -> Self {
109        let inverse_multiplier = Self::mod_inverse(self.multiplier);
110        let inverse_offset = Self::mod_mul(inverse_multiplier, self.offset);
111        self.multiplier = inverse_multiplier;
112        self.offset = (DECK_SIZE - inverse_offset) % DECK_SIZE;
113        self
114    }
115
116    fn repeat(mut self, exponent: u64) -> Self {
117        let repeated_multiplier = mod_pow(
118            u128::from(self.multiplier),
119            u128::from(exponent),
120            u128::from(DECK_SIZE),
121        ) as u64;
122        self.offset = if self.multiplier == 1 {
123            Self::mod_mul(self.offset, exponent)
124        } else {
125            let numerator = (repeated_multiplier + DECK_SIZE - 1) % DECK_SIZE;
126            let geometric_sum = Self::mod_mul(numerator, Self::mod_inverse(self.multiplier - 1));
127            Self::mod_mul(self.offset, geometric_sum)
128        };
129        self.multiplier = repeated_multiplier;
130        self
131    }
132
133    fn mod_inverse(value: u64) -> u64 {
134        mod_inverse(value as i64, DECK_SIZE as i64).expect("part 2 requires an invertible shuffle")
135            as u64
136    }
137
138    fn mod_mul(a: u64, b: u64) -> u64 {
139        ((u128::from(a) * u128::from(b)) % u128::from(DECK_SIZE)) as u64
140    }
141}
142
143examples!(Day22 -> (u64, u64) []);
year2019/day22.rs

year2019/
day22.rs
