main.rs (3851B)
1 use std::collections::{HashMap, VecDeque};
2
3 fn main() {
4 let (p1, p2) = (7, 1);
5 // 684495
6 println!("Part 1: {}", part_1(p1, p2, 1000));
7 // 152587196649184
8 println!("Part 2: {}", part_2(p1, p2, 21));
9 }
10
11 struct DeterministicDice {
12 value: usize,
13 count: usize,
14 }
15
16 impl DeterministicDice {
17 fn next(&mut self) -> usize {
18 self.value = self.value % 100 + 1;
19 self.count += 1;
20 self.value
21 }
22 }
23
24 fn part_1(mut p1: usize, mut p2: usize, winning_score: usize) -> usize {
25 let mut dice = DeterministicDice { value: 0, count: 0 };
26 let mut p1_score = 0;
27 let mut p2_score = 0;
28 loop {
29 p1 = (p1 + dice.next() + dice.next() + dice.next() - 1) % 10 + 1;
30 p1_score += p1;
31 if p1_score >= winning_score {
32 return dice.count * p2_score;
33 }
34 p2 = (p2 + dice.next() + dice.next() + dice.next() - 1) % 10 + 1;
35 p2_score += p2;
36 if p2_score >= winning_score {
37 return dice.count * p1_score;
38 }
39 }
40 }
41
42 fn calc_winning_steps(p: usize, winning_score: usize) -> HashMap<usize, usize> {
43 // comput number of ways to win in n steps
44 let mut winning_steps = HashMap::new();
45 let mut queue = VecDeque::new();
46 queue.push_back((p, 0, 0, 1));
47 while let Some((pos, score, step_count, mult)) = queue.pop_front() {
48 let mut next_batch = HashMap::new();
49 for dice_1 in 1..=3 {
50 for dice_2 in 1..=3 {
51 for dice_3 in 1..=3 {
52 let next_pos = (pos + dice_1 + dice_2 + dice_3 - 1) % 10 + 1;
53 let next_score = score + next_pos;
54 let next_step_count = step_count + 1;
55 if next_score >= winning_score {
56 winning_steps.insert(
57 next_step_count,
58 *winning_steps.get(&next_step_count).unwrap_or(&0) + mult,
59 );
60 } else {
61 let entry = (next_pos, next_score, next_step_count);
62 next_batch.insert(entry, *next_batch.get(&entry).unwrap_or(&0) + mult);
63 }
64 }
65 }
66 }
67 for ((next_pos, next_score, next_step_count), next_mult) in next_batch.into_iter() {
68 queue.push_back((next_pos, next_score, next_step_count, next_mult));
69 }
70 }
71 winning_steps
72 }
73
74 fn part_2(p1: usize, p2: usize, winning_score: usize) -> usize {
75 let p1_winning_steps = calc_winning_steps(p1, winning_score);
76 let p2_winning_steps = calc_winning_steps(p2, winning_score);
77
78 let mut p1_win_count = 0;
79 for (&p1_step, &p1_step_win_count) in p1_winning_steps.iter() {
80 // p1 moves first, so p2 have only moved p1_step - 1 steps
81 let p2_step_win_count = p2_winning_steps
82 .iter()
83 .filter(|&(p2_step, _)| *p2_step <= p1_step - 1)
84 .map(|(p2_step, p2_count)| {
85 p2_count * 3usize.pow(3).pow(((p1_step - 1) - p2_step) as u32)
86 })
87 .sum::<usize>();
88 let p2_step_lose_count = 3usize.pow(3).pow((p1_step - 1) as u32) - p2_step_win_count;
89 p1_win_count += p1_step_win_count * p2_step_lose_count;
90 }
91
92 let mut p2_win_count = 0;
93 for (&p2_step, &p2_step_win_count) in p2_winning_steps.iter() {
94 // p1 moves first, so p1 have also moved p2_step steps
95 let p1_step_win_count = p1_winning_steps
96 .iter()
97 .filter(|&(p1_step, _)| *p1_step <= p2_step)
98 .map(|(p1_step, p1_count)| p1_count * 3usize.pow(3).pow((p2_step - p1_step) as u32))
99 .sum::<usize>();
100 let p1_step_lose_count = 3usize.pow(3).pow(p2_step as u32) - p1_step_win_count;
101 p2_win_count += p2_step_win_count * p1_step_lose_count;
102 }
103
104 p1_win_count.max(p2_win_count)
105 }