aoc/year2019/
day22.rs

1//! # Slam Shuffle
2//!
3//! This problem requires `i128` integers to prevent overflow!
4//!
5//! ## Modular Arithmetic
6//!
7//! To solve we'll need some knowledge of [modular arithemetic](https://en.wikipedia.org/wiki/Modular_arithmetic).
8//!
9//! Some basic modular identities:
10//! * (a + b) mod m = (a mod m) + (b mod m)
11//! * (a * b) mod m = (a mod m) * (b mod m)
12//! * The [modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)
13//!   is used instead of division.
14//!
15//! ## Linear Congruences
16//!
17//! The next required insight is that each of the shuffle operation is a *linear congruence*
18//! of the form:
19//!
20//! `Xₙ₊₁ = (aXₙ + c) mod m`
21//!
22//! For example "deal into new stack" which reverses the deck can be represented as:
23//!
24//! `Xₙ₊₁ = ((m - 1) * Xₙ + (m - 1)) mod m`
25//!
26//! With a deck of 3 cards this is:
27//! * 0 => (2 * 0 + 2) mod 3 = 2
28//! * 1 => (2 * 1 + 2) mod 3 = 1
29//! * 2 => (2 * 2 + 2) mod 3 = 0
30//!
31//! "cut N cards" is:
32//!
33//! `Xₙ₊₁ = 1 * Xₙ + (m - N)) mod m`
34//!
35//! For example "cut 3" with a deck of 5 cards is:
36//! * 0 => (1 * 0 + (5 - 3)) mod 5 = 2
37//! * 1 => (1 * 1 + (5 - 3)) mod 5 = 3
38//! * 2 => (1 * 2 + (5 - 3)) mod 5 = 4
39//! * 3 => (1 * 3 + (5 - 3)) mod 5 = 0
40//! * 4 => (1 * 3 + (5 - 3)) mod 5 = 1
41//!
42//! If N is negative the cut works from the end. If N is greater than m then take N mod m.
43//!
44//! "deal with increment N" is:
45//!
46//! `Xₙ₊₁ = N * Xₙ + 0) mod m`
47//!
48//! For example "deal with increment 3" with a deck of 5 cards is:
49//! * 0 => (3 * 0 + 0) mod 5 = 0
50//! * 1 => (3 * 1 + 0) mod 5 = 3
51//! * 2 => (3 * 2 + 0) mod 5 = 1
52//! * 3 => (3 * 3 + 0) mod 5 = 4
53//! * 4 => (3 * 4 + 0) mod 5 = 2
54//!
55//! ## Composition
56//!
57//! Congruences can be composed:
58//!
59//! `Xₙ₊₁ = a₂ * (a₁Xₙ + c₁) + c₂) mod m = (a₁a₂Xₙ + a₂c₁ + c₂) mod m`
60//!
61//! so we could combine the previous "cut 3" and deal with increment 3" as:
62//!
63//! `Xₙ₊₁ = 3 * (1Xₙ + 2) + 0) mod m = (3Xₙ + 6) mod m`.
64//!
65//! This allows us to take all the input techniques and then combine them into a *single*
66//! technique with the same effect, providing an efficient solution for part one.
67//!
68//! ## Inverse
69//!
70//! Part two is trickier. To find the card that ends up at index 2020 we need to find an inverse
71//! congruence such that when we apply a composition to the shuffle we get the identity congruence:
72//!
73//! `(a₁a₂Xₙ + a₂c₁ + c₂) mod m = (Xₙ + 0) mod m`
74//!
75//! This implies that `a₁a₂ mod m = 1` which is the definition of the modular inverse`a₂ = a₁⁻¹`.
76//!
77//! The constant term `(a₂c₁ + c₂) mod m = 0` implies `c₂ = m - a₂c₁`.
78//!
79//! ## Exponentiation
80//!
81//! To find of inverse of 101741582076661 shuffles we need to raise to our inverse to the same
82//! power. Let's look at the first few powers
83//! * ax + c
84//! * a * (ax + c) + c = a²x + ac + c
85//! * a * (a²x + ac + c) = a³x + a²c + ac + c
86//! * a * (a³x + a²c + ac + c) = a⁴x + a³c + a²c + ac + c
87//!
88//! We notice that the constant terms are the sum of a [geometric series](https://en.wikipedia.org/wiki/Geometric_series)
89//! which is given by the closed-form formula:
90//!
91//! `cₙ = c(1 - aⁿ)/(1 - a)`
92//!
93//! Multiplying both sides by -1 and remembering that modular division is the multiplicative
94//! inverse yields:
95//!
96//! `cₙ = c(aⁿ - 1)((a - 1)⁻¹) mod m`
97//!
98//! We can then raise a congruence to any power, using only one modular exponentiation and
99//! one modular inverse, allowing us to solve part two efficiently.
100//!
101//! `Xₙ₊₁ = (aⁿXₙ + c(aⁿ - 1)((a - 1)⁻¹)) mod m`
102use crate::util::math::*;
103use crate::util::parse::*;
104
105struct Technique {
106    a: i128,
107    c: i128,
108    m: i128,
109}
110
111impl Technique {
112    fn compose(&self, other: &Technique) -> Technique {
113        let m = self.m;
114        let a = (self.a * other.a) % m;
115        let c = (self.c * other.a + other.c) % m;
116        Technique { a, c, m }
117    }
118
119    fn inverse(&self) -> Technique {
120        let m = self.m;
121        let a = self.a.mod_inv(m).unwrap();
122        let c = m - (a * self.c) % m;
123        Technique { a, c, m }
124    }
125
126    fn power(&self, e: i128) -> Technique {
127        let m = self.m;
128        let a = self.a.mod_pow(e, m);
129        let c = (((a - 1) * (self.a - 1).mod_inv(m).unwrap() % m) * self.c) % m;
130        Technique { a, c, m }
131    }
132
133    fn shuffle(&self, index: i128) -> i128 {
134        (self.a * index + self.c) % self.m
135    }
136}
137
138pub fn parse(input: &str) -> &str {
139    input
140}
141
142pub fn part1(input: &str) -> i128 {
143    deck(input, 10007).shuffle(2019)
144}
145
146pub fn part2(input: &str) -> i128 {
147    deck(input, 119315717514047).inverse().power(101741582076661).shuffle(2020)
148}
149
150fn deck(input: &str, m: i128) -> Technique {
151    input
152        .lines()
153        .map(|line| {
154            let tokens: Vec<_> = line.split_ascii_whitespace().collect();
155            match tokens[..] {
156                [_, "into", _, _] => Technique { a: m - 1, c: m - 1, m },
157                [_, "with", _, n] => {
158                    let n: i128 = n.signed();
159                    let a = (m + n % m) % m;
160                    Technique { a, c: 0, m }
161                }
162                ["cut", n] => {
163                    let n: i128 = n.signed();
164                    let c = (m - n % m) % m;
165                    Technique { a: 1, c, m }
166                }
167                _ => unreachable!(),
168            }
169        })
170        .reduce(|a, b| a.compose(&b))
171        .unwrap()
172}
aoc/year2019/day22.rs

aoc/year2019/
day22.rs
