Day 21 part 2

3 files changed, 285 insertions, 17 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 9bc8573..720bb14 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -6,12 +6,101 @@ version = 3
 name = "aoc2021"
 version = "0.1.0"
 dependencies = [
+ "cached",
  "derive_more",
  "nom",
  "thiserror",
 ]
 
 [[package]]
+name = "async-mutex"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "479db852db25d9dbf6204e6cb6253698f175c15726470f78af0d918e99d6156e"
+dependencies = [
+ "event-listener",
+]
+
+[[package]]
+name = "async-trait"
+version = "0.1.52"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "061a7acccaa286c011ddc30970520b98fa40e00c9d644633fb26b5fc63a265e3"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "cached"
+version = "0.25.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "14d3b04f85a6ef9fe543b2564ec8630bdf3363aa9bf664a1bfc85033e7350aaf"
+dependencies = [
+ "async-mutex",
+ "async-trait",
+ "cached_proc_macro",
+ "cached_proc_macro_types",
+ "futures",
+ "hashbrown",
+ "once_cell",
+]
+
+[[package]]
+name = "cached_proc_macro"
+version = "0.6.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4230b8d9f5db741004bfaef172c5b2dbf0eb94f105204cc6147a220080daaa85"
+dependencies = [
+ "cached_proc_macro_types",
+ "darling",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "cached_proc_macro_types"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3a4f925191b4367301851c6d99b09890311d74b0d43f274c0b34c86d308a3663"
+
+[[package]]
+name = "darling"
+version = "0.13.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d0d720b8683f8dd83c65155f0530560cba68cd2bf395f6513a483caee57ff7f4"
+dependencies = [
+ "darling_core",
+ "darling_macro",
+]
+
+[[package]]
+name = "darling_core"
+version = "0.13.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7a340f241d2ceed1deb47ae36c4144b2707ec7dd0b649f894cb39bb595986324"
+dependencies = [
+ "fnv",
+ "ident_case",
+ "proc-macro2",
+ "quote",
+ "strsim",
+ "syn",
+]
+
+[[package]]
+name = "darling_macro"
+version = "0.13.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "72c41b3b7352feb3211a0d743dc5700a4e3b60f51bd2b368892d1e0f9a95f44b"
+dependencies = [
+ "darling_core",
+ "quote",
+ "syn",
+]
+
+[[package]]
 name = "derive_more"
 version = "0.99.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -23,6 +112,119 @@ dependencies = [
 ]
 
 [[package]]
+name = "event-listener"
+version = "2.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f7531096570974c3a9dcf9e4b8e1cede1ec26cf5046219fb3b9d897503b9be59"
+
+[[package]]
+name = "fnv"
+version = "1.0.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
+
+[[package]]
+name = "futures"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "28560757fe2bb34e79f907794bb6b22ae8b0e5c669b638a1132f2592b19035b4"
+dependencies = [
+ "futures-channel",
+ "futures-core",
+ "futures-executor",
+ "futures-io",
+ "futures-sink",
+ "futures-task",
+ "futures-util",
+]
+
+[[package]]
+name = "futures-channel"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ba3dda0b6588335f360afc675d0564c17a77a2bda81ca178a4b6081bd86c7f0b"
+dependencies = [
+ "futures-core",
+ "futures-sink",
+]
+
+[[package]]
+name = "futures-core"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d0c8ff0461b82559810cdccfde3215c3f373807f5e5232b71479bff7bb2583d7"
+
+[[package]]
+name = "futures-executor"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "29d6d2ff5bb10fb95c85b8ce46538a2e5f5e7fdc755623a7d4529ab8a4ed9d2a"
+dependencies = [
+ "futures-core",
+ "futures-task",
+ "futures-util",
+]
+
+[[package]]
+name = "futures-io"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b1f9d34af5a1aac6fb380f735fe510746c38067c5bf16c7fd250280503c971b2"
+
+[[package]]
+name = "futures-macro"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6dbd947adfffb0efc70599b3ddcf7b5597bb5fa9e245eb99f62b3a5f7bb8bd3c"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "futures-sink"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e3055baccb68d74ff6480350f8d6eb8fcfa3aa11bdc1a1ae3afdd0514617d508"
+
+[[package]]
+name = "futures-task"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6ee7c6485c30167ce4dfb83ac568a849fe53274c831081476ee13e0dce1aad72"
+
+[[package]]
+name = "futures-util"
+version = "0.3.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d9b5cf40b47a271f77a8b1bec03ca09044d99d2372c0de244e66430761127164"
+dependencies = [
+ "futures-channel",
+ "futures-core",
+ "futures-io",
+ "futures-macro",
+ "futures-sink",
+ "futures-task",
+ "memchr",
+ "pin-project-lite",
+ "pin-utils",
+ "slab",
+]
+
+[[package]]
+name = "hashbrown"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ab5ef0d4909ef3724cc8cce6ccc8572c5c817592e9285f5464f8e86f8bd3726e"
+
+[[package]]
+name = "ident_case"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b9e0384b61958566e926dc50660321d12159025e767c18e043daf26b70104c39"
+
+[[package]]
 name = "memchr"
 version = "2.4.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -46,6 +248,24 @@ dependencies = [
 ]
 
 [[package]]
+name = "once_cell"
+version = "1.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "da32515d9f6e6e489d7bc9d84c71b060db7247dc035bbe44eac88cf87486d8d5"
+
+[[package]]
+name = "pin-project-lite"
+version = "0.2.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8d31d11c69a6b52a174b42bdc0c30e5e11670f90788b2c471c31c1d17d449443"
+
+[[package]]
+name = "pin-utils"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8b870d8c151b6f2fb93e84a13146138f05d02ed11c7e7c54f8826aaaf7c9f184"
+
+[[package]]
 name = "proc-macro2"
 version = "1.0.32"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -56,14 +276,26 @@ dependencies = [
 
 [[package]]
 name = "quote"
-version = "1.0.2"
+version = "1.0.10"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe"
+checksum = "38bc8cc6a5f2e3655e0899c1b848643b2562f853f114bfec7be120678e3ace05"
 dependencies = [
  "proc-macro2",
 ]
 
 [[package]]
+name = "slab"
+version = "0.4.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9def91fd1e018fe007022791f865d0ccc9b3a0d5001e01aabb8b40e46000afb5"
+
+[[package]]
+name = "strsim"
+version = "0.10.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "73473c0e59e6d5812c5dfe2a064a6444949f089e20eec9a2e5506596494e4623"
+
+[[package]]
 name = "syn"
 version = "1.0.82"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index ce20b0e..9e2399b 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,6 +5,7 @@ authors = ["Justin Wernick <justin@worthe-it.co.za>"]
 edition = "2021"
 
 [dependencies]
+cached = "0.25.0"
 derive_more = "0.99.2"
 nom = "7.0.0"
 thiserror = "1.0.29"
diff --git a/src/bin/day_21.rs b/src/bin/day_21.rs
index e937bcb..245a0e6 100644
--- a/src/bin/day_21.rs
+++ b/src/bin/day_21.rs
@@ -1,3 +1,4 @@
+use cached::proc_macro::cached;
 use nom::{
     bytes::complete::tag,
     character::complete::u32 as nom_u32,
@@ -9,27 +10,61 @@ use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_21.txt")?;
-    let mut player_positions = parse_starting_positions(&input).unwrap().1;
-    let mut player_scores = [0, 0];
-    let mut dice = (1..=100).cycle().enumerate().peekable();
-    let mut player_turn = 0;
-    while player_scores[0] < 1000 && player_scores[1] < 1000 {
-        let dice_roll: u32 = dice.by_ref().take(3).map(|(_, roll)| roll).sum();
-        player_positions[player_turn] = (player_positions[player_turn] + dice_roll) % 10;
-        if player_positions[player_turn] == 0 {
-            player_positions[player_turn] = 10;
+    let player_positions = parse_starting_positions(&input).unwrap().1;
+    {
+        let mut player_positions = player_positions.clone();
+        let mut player_scores = [0, 0];
+        let mut dice = (1..=100).cycle().enumerate().peekable();
+        let mut player_turn = 0;
+        while player_scores[0] < 1000 && player_scores[1] < 1000 {
+            let dice_roll: u32 = dice.by_ref().take(3).map(|(_, roll)| roll).sum();
+            player_positions[player_turn] = (player_positions[player_turn] + dice_roll) % 10;
+            if player_positions[player_turn] == 0 {
+                player_positions[player_turn] = 10;
+            }
+            player_scores[player_turn] += player_positions[player_turn];
+            player_turn = (player_turn + 1) % 2;
         }
-        player_scores[player_turn] += player_positions[player_turn];
-        player_turn = (player_turn + 1) % 2;
+        let losing_score = player_scores.iter().min().cloned().unwrap_or(0);
+        let dice_roll_count = dice.peek().unwrap().0;
+        dbg!((losing_score, dice_roll_count));
+        dbg!(losing_score * dice_roll_count as u32);
     }
-    let losing_score = player_scores.iter().min().cloned().unwrap_or(0);
-    let dice_roll_count = dice.peek().unwrap().0;
-    dbg!((losing_score, dice_roll_count));
-    dbg!(losing_score * dice_roll_count as u32);
 
+    let win_counts = player_win_counts(player_positions, [0, 0]);
+    dbg!(win_counts);
+    dbg!(win_counts.into_iter().max().unwrap_or(0));
     Ok(())
 }
 
+#[cached]
+fn player_win_counts(player_positions: [u32; 2], player_scores: [u32; 2]) -> [u64; 2] {
+    let mut win_counts = [0; 2];
+    for dice_roll_1 in 1..=3 {
+        for dice_roll_2 in 1..=3 {
+            for dice_roll_3 in 1..=3 {
+                let dice_roll = dice_roll_1 + dice_roll_2 + dice_roll_3;
+                let mut new_position = (player_positions[0] + dice_roll) % 10;
+                if new_position == 0 {
+                    new_position = 10;
+                }
+                let new_score = player_scores[0] + new_position;
+                if new_score >= 21 {
+                    win_counts[0] += 1;
+                } else {
+                    let recursive_wins = player_win_counts(
+                        [player_positions[1], new_position],
+                        [player_scores[1], new_score],
+                    );
+                    win_counts[0] += recursive_wins[1];
+                    win_counts[1] += recursive_wins[0];
+                }
+            }
+        }
+    }
+    win_counts
+}
+
 fn parse_starting_positions(input: &str) -> IResult<&str, [u32; 2]> {
     map(
         tuple((