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

use crate::input::Input;
use std::collections::{HashSet, VecDeque};

enum Winner {
    Player1,
    Player2,
}

fn parse_player_cards(input: &str) -> Option<VecDeque<u8>> {
    input
        .lines()
        .skip(1)
        .map(str::parse)
        .collect::<Result<_, _>>()
        .ok()
}

fn play_recursive(player_1_cards: &mut VecDeque<u8>, player_2_cards: &mut VecDeque<u8>) -> Winner {
    #![allow(clippy::unwrap_used)]
    let mut seen_1 = HashSet::new();
    let mut seen_2 = HashSet::new();

    loop {
        if !(seen_1.insert(player_1_cards.clone()) && seen_2.insert(player_2_cards.clone())) {
            return Winner::Player1;
        } else if player_1_cards.is_empty() {
            return Winner::Player2;
        } else if player_2_cards.is_empty() {
            return Winner::Player1;
        }

        let c1 = player_1_cards.pop_front().unwrap();
        let c2 = player_2_cards.pop_front().unwrap();

        let winner = if player_1_cards.len() >= c1 as usize && player_2_cards.len() >= c2 as usize {
            let mut p1_subgame_cards = player_1_cards
                .iter()
                .take(c1 as usize)
                .copied()
                .collect::<VecDeque<u8>>();
            let mut p2_subgame_cards = player_2_cards
                .iter()
                .take(c2 as usize)
                .copied()
                .collect::<VecDeque<u8>>();
            play_recursive(&mut p1_subgame_cards, &mut p2_subgame_cards)
        } else if c1 > c2 {
            Winner::Player1
        } else {
            Winner::Player2
        };

        match winner {
            Winner::Player1 => {
                player_1_cards.push_back(c1);
                player_1_cards.push_back(c2);
            }
            Winner::Player2 => {
                player_2_cards.push_back(c2);
                player_2_cards.push_back(c1);
            }
        }
    }
}

pub fn solve(input: &mut Input) -> Result<u64, String> {
    #![allow(clippy::unwrap_used)]
    let on_error = || "Invalid input".to_string();

    let mut parts = input.text.splitn(2, "\n\n");
    let mut player_1_cards =
        parse_player_cards(parts.next().ok_or_else(on_error)?).ok_or_else(on_error)?;
    let mut player_2_cards =
        parse_player_cards(parts.next().ok_or_else(on_error)?).ok_or_else(on_error)?;

    let winner = if input.is_part_one() {
        while !player_1_cards.is_empty() && !player_2_cards.is_empty() {
            let c1 = player_1_cards.pop_front().unwrap();
            let c2 = player_2_cards.pop_front().unwrap();
            if c1 > c2 {
                player_1_cards.push_back(c1);
                player_1_cards.push_back(c2);
            } else {
                player_2_cards.push_back(c2);
                player_2_cards.push_back(c1);
            }
        }
        if player_1_cards.is_empty() {
            Winner::Player2
        } else {
            Winner::Player1
        }
    } else {
        play_recursive(&mut player_1_cards, &mut player_2_cards)
    };

    let winner_cards = match winner {
        Winner::Player1 => player_1_cards,
        Winner::Player2 => player_2_cards,
    };

    Ok(winner_cards
        .iter()
        .rev()
        .enumerate()
        .map(|(idx, &card)| (idx + 1) as u64 * u64::from(card))
        .sum())
}

#[test]
pub fn tests() {
    use crate::{test_part_one, test_part_two};

    let example = "Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10
";
    test_part_one!(example => 306);
    test_part_two!(example => 291);

    let real_input = include_str!("day22_input.txt");
    test_part_one!(real_input => 33098);
    test_part_two!(real_input => 35055);
}