1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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)
}
|
