year2018/
day09.rs

1use utils::prelude::*;
2
3/// Simulating a marble game.
4#[derive(Clone, Debug)]
5pub struct Day09 {
6    players: u32,
7    marbles: u32,
8}
9
10impl Day09 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        let (players, marbles) = parser::number_range(1..=999)
13            .with_suffix(" players; last marble is worth ")
14            .then(parser::number_range(23..=99_999))
15            .with_suffix(" points")
16            .parse_complete(input)?;
17
18        Ok(Self { players, marbles })
19    }
20
21    #[must_use]
22    pub fn part1(&self) -> u64 {
23        Self::max_score(self.players, self.marbles)
24    }
25
26    #[must_use]
27    pub fn part2(&self) -> u64 {
28        Self::max_score(self.players, self.marbles * 100)
29    }
30
31    fn max_score(players: u32, marbles: u32) -> u64 {
32        let batches = marbles / 23;
33
34        // Each batch does 23x pop_back, 7x push_back and 37x push_front, meaning the buffer only
35        // grows towards the front and the head pointer progresses far faster than the tail pointer.
36        // The score only depends on values near the tail and within each batch is computed before
37        // the tail is overwritten.
38        let len = ((batches - 1) as usize * 16).next_multiple_of(37) + 22;
39        let mut circle = vec![0u32; len];
40
41        // Start with the first batch completed to ensure there are enough entries to pop
42        circle[len - 22..].copy_from_slice(&[
43            18, 4, 17, 8, 16, 0, 15, 7, 14, 3, 13, 6, 12, 1, 11, 22, 5, 21, 10, 20, 2, 19,
44        ]);
45        let (mut head, mut tail) = (len - 22, len - 1);
46        let mut scores = vec![0u64; players as usize];
47        scores[(23 % players) as usize] += 32;
48
49        for base in (23..23 * batches).step_by(23) {
50            // Equivalent to the following operations, which naively add 23 marbles while keeping
51            // the current marble at the back of dequeue:
52            //  22x [push_front(pop_back), push_front(pop_back), push_back(i)]
53            //   7x [push_back(pop_front)]
54            //      [pop_back]
55
56            scores[((base + 23) % players) as usize] +=
57                (base + 23) as u64 + circle[tail - 19] as u64;
58
59            if head > 0 {
60                let push_front = [
61                    base + 18,
62                    circle[tail - 18],
63                    base + 17,
64                    circle[tail - 17],
65                    base + 16,
66                    circle[tail - 16],
67                    base + 15,
68                    circle[tail - 15],
69                    base + 14,
70                    circle[tail - 14],
71                    base + 13,
72                    circle[tail - 13],
73                    base + 12,
74                    circle[tail - 12],
75                    base + 11,
76                    circle[tail - 11],
77                    base + 10,
78                    circle[tail - 10],
79                    base + 9,
80                    circle[tail - 9],
81                    base + 8,
82                    circle[tail - 8],
83                    base + 7,
84                    circle[tail - 7],
85                    base + 6,
86                    circle[tail - 6],
87                    base + 5,
88                    circle[tail - 5],
89                    base + 4,
90                    circle[tail - 4],
91                    base + 3,
92                    circle[tail - 3],
93                    base + 2,
94                    circle[tail - 2],
95                    base + 1,
96                    circle[tail - 1],
97                    circle[tail],
98                ];
99                let push_back = [
100                    base + 22,
101                    circle[tail - 22],
102                    base + 21,
103                    circle[tail - 21],
104                    base + 20,
105                    circle[tail - 20],
106                    base + 19,
107                ];
108
109                circle[head - 37..head].copy_from_slice(&push_front);
110                circle[tail - 22..tail - 15].copy_from_slice(&push_back);
111
112                head -= 37;
113            }
114
115            tail -= 16;
116        }
117
118        scores.iter().copied().max().unwrap()
119    }
120}
121
122examples!(Day09 -> (u64, u64) [
123    {input: "10 players; last marble is worth 1618 points", part1: 8317},
124    {input: "13 players; last marble is worth 7999 points", part1: 146373},
125    {input: "17 players; last marble is worth 1104 points", part1: 2764},
126    {input: "21 players; last marble is worth 6111 points", part1: 54718},
127    {input: "30 players; last marble is worth 5807 points", part1: 37305},
128]);
year2018/day09.rs

year2018/
day09.rs
