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

use mod_exp::mod_exp;

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

    for (index, line) in input_string.lines().enumerate() {
        let line_number = index + 1;
        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(|| {
                format!(
                    "Incorrect input at line {}: No argument to cut",
                    line_number
                )
            })?;
            let how_many = how_many.parse::<i32>().map_err(|parse_error| {
                format!(
                    "Incorrect input at line {}: Cannot parse number of cuts - {}",
                    line_number, parse_error
                )
            })?;
            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)
                .unwrap()
                .parse::<usize>()
                .unwrap();
            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));
        }
    }

    Ok(deck.iter().position(|&card| card == 2019).unwrap())
}

/// 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 in input_string.lines() {
        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)
                .unwrap()
                .parse::<i128>()
                .unwrap();
            offset_diff += increment_mul * n;
        } else if line.starts_with("deal with") {
            let n = line
                .split_whitespace()
                .nth(3)
                .unwrap()
                .parse::<i128>()
                .unwrap();
            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));
        }

        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)
    );
}