3 files changed, 109 insertions, 0 deletions

diff --git a/2021/day21/Cargo.toml b/2021/day21/Cargo.toml
new file mode 100644
index 0000000..c2bd70c
--- /dev/null
+++ b/2021/day21/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day21"
+version = "0.1.0"
+authors = ["Federico Igne <git@federicoigne.com>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/2021/day21/resources/input.txt b/2021/day21/resources/input.txt
new file mode 100644
index 0000000..085f690
--- /dev/null
+++ b/2021/day21/resources/input.txt
@@ -0,0 +1,2 @@
+Player 1 starting position: 4
+Player 2 starting position: 10
diff --git a/2021/day21/src/main.rs b/2021/day21/src/main.rs
new file mode 100644
index 0000000..55e70f6
--- /dev/null
+++ b/2021/day21/src/main.rs
@@ -0,0 +1,98 @@
+use std::fs;
+use std::path::Path;
+use std::collections::HashMap;
+
+const ROLLS: [(u64,u64);7] = [(3,1),(4,3),(5,6),(6,7),(7,6),(8,3),(9,1)];
+
+struct Player {
+    pos: u32,
+    score: u32
+}
+
+struct QPlayer {
+    plays: HashMap<(u8,u64,u64),u64>,
+    wins: HashMap<u8,u64>,
+    turn: u8
+}
+
+impl QPlayer {
+    fn new(pos: u64) -> QPlayer {
+        let mut plays = HashMap::new();
+        plays.insert((0,pos,0), 1);
+        QPlayer { plays, wins: HashMap::new(), turn: 0}
+    }
+
+    /// Return true if any current state advanced
+    fn quantum_roll(&mut self) -> bool {
+        let mut ret = false;
+        // Compute update
+        let mut plays = vec![];
+        let mut wins = vec![];
+        self.plays.iter().for_each(|(&(t,p,s), &n)| {
+            if t == self.turn {
+                if s > 20 {
+                    wins.push((t,n));
+                } else {
+                    ret = true;
+                    for (roll,card) in ROLLS.iter() {
+                        let pos = (p + roll) % 10;
+                        plays.push((t+1,pos,s+pos+1,n*card));
+                    }
+                }
+            }
+        });
+        // Apply update
+        plays.iter().for_each(|&(t,p,s,n)| *self.plays.entry((t,p,s)).or_default() += n);
+        wins.iter().for_each(|&(t,n)| *self.wins.entry(t).or_default() += n);
+        self.turn += 1;
+        ret
+    }
+}
+
+/* AOC21 Day 21: https://adventofcode.com/2021/day/21 */
+fn main() {
+    let input = Path::new("resources").join("input.txt");
+    let content = fs::read_to_string(input).expect("Unable to read input file");
+    println!("Ex1: the result is {}", ex1(&content));
+    println!("Ex2: the result is {}", ex2(&content));
+}
+
+fn parse_input(input: &str) -> Vec<Player> {
+    input.lines().map(|l| {
+        let (_,pos) = l.split_once(": ").expect("Malformed input");
+        Player { pos: pos.parse::<u32>().unwrap() - 1, score: 0 }
+    }).collect()
+}
+
+fn ex1(input: &str) -> u32 {
+    let mut players = parse_input(input);
+    let mut p = players.len()-1;
+    let mut turn = 0;
+    while players[p].score < 1000 {
+        p = (p+1) % players.len();
+        players[p].pos = (players[p].pos + 9*turn + 6) % 10;
+        players[p].score += players[p].pos + 1;
+        turn += 1;
+    }
+    players[(p+1) % players.len()].score * turn * 3
+}
+
+fn ex2(input: &str) -> u64 {
+    let mut p1 = {
+        let (_,pos) = input.lines().nth(0).unwrap().split_once(": ").expect("Malformed input");
+        QPlayer::new(pos.parse::<u64>().unwrap() - 1)
+    };
+    let mut p2 = {
+        let (_,pos) = input.lines().nth(1).unwrap().split_once(": ").expect("Malformed input");
+        QPlayer::new(pos.parse::<u64>().unwrap() - 1)
+    };
+    while p1.quantum_roll() { }
+    while p2.quantum_roll() { }
+    let p1wins = p1.wins.iter().map(|(&t1,&n1)| {
+        p2.plays.iter().filter_map(|(&(t2,_,s2),&n2)| if t1 == t2+1 && s2 < 21 { Some(n1*n2) } else { None }).sum::<u64>()
+    }).sum();
+    let p2wins = p2.wins.iter().map(|(&t2,&n2)|
+        p1.plays.iter().filter_map(|(&(t1,_,s1),&n1)| if t1 == t2 && s1 < 21 { Some(n1*n2) } else { None }).sum::<u64>()
+    ).sum();
+    u64::max(p1wins, p2wins)
+}