aoc/year2018/day09.rs
1//! # Marble Mania
2//!
3//! Efficient solution using an append-only `vec` and generating only the minimum number of marbles
4//! needed to play the game.
5//!
6//! First let's consider some other slower approaches.
7//!
8//! We could store marbles in a `vec`, inserting and removing elements to make room. Each of these
9//! operations takes `O(n)` complexity. For part two if the number of marbles is 100,000 then the
10//! total complexity is `100,000 * 100 * 100,000 = 10¹²` which is infeasible.
11//!
12//! A better approach is a linked list. Insert and remove operations are now `O(1)` for a total
13//! part two complexity of `100,000 * 1 * 100 = 10⁷`. This is slow but practical. However, linked
14//! lists have a number of drawbacks:
15//!
16//! 1. Poor cache locality.
17//! 2. Allocation per element.
18//! 3. Ownership issues complex enough to inspire an entire [blog post series](https://rust-unofficial.github.io/too-many-lists/).
19//!
20//! ## First optimization
21//!
22//! The first key insight is that we can generate the marble sequence by only appending to a `vec`.
23//! We keep track of the head `()` and tail `<>` of the circle. Each turn adds two marbles to the
24//! head and removes one from the tail, growing the circle by one each time.
25//! For example, the first 4 marbles look like:
26//!
27//! ```none
28//! <0>
29//! 0 <0> (1)
30//! 0 0 <1> 0 (2)
31//! 0 0 1 <0> 2 1 (3)
32//! 0 0 1 0 <2> 1 3 0 (4)
33//! ```
34//!
35//! Things start to get interesting at the 19th marble. When we pick the 23rd marble this will
36//! be 7 places counter-clockwise, so we can optimize by not adding it at all to the circle.
37//! Instead we save the value for later.
38//!
39//! ```none
40//! 18th marble
41//! ...<9> 2 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 (18)
42//!
43//! 19th marble, saving value of previous tail 9.
44//! ...<2> 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 (19)
45//! ```
46//!
47//! For the 20th, 21st and 22nd marbles we re-write the history of the tail then move it backward.
48//!
49//! ```none
50//! 20th marble
51//! ... 2 20 9 <2> 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 (19)
52//! ^ ^^
53//!
54//! 21st marble
55//! ... 2 20 10 <21> 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 (19)
56//! ^^ ^^
57//!
58//! 22nd marble (move tail)
59//! ...<2> 20 10 21 5 22 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 (19)
60//! ^ ^^
61//! ```
62//!
63//! The 23rd marble is never added to the circle instead increasing the current player's score.
64//! The cycle then begins again, handling the next 18 marbles normally, then the next 19th to 22nd
65//! marbles specially.
66//!
67//! ## Second optimization
68//!
69//! It may seem that we need to generate `(last marble / 23)` blocks. However, in each block we add
70//! 37 marbles (2 each for the first 18 marbles and 1 for the 19th) while the marble added to each
71//! player's score advances `23 - 7 = 16` marbles. This means we only need to generate about
72//! `16/37` or `44%` of the total blocks to solve the game deterministically. This saves both
73//! processing time and memory storage proportionally.
74use crate::util::iter::*;
75use crate::util::parse::*;
76
77type Input = [usize; 2];
78
79pub fn parse(input: &str) -> Input {
80 input.iter_unsigned().chunk::<2>().next().unwrap()
81}
82
83pub fn part1(input: &Input) -> u64 {
84 let [players, last] = *input;
85 game(players, last)
86}
87
88pub fn part2(input: &Input) -> u64 {
89 let [players, last] = *input;
90 game(players, last * 100)
91}
92
93fn game(players: usize, last: usize) -> u64 {
94 // Play the game in blocks of 23.
95 let blocks = last / 23;
96 // The number of marbles needed for scoring.
97 let needed = 2 + 16 * blocks;
98 // Each block adds 37 marbles, so allow a little extra capacity to prevent reallocation.
99 let mut circle: Vec<u32> = vec![0; needed + 37];
100 // The score for each block is deterministic so the number of players only affects how scores
101 // are distributed. Type is `u64` to prevent overflow during part two.
102 let mut scores = vec![0; players];
103 // The first marble picked up and removed by the player is 9.
104 let mut pickup = 9;
105 // The first block is pre-generated, so we start at marble 23.
106 let mut head = 23;
107 // Keep track of previous marbles to re-add to the start of the circle and for scoring.
108 let mut tail = 0;
109 // Keep track of how many marbles have been placed.
110 let mut placed = 22;
111 // Add pre-generated marbles for first block.
112 let start = [2, 20, 10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 19];
113 circle[0..22].copy_from_slice(&start);
114
115 for _ in 0..blocks {
116 // Score the previous block.
117 scores[head as usize % players] += (head + pickup) as u64;
118 // The next marble picked up is from the current block.
119 pickup = circle[tail + 18];
120
121 // Generate the next block only until we have enough marbles to finish the game.
122 if placed <= needed {
123 // Extending a vector from a slice is faster than adding elements one at a time.
124 let slice = &[
125 circle[tail],
126 head + 1,
127 circle[tail + 1],
128 head + 2,
129 circle[tail + 2],
130 head + 3,
131 circle[tail + 3],
132 head + 4,
133 circle[tail + 4],
134 head + 5,
135 circle[tail + 5],
136 head + 6,
137 circle[tail + 6],
138 head + 7,
139 circle[tail + 7],
140 head + 8,
141 circle[tail + 8],
142 head + 9,
143 circle[tail + 9],
144 head + 10,
145 circle[tail + 10],
146 head + 11,
147 circle[tail + 11],
148 head + 12,
149 circle[tail + 12],
150 head + 13,
151 circle[tail + 13],
152 head + 14,
153 circle[tail + 14],
154 head + 15,
155 circle[tail + 15],
156 head + 16,
157 circle[tail + 16],
158 head + 17,
159 circle[tail + 17],
160 head + 18,
161 // circle[tail + 18] 19th marble is picked up and removed.
162 head + 19,
163 ];
164 circle[placed..placed + 37].copy_from_slice(slice);
165
166 // Overwrite the tail for the 20th, 21st and 22nd marbles.
167 let slice = &[
168 circle[tail + 19],
169 head + 20,
170 circle[tail + 20],
171 head + 21,
172 circle[tail + 21],
173 head + 22,
174 ];
175 circle[tail + 16..tail + 22].copy_from_slice(slice);
176
177 // Keep track of how many marbles have been placed.
178 placed += 37;
179 }
180
181 // Marbles increase by 23 per block but the tail only by 16 as we reset by 7 marbles
182 // according to the rules.
183 head += 23;
184 tail += 16;
185 }
186
187 *scores.iter().max().unwrap()
188}