1 files changed, 192 insertions, 0 deletions
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)
+}
+