diff options
Diffstat (limited to '2020/src/bin/2020day22.rs')
-rw-r--r-- | 2020/src/bin/2020day22.rs | 64 |
1 files changed, 60 insertions, 4 deletions
diff --git a/2020/src/bin/2020day22.rs b/2020/src/bin/2020day22.rs index ca270dc..9d055d7 100644 --- a/2020/src/bin/2020day22.rs +++ b/2020/src/bin/2020day22.rs @@ -1,6 +1,6 @@ use aoc2020::*; -#[derive(Debug, Clone)] +#[derive(Debug, Clone, Hash, PartialEq, Eq)] struct Decks { p1: VecDeque<u8>, p2: VecDeque<u8>, @@ -56,8 +56,62 @@ fn part1(input: &Decks) -> 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 { - unimplemented!() + // 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)] @@ -81,12 +135,14 @@ Player 2: #[test] fn testcase1() { let decks = Decks::from_str(TEST_INPUT).unwrap(); - println!("{:?}", decks); assert_eq!(part1(&decks), 306); } #[test] - fn testcase2() {} + fn testcase2() { + let decks = Decks::from_str(TEST_INPUT).unwrap(); + assert_eq!(part2(&decks), 291); + } } fn main() -> Result<()> { |