aoc/year2017/day22.rs
1//! # Sporifica Virus
2//!
3//! Part two is made faster by a factor of two by packing 4 nodes into each byte using
4//! 2 bits per node. Then multiple steps are memoized for each of the 256 possible states,
5//! for each of the 4 positions and each of the 4 directions, for a total of 4,096 combinations.
6//! This allows us to skip forward up to 8 steps at a time. For example:
7//!
8//! ```none
9//! . = Clean # = Infected F = Flagged W = Weakened
10//!
11//! State Direction Steps Infected
12//! [W] # Down 0 0
13//! F W
14//!
15//! # # Down 1 1
16//! [F] W
17//!
18//! [#] # Up 2 1
19//! . W
20//!
21//! F [#] Right 3 1
22//! . W
23//!
24//! F F Down 4 1
25//! . [W]
26//!
27//! F F Down 5 2
28//! . #
29//! [ ]
30//! ```
31//!
32//! Starting in the top-left corner facing down, after 5 steps the virus carrier leaves the 2x2
33//! block having infected 2 nodes. This is memoized as:
34//!
35//! ```none
36//! [0][2][01111001] => (2, 5, 10001111)
37//! ```
38use crate::util::grid::*;
39use crate::util::point::*;
40use std::array::from_fn;
41use std::mem::take;
42
43const SIZE: usize = 250;
44const HALF: usize = SIZE / 2;
45const CENTER: usize = SIZE * HALF + HALF;
46
47pub fn parse(input: &str) -> Grid<u8> {
48 Grid::parse(input)
49}
50
51/// Direct implementation on a fixed-size grid.
52pub fn part1(input: &Grid<u8>) -> u32 {
53 let size = SIZE as i32;
54 let center = Point::new(size, size);
55 let offset = center - Point::new(input.width / 2, input.height / 2);
56
57 // Assume the virus carrier will never leave a 500 x 500 grid, starting at the center.
58 let mut grid = Grid::new(2 * size, 2 * size, false);
59 let mut position = center;
60 let mut direction = UP;
61 let mut infected = 0;
62
63 // Copy the smaller initial input grid to the center of the larger grid.
64 for y in 0..input.height {
65 for x in 0..input.width {
66 let point = Point::new(x, y);
67 grid[point + offset] = input[point] == b'#';
68 }
69 }
70
71 // The grid toggles between clean and infected.
72 for _ in 0..10_000 {
73 direction = if grid[position] {
74 direction.clockwise()
75 } else {
76 infected += 1;
77 direction.counter_clockwise()
78 };
79 grid[position] = !grid[position];
80 position += direction;
81 }
82
83 infected
84}
85
86/// Use a compressed grid where each byte stores 4 cells (2x2 block) with 2 bits per cell.
87pub fn part2(input: &Grid<u8>) -> usize {
88 // Assume that the carrier will never go outside the range 0 to 500 in both x and y axes
89 // starting at the center. As we store 4 nodes per byte, we compress the x and y axes by two.
90 let mut grid = vec![0; SIZE * SIZE];
91
92 // Precompute all 4 * 4 * 256 possible state transitions for faster simulation.
93 let cache: [[[_; 256]; 4]; 4] = from_fn(|quadrant| {
94 from_fn(|direction| from_fn(|state| compute_block(&mut grid, quadrant, direction, state)))
95 });
96
97 // Copy the smaller initial input grid to the center of the larger grid,
98 // packing 4 nodes into each byte.
99 let offset = SIZE - (input.width / 2) as usize;
100
101 for x in 0..input.width {
102 for y in 0..input.height {
103 if input[Point::new(x, y)] == b'#' {
104 let (adjusted_x, adjusted_y) = (x as usize + offset, y as usize + offset);
105 let index = SIZE * (adjusted_y / 2) + (adjusted_x / 2);
106 let offset = 4 * (adjusted_y % 2) + 2 * (adjusted_x % 2);
107 // Mark node as infected.
108 grid[index] |= 2 << offset;
109 }
110 }
111 }
112
113 // Start in the center of the grid, in the top-left corner of a 2x2 cell, facing up.
114 let mut index = CENTER;
115 let mut quadrant = 0; // Top-left corner
116 let mut direction = 0; // Facing up
117 let mut infected = 0;
118 let mut remaining = 10_000_000;
119
120 // Memoized blocks can combine up to 8 steps. Handle the last few steps individually to
121 // prevent overshooting the step target and overcounting the infected node transitions.
122 while remaining > 8 {
123 let state = grid[index] as usize;
124 let packed = cache[quadrant][direction][state];
125
126 // With 10 million repetitions, saving time inside this hot loop is essential.
127 // By bit-packing 6 fields into a single `u32`, we limit the size of the array to 16kB
128 // making sure that it fits into L1 cache.
129 grid[index] = packed as u8; // bits 0-7
130 index = index + (packed >> 20) as usize - SIZE; // bits 20 to 31
131 quadrant = ((packed >> 8) % 4) as usize; // bits 8-9
132 direction = ((packed >> 10) % 4) as usize; // bits 10-11
133 infected += ((packed >> 12) % 16) as usize; // bits 12-15
134 remaining -= ((packed >> 16) % 16) as usize; // bits 16-19
135 }
136
137 // Handle up to 8 remaining steps individually to prevent overcounting.
138 for _ in 0..remaining {
139 let [next_index, next_quadrant, next_direction, next_infected] =
140 step(&mut grid, index, quadrant, direction);
141 index = next_index;
142 quadrant = next_quadrant;
143 direction = next_direction;
144 infected += next_infected;
145 }
146
147 infected
148}
149
150/// Computes the number of steps taken, infected nodes and next location for 2 x 2 blocks of nodes.
151fn compute_block(grid: &mut [u8], mut quadrant: usize, mut direction: usize, state: usize) -> u32 {
152 let mut index = CENTER;
153 let mut infected = 0;
154 let mut steps = 0;
155
156 // Temporarily use the grid. This allows the index to move without exceeding bounds.
157 grid[CENTER] = state as u8;
158
159 // Count steps and infected nodes until we leave this cell.
160 while index == CENTER {
161 let [next_index, next_quadrant, next_direction, next_infected] =
162 step(grid, index, quadrant, direction);
163 index = next_index;
164 quadrant = next_quadrant;
165 direction = next_direction;
166 infected += next_infected;
167 steps += 1;
168 }
169
170 // Reset the grid to zero and figure out the next index. We offset index by SIZE to keep the
171 // value positive for easier bit manipulation.
172 let next_state = take(&mut grid[CENTER]);
173 let next_index = index + SIZE - CENTER;
174
175 // Pack six fields into a single `u32`, maximizing cache locality by minimizing space.
176 next_state as u32
177 | (quadrant << 8) as u32
178 | (direction << 10) as u32
179 | (infected << 12) as u32
180 | (steps << 16)
181 | (next_index << 20) as u32
182}
183
184// Process a single step in any arbitrary location on the grid.
185fn step(grid: &mut [u8], index: usize, quadrant: usize, direction: usize) -> [usize; 4] {
186 // 4 nodes are packed into a single byte with quadrants arranged as:
187 // [ 0 1 ]
188 // [ 2 3 ]
189 let shift = 2 * quadrant;
190 let node = (grid[index] >> shift) % 4;
191
192 // Nodes cycle between 4 possible values:
193 // 0 = Clean, 1 = Weakened, 2 = Infected, 3 = Flagged
194 let next_node = (node + 1) % 4;
195 // Direction changes based on the *previous* value of the node. In clockwise order:
196 // 0 = Up, 1 = Right, 2 = Down, 3 = Left
197 let next_direction = (direction + node as usize + 3) % 4;
198
199 // Update the 2 bits representing the current node.
200 let mask = !(0b11 << shift);
201 grid[index] = (grid[index] & mask) | (next_node << shift);
202
203 // Calculate x and y coordinates as if a single node was stored in each cell.
204 // This is used in the next step in order to calculate if the index has changed.
205 let (x, y) = (2 * (index % SIZE) + quadrant % 2, 2 * (index / SIZE) + quadrant / 2);
206 let (x, y) = match next_direction {
207 0 => (x, y - 1),
208 1 => (x + 1, y),
209 2 => (x, y + 1),
210 3 => (x - 1, y),
211 _ => unreachable!(),
212 };
213
214 // Convert the x and y coordinates back into the compressed values for 2 x 2 nodes in each cell.
215 let next_index = SIZE * (y / 2) + (x / 2);
216 let next_quadrant = 2 * (y % 2) + (x % 2);
217 let infected = usize::from(next_node == 2);
218
219 [next_index, next_quadrant, next_direction, infected]
220}