summaryrefslogtreecommitdiff
path: root/2020/src/bin/2020day22.rs
diff options
context:
space:
mode:
Diffstat (limited to '2020/src/bin/2020day22.rs')
-rw-r--r--2020/src/bin/2020day22.rs64
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<()> {