21

5 files changed, 358 insertions, 0 deletions

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 <ireneista@gmail.com>"]
+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<PlayerState>,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
+struct NondeterministicState {
+  next_player_index: i64,
+  players: Vec<PlayerState>,
+}
+
+#[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::<i64>().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, &parameters);
+    if is_done(&state, &parameters) {
+      break;
+    }
+  }
+
+  let result = losing_player(&state, &parameters).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, &parameters);
+    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<NondeterministicState,i64>,
+    parameters: &GameParameters)
+  -> (HashMap<NondeterministicState,i64>, Vec<i64>)
+{
+  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<dyn std::error::Error>> {
+  let mut command = Command::cargo_bin("advent_21")?;
+
+  command.arg("input");
+  command.assert().success().stdout(
+      "888735\n\
+      647608359455719\n");
+
+  Ok(())
+}
+