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<()> {