From 4cf1061e00993118847c24177ea2cc1e5455211d Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Mon, 20 Dec 2021 22:59:31 -0800 Subject: 21 --- 20/tests/main.rs | 2 +- 21/Cargo.toml | 11 ++++ 21/input | 2 + 21/small | 136 +++++++++++++++++++++++++++++++++++++++ 21/src/main.rs | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 21/tests/main.rs | 17 +++++ Cargo.lock | 8 +++ Cargo.toml | 1 + 8 files changed, 368 insertions(+), 1 deletion(-) create mode 100644 21/Cargo.toml create mode 100644 21/input create mode 100644 21/small create mode 100644 21/src/main.rs create mode 100644 21/tests/main.rs diff --git a/20/tests/main.rs b/20/tests/main.rs index 826e079..f681209 100644 --- a/20/tests/main.rs +++ b/20/tests/main.rs @@ -7,7 +7,7 @@ use std::process::Command; fn personal_input() -> Result<(), Box> { let mut command = Command::cargo_bin("advent_20")?; - command.arg("small"); + command.arg("input"); command.assert().success().stdout( "5573\n\ 20097\n"); diff --git a/21/Cargo.toml b/21/Cargo.toml new file mode 100644 index 0000000..7d88c6f --- /dev/null +++ b/21/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_21" +version = "0.1.0" +authors = ["Irene Knapp "] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/21/input b/21/input new file mode 100644 index 0000000..5ff8228 --- /dev/null +++ b/21/input @@ -0,0 +1,2 @@ +Player 1 starting position: 4 +Player 2 starting position: 6 diff --git a/21/small b/21/small new file mode 100644 index 0000000..4e496e9 --- /dev/null +++ b/21/small @@ -0,0 +1,136 @@ +--- scanner 0 --- +404,-588,-901 +528,-643,409 +-838,591,734 +390,-675,-793 +-537,-823,-458 +-485,-357,347 +-345,-311,381 +-661,-816,-575 +-876,649,763 +-618,-824,-621 +553,345,-567 +474,580,667 +-447,-329,318 +-584,868,-557 +544,-627,-890 +564,392,-477 +455,729,728 +-892,524,684 +-689,845,-530 +423,-701,434 +7,-33,-71 +630,319,-379 +443,580,662 +-789,900,-551 +459,-707,401 + +--- scanner 1 --- +686,422,578 +605,423,415 +515,917,-361 +-336,658,858 +95,138,22 +-476,619,847 +-340,-569,-846 +567,-361,727 +-460,603,-452 +669,-402,600 +729,430,532 +-500,-761,534 +-322,571,750 +-466,-666,-811 +-429,-592,574 +-355,545,-477 +703,-491,-529 +-328,-685,520 +413,935,-424 +-391,539,-444 +586,-435,557 +-364,-763,-893 +807,-499,-711 +755,-354,-619 +553,889,-390 + +--- scanner 2 --- +649,640,665 +682,-795,504 +-784,533,-524 +-644,584,-595 +-588,-843,648 +-30,6,44 +-674,560,763 +500,723,-460 +609,671,-379 +-555,-800,653 +-675,-892,-343 +697,-426,-610 +578,704,681 +493,664,-388 +-671,-858,530 +-667,343,800 +571,-461,-707 +-138,-166,112 +-889,563,-600 +646,-828,498 +640,759,510 +-630,509,768 +-681,-892,-333 +673,-379,-804 +-742,-814,-386 +577,-820,562 + +--- scanner 3 --- +-589,542,597 +605,-692,669 +-500,565,-823 +-660,373,557 +-458,-679,-417 +-488,449,543 +-626,468,-788 +338,-750,-386 +528,-832,-391 +562,-778,733 +-938,-730,414 +543,643,-506 +-524,371,-870 +407,773,750 +-104,29,83 +378,-903,-323 +-778,-728,485 +426,699,580 +-438,-605,-362 +-469,-447,-387 +509,732,623 +647,635,-688 +-868,-804,481 +614,-800,639 +595,780,-596 + +--- scanner 4 --- +727,592,562 +-293,-554,779 +441,611,-461 +-714,465,-776 +-743,427,-804 +-660,-479,-426 +832,-632,460 +927,-485,-438 +408,393,-506 +466,436,-512 +110,16,151 +-258,-428,682 +-393,719,612 +-211,-452,876 +808,-476,-593 +-575,615,604 +-485,667,467 +-680,325,-822 +-627,-443,-432 +872,-547,-609 +833,512,582 +807,604,487 +839,-516,451 +891,-625,532 +-652,-548,-490 +30,-46,-14 diff --git a/21/src/main.rs b/21/src/main.rs new file mode 100644 index 0000000..54a03f1 --- /dev/null +++ b/21/src/main.rs @@ -0,0 +1,192 @@ +use advent_lib::prelude::*; + +use std::collections::HashMap; + + +#[derive(Debug, Clone)] +struct GameState { + next_roll: i64, + roll_odometer: i64, + next_player_index: i64, + players: Vec, +} + +#[derive(Debug, Clone, Eq, PartialEq, Hash)] +struct NondeterministicState { + next_player_index: i64, + players: Vec, +} + +#[derive(Debug, Clone, Eq, PartialEq, Hash)] +struct PlayerState { + position: i64, + score: i64, +} + +#[derive(Debug, Clone)] +struct GameParameters { + die_size: i64, + required_score: i64, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut players = Vec::new(); + for line in &input { + let words: Vec<&str> = line.split_whitespace().collect(); + let position = words[4].parse::().unwrap(); + players.push(PlayerState { + position: position, + score: 0, + }); + } + let initial_state = GameState { + next_roll: 1, + roll_odometer: 0, + next_player_index: 0, + players, + }; + + let mut state = initial_state.clone(); + let parameters = GameParameters { + die_size: 100, + required_score: 1000, + }; + loop { + iterate(&mut state, ¶meters); + if is_done(&state, ¶meters) { + break; + } + } + + let result = losing_player(&state, ¶meters).score * state.roll_odometer; + println!("{}", result); + + let parameters = GameParameters { + die_size: 3, + required_score: 21, + }; + let mut all_states = HashMap::new(); + all_states.insert(NondeterministicState { + next_player_index: initial_state.next_player_index, + players: initial_state.players.clone(), + }, 1); + let mut victories = vec![0, 0]; + loop { + if all_states.len() == 0 { + break; + } + //println!("{:?}", all_states); + + let (new_all_states, new_victories) = iterate_nondeterministic( + &all_states, ¶meters); + for (i, n) in new_victories.iter().enumerate() { + victories[i] += n; + } + all_states = new_all_states; + } + + let mut max_victories = victories[0]; + if victories[1] > max_victories { + max_victories = victories[1]; + } + println!("{}", max_victories); + + Ok(()) +} + + +fn iterate(state: &mut GameState, parameters: &GameParameters) { + let player = &mut state.players[state.next_player_index as usize]; + + let mut roll = 0; + for _ in 0 .. 3 { + roll += state.next_roll; + state.next_roll = (state.next_roll % parameters.die_size) + 1; + + state.roll_odometer += 1; + } + + player.position = (player.position + roll - 1) % 10 + 1; + player.score += player.position; + + state.next_player_index = (state.next_player_index + 1) % 2; +} + + +fn is_done(state: &GameState, parameters: &GameParameters) -> bool { + for player in &state.players { + if player.score >= parameters.required_score { + return true; + } + } + + return false; +} + + +fn losing_player<'a>(state: &'a GameState, parameters: &GameParameters) + -> &'a PlayerState +{ + for player in &state.players { + if player.score < parameters.required_score { + return player; + } + } + + panic!("everybody wins"); +} + + +fn iterate_nondeterministic(all_states: &HashMap, + parameters: &GameParameters) + -> (HashMap, Vec) +{ + let mut new_all_states = HashMap::new(); + let mut victory_counts = vec![0, 0]; + + for (state, count_in) in all_states.iter() { + for (roll, count_here) in [ + (3, 1), (4, 3), (5, 6), (6, 7), (7, 6), (8, 3), (9, 1)].iter() + { + let mut new_state = state.clone(); + let player_index = new_state.next_player_index as usize; + + new_state.players[player_index].position = + (new_state.players[player_index].position + roll - 1) % 10 + 1; + new_state.players[player_index].score += + new_state.players[player_index].position; + + new_state.next_player_index = (new_state.next_player_index + 1) % 2; + + let new_score = new_state.players[player_index].score; + + let unrelated_count = match new_all_states.get(&new_state) { + None => 0, + Some(n) => *n, + }; + + let count_out = unrelated_count + count_in*count_here; + + if new_score >= parameters.required_score { + //println!("logging victory for {} x{}", player_index, count_out); + victory_counts[player_index] += count_out; + } else { + //println!("logging x{} {:?}", count_out, new_state); + new_all_states.insert(new_state.clone(), count_out); + } + } + } + + (new_all_states, victory_counts) +} + diff --git a/21/tests/main.rs b/21/tests/main.rs new file mode 100644 index 0000000..b340c65 --- /dev/null +++ b/21/tests/main.rs @@ -0,0 +1,17 @@ +use assert_cmd::prelude::*; +//use predicates::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box> { + let mut command = Command::cargo_bin("advent_21")?; + + command.arg("input"); + command.assert().success().stdout( + "888735\n\ + 647608359455719\n"); + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index 12d658b..0cab4ef 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -162,6 +162,14 @@ dependencies = [ "assert_cmd", ] +[[package]] +name = "advent_21" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + [[package]] name = "advent_lib" version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml index 154b354..803c3a9 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -21,4 +21,5 @@ members = [ "18", "19", "20", + "21", ] -- cgit 1.4.1