-
Notifications
You must be signed in to change notification settings - Fork 4
/
day20.rs
104 lines (90 loc) · 3.83 KB
/
day20.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//! # Trench Map
//!
//! This is a cellular automata problem, similar to Conway's Game of Life, except that the rules
//! are encoded in the enhancement algorithm string, instead of being statically specified. Each
//! round the initial square area of cells expands by at most one in each direction, so we can store
//! the cell in a fixed size array with enough space on either side to expand into.
//!
//! The interesting nuance is handling the edge cells when all 9 cells are empty (index 0) or all
//! 9 cell are active (index 511). The sample data encodes a blank cell in both scenarios.
//! My input encoded an active cell for index 0 and a blank cell for index 511, meaning that each
//! turn the edge cells toggle from set to unset.
//!
//! The algorithm keeps track of the bounds of the expanding square and supplies a `default` value,
//! that in the example case is always zero, but in the real data toggles between zero and one.
pub struct Input {
size: usize,
algorithm: [u8; 512],
pixels: [u8; 40_000],
}
pub fn parse(input: &str) -> Input {
// `#` is odd and `.` is even so we can convert to one or zero by bitwise AND with 1.
let bits: Vec<Vec<_>> =
input.lines().map(|line| line.bytes().map(|b| b & 1).collect()).collect();
let size = bits.len() - 2;
let algorithm = bits[0][..512].try_into().unwrap();
// Offset the initial square by 50 cells in both dimensions.
// The square expands by at most one in each step so this is enough room to stay within bounds.
let mut pixels = [0; 40_000];
for (i, row) in bits[2..].iter().enumerate() {
let start = (i + 50) * 200 + 50;
let end = start + size;
pixels[start..end].copy_from_slice(&row[..size]);
}
Input { size, algorithm, pixels }
}
pub fn part1(input: &Input) -> usize {
enhance(input, 2)
}
pub fn part2(input: &Input) -> usize {
enhance(input, 50)
}
fn enhance(input: &Input, steps: usize) -> usize {
let algorithm = input.algorithm;
let mut pixels = input.pixels;
let mut next = [0; 40_000];
let mut start = 50;
let mut end = 50 + input.size as i32;
let mut default = 0;
for _ in 0..steps {
for y in (start - 1)..(end + 1) {
// If the pixel is within current bounds then return it, or else use the `default`
// edge value specified by the enhancement algorithm.
let helper = |sx, sy, shift| {
let result = if sx < end && sy >= start && sy < end {
pixels[(sy * 200 + sx) as usize] as usize
} else {
default as usize
};
result << shift
};
// If the edge pixels are 1 then the inital edge will look like
// [##a]
// [##b]
// [##c]
// or 11a11b11c when encoded as an index.
let mut index = if default == 1 { 0b11011011 } else { 0b00000000 };
for x in (start - 1)..(end + 1) {
// Keeps a sliding window of the index, updated as we evaluate the row from
// left to right. Shift the index left by one each turn, updating the values from
// the three new rightmost pixels entering the window.
index = ((index << 1) & 0b110110110)
+ helper(x + 1, y - 1, 6)
+ helper(x + 1, y, 3)
+ helper(x + 1, y + 1, 0);
next[(y * 200 + x) as usize] = algorithm[index];
}
}
// Boundaries expand by one each turn
pixels = next;
start -= 1;
end += 1;
// Calculate the next value for edge pixels beyond the boundary.
if default == 0 {
default = algorithm[0];
} else {
default = algorithm[511];
}
}
pixels.iter().filter(|&&p| p == 1).count()
}