summaryrefslogtreecommitdiff
path: root/2020/src/bin/2020day22.rs
blob: 9d055d7ca0b66400cf389812ad8c0111a96c7f96 (plain)
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
143
144
145
146
147
148
149
150
151
152
153
154
use aoc2020::*;

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
struct Decks {
    p1: VecDeque<u8>,
    p2: VecDeque<u8>,
}

impl FromStr for Decks {
    type Err = GenError;

    fn from_str(value: &str) -> Result<Self> {
        // Rough format:
        // Player1: nums \n\n Player2: nums
        let value = value.trim();
        let gap = value.find("\n\n").ok_or("no gap?")?;
        let (p1, p2) = value.split_at(gap);
        let p1 = p1.trim().lines().skip(1);
        let p2 = p2.trim().lines().skip(1);

        let p1: StdResult<_, _> = p1.map(|s| s.parse()).collect();
        let p2: StdResult<_, _> = p2.map(|s| s.parse()).collect();

        let p1 = p1?;
        let p2 = p2?;

        Ok(Self { p1, p2 })
    }
}

fn part1(input: &Decks) -> usize {
    let mut game = input.clone();
    while !(game.p1.is_empty() || game.p2.is_empty()) {
        let p1card = game.p1.pop_front().unwrap();
        let p2card = game.p2.pop_front().unwrap();
        if p1card > p2card {
            game.p1.push_back(p1card);
            game.p1.push_back(p2card);
        } else {
            game.p2.push_back(p2card);
            game.p2.push_back(p1card);
        }
    }
    // Game over, give winning player their score
    let winner = if game.p1.is_empty() {
        &game.p2
    } else {
        &game.p1
    };
    winner
        .iter()
        .rev()
        .copied()
        .enumerate()
        .map(|(i, c)| (i + 1) * (c as usize))
        .sum()
}

fn recursive_game(mut game: Decks) -> (u8, Decks) {
    // During a recursive game, we can't repeat arrangements
    let mut seen = HashSet::new();
    while !(game.p1.is_empty() || game.p2.is_empty()) {
        if seen.contains(&game) {
            // We've seen this arrangement before, p1 wins by default
            return (1, game);
        }
        seen.insert(game.clone());
        // Okay, unique arrangement, play a round...
        let p1card = game.p1.pop_front().unwrap() as usize;
        let p2card = game.p2.pop_front().unwrap() as usize;
        let winner = if (game.p1.len() >= p1card) && (game.p2.len() >= p2card) {
            // We can recurse, so let's do that
            let mut subgame = game.clone();
            while subgame.p1.len() > p1card {
                subgame.p1.pop_back();
            }
            while subgame.p2.len() > p2card {
                subgame.p2.pop_back();
            }
            recursive_game(subgame).0
        } else {
            // We can't recurse, normal round
            if p1card > p2card {
                1
            } else {
                2
            }
        };
        let p1card = p1card as u8;
        let p2card = p2card as u8;
        if winner == 1 {
            game.p1.push_back(p1card);
            game.p1.push_back(p2card);
        } else {
            game.p2.push_back(p2card);
            game.p2.push_back(p1card);
        }
    }
    // Since we reached here, the winner is simply whoever has cards.
    let winner = if game.p1.is_empty() { 2 } else { 1 };
    (winner, game)
}

fn part2(input: &Decks) -> usize {
    // Recursive gaming...
    let (winner, game) = recursive_game(input.clone());
    let winner = if winner == 1 { &game.p1 } else { &game.p2 };
    winner
        .iter()
        .rev()
        .copied()
        .enumerate()
        .map(|(i, c)| (i + 1) * (c as usize))
        .sum()
}

#[cfg(test)]
mod test {
    use super::*;

    const TEST_INPUT: &str = r#"Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10"#;

    #[test]
    fn testcase1() {
        let decks = Decks::from_str(TEST_INPUT).unwrap();
        assert_eq!(part1(&decks), 306);
    }

    #[test]
    fn testcase2() {
        let decks = Decks::from_str(TEST_INPUT).unwrap();
        assert_eq!(part2(&decks), 291);
    }
}

fn main() -> Result<()> {
    let input: String = read_input(22)?;
    let input = Decks::from_str(&input)?;
    println!("Part 1: {}", part1(&input));
    println!("Part 2: {}", part2(&input));
    Ok(())
}