1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

/// From https://docs.rs/mod_exp/1.0.1/mod_exp, specialised to i128.
pub fn mod_exp(base: i128, exponent: i128, modulus: i128) -> i128 {
    const ONE: i128 = 1;
    const TWO: i128 = 2;
    const ZERO: i128 = 0;
    const MAX: i128 = i128::MAX;

    assert!((modulus - ONE) < (MAX / (modulus - ONE)));

    let mut result = ONE;
    let mut base = base % modulus;
    let mut exponent = exponent;

    loop {
        if exponent <= ZERO {
            break;
        }

        if exponent % TWO == ONE {
            result = (result * base) % modulus;
        }

        exponent >>= ONE;
        base = (base * base) % modulus;
    }

    result
}

pub fn part1(input_string: &str) -> Result<usize, String> {
    let mut deck = Vec::new();
    for i in 0..10_007 {
        deck.push(i);
    }

    for (line_index, line) in input_string.lines().enumerate() {
        let error_message = || format!("Invalid line: {}", line_index + 1);
        let error_message_arg = |_| error_message();

        if line.starts_with("deal into") {
            deck = deck.iter().rev().copied().collect();
        } else if line.starts_with("cut") {
            let how_many = line.split_whitespace().nth(1).ok_or_else(error_message)?;
            let how_many = how_many.parse::<i32>().map_err(error_message_arg)?;
            let how_many = if how_many > 0 {
                how_many
            } else {
                10_007 - how_many.abs()
            } as usize;
            deck = [&deck[how_many..], &deck[..how_many]].concat();
        } else if line.starts_with("deal with") {
            let increment = line
                .split_whitespace()
                .nth(3)
                .ok_or_else(error_message)
                .and_then(|value_str| value_str.parse::<usize>().map_err(error_message_arg))?;
            let old_deck = deck.clone();
            let mut current_index = 0;
            for &card_at_front in old_deck.iter() {
                deck[current_index] = card_at_front;
                current_index = (current_index + increment) % deck.len();
            }
        } else {
            return Err(format!("Invalid line: {}", line_index + 1));
        }
    }

    let desired_card = 2019;
    deck.iter()
        .position(|&card| card == 2019)
        .ok_or(format!("No card {} found", desired_card))
}

/// Explanation:
/// https://www.reddit.com/r/adventofcode/comments/ee0rqi/2019_day_22_solutions/fbnkaju?utm_source=share&utm_medium=web2x
pub fn part2(input_string: &str) -> Result<i128, String> {
    fn inv(n: i128) -> i128 {
        mod_exp(n, MOD - 2, MOD)
    }

    const SHUFFLES: i128 = 101_741_582_076_661;

    const NUM_CARDS: i128 = 119_315_717_514_047;
    const MOD: i128 = NUM_CARDS;

    let mut offset_diff: i128 = 0;
    let mut increment_mul: i128 = 1;

    for (line_index, line) in input_string.lines().enumerate() {
        let error_message = || format!("Invalid line: {}", line_index + 1);
        let error_message_arg = |_| error_message();

        if line.starts_with("deal into") {
            increment_mul *= -1;
            offset_diff += increment_mul;
        } else if line.starts_with("cut") {
            let n = line
                .split_whitespace()
                .nth(1)
                .ok_or_else(error_message)
                .and_then(|value_str| value_str.parse::<i128>().map_err(error_message_arg))?;
            offset_diff += increment_mul * n;
        } else if line.starts_with("deal with") {
            let n = line
                .split_whitespace()
                .nth(3)
                .ok_or_else(error_message)
                .and_then(|value_str| value_str.parse::<i128>().map_err(error_message_arg))?;
            increment_mul *= inv(n);
        // The offset (first card) does not change.
        // To get the increment, we need to calculate the second card.
        // "The 0th card in our old list goes to the 0th card in our new list, 1st card in
        // old goes to the nth card in new list (mod MOD), 2nd card in old goes to the 2*nth
        // card in new list, and so on. So, the ith card in our old list goes to the i*nth
        // card in the new list. When is i*n = 1?"
        } else {
            return Err(format!("Invalid line: {}", line_index + 1));
        }

        increment_mul = increment_mul.rem_euclid(MOD);
        offset_diff = offset_diff.rem_euclid(MOD);
    }

    let increment = mod_exp(increment_mul, SHUFFLES, MOD);
    let offset = (offset_diff * (1_i128 - increment)).rem_euclid(MOD) * inv(1 - increment_mul);

    let result = (offset + increment * 2020).rem_euclid(MOD);
    Ok(result)
}

#[test]
pub fn tests_part1() {
    assert_eq!(part1(include_str!("day22_input.txt")), Ok(6526));
}

#[test]
fn tests_part2() {
    assert_eq!(
        part2(include_str!("day22_input.txt")),
        Ok(79_855_812_422_607)
    );
}