From 1b24db05ed43796847389ea94b973c36b6b262d2 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 21 Dec 2021 10:19:29 +0200 Subject: Day 21 part 2 --- Cargo.lock | 236 +++++++++++++++++++++++++++++++++++++++++++++++++++++- Cargo.toml | 1 + src/bin/day_21.rs | 65 +++++++++++---- 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,11 +6,100 @@ 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" @@ -22,6 +111,119 @@ dependencies = [ "syn", ] +[[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" @@ -45,6 +247,24 @@ dependencies = [ "version_check", ] +[[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" @@ -56,13 +276,25 @@ 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" 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 "] 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> { 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(( -- cgit v1.2.3