aoc/year2020/
day25.rs

1//! # Combo Breaker
2//!
3//! The card loop size is found using the
4//! [Baby-step giant-step algorithm](https://en.wikipedia.org/wiki/Baby-step_giant-step).
5//! This takes only √20201227 = 4495 steps, compared to potentially up to 20201227 steps
6//! for the brute force approach.
7//!
8//! The common encryption key is then calculated efficiently by
9//! [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation) using
10//! [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring).
11use crate::util::hash::*;
12use crate::util::iter::*;
13use crate::util::math::*;
14use crate::util::parse::*;
15
16pub fn parse(input: &str) -> [u64; 2] {
17    input.iter_unsigned().chunk::<2>().next().unwrap()
18}
19
20pub fn part1(input: &[u64; 2]) -> u64 {
21    let [card_public_key, door_public_key] = *input;
22    let card_loop_count = discrete_logarithm(card_public_key);
23    door_public_key.mod_pow(card_loop_count, 20201227)
24}
25
26pub fn part2(_input: &[u64; 2]) -> &'static str {
27    "n/a"
28}
29
30/// Baby-step giant-step algorithm to compute discrete logarithm.
31/// Constants are hardcoded to this specific problem.
32/// * 4495 is the ceiling of √20201227
33/// * 680915 is 7⁻⁴⁴⁹⁵, or the
34///   [multiplicative modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)
35///   of 7 to modular exponent 4495.
36fn discrete_logarithm(public_key: u64) -> u64 {
37    let m = 4495;
38    let mut map = FastMap::with_capacity(m as usize);
39
40    let mut a = 1;
41    for j in 0..m {
42        map.insert(a, j);
43        a = (a * 7) % 20201227;
44    }
45
46    let mut b = public_key;
47    for i in 0..m {
48        if let Some(j) = map.get(&b) {
49            return i * m + j;
50        }
51        b = (b * 680915) % 20201227;
52    }
53
54    unreachable!()
55}