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