aoc/year2020/
day11.rs

1//! # Seating System
2//!
3//! Cellular automata are hard to speed up due to the need to check all neighbors each iteration.
4//! For both parts we minimize expensive memory allocation by creating only two temporary buffers
5//! then swapping between them each turn, a similar approach to double buffering.
6//!
7//! For part two we can further optimize by precalculating the locations of the nearest visible
8//! seats only once then reusing that information for each step.
9use crate::util::grid::*;
10use crate::util::point::*;
11use std::mem::swap;
12
13const FLOOR: u8 = b'.';
14const DIRECTIONS: [Point; 8] = [
15    Point::new(-1, -1),
16    Point::new(0, -1),
17    Point::new(1, -1),
18    Point::new(-1, 0),
19    Point::new(1, 0),
20    Point::new(-1, 1),
21    Point::new(0, 1),
22    Point::new(1, 1),
23];
24
25struct Seat {
26    index: u16,
27    size: u8,
28    neighbors: [u16; 8],
29}
30
31impl Seat {
32    #[inline]
33    fn push(&mut self, index: u16) {
34        self.neighbors[self.size as usize] = index;
35        self.size += 1;
36    }
37}
38
39pub fn parse(input: &str) -> Grid<u8> {
40    Grid::parse(input)
41}
42
43pub fn part1(input: &Grid<u8>) -> u32 {
44    simulate(input, true, 4)
45}
46
47pub fn part2(input: &Grid<u8>) -> u32 {
48    simulate(input, false, 5)
49}
50
51pub fn simulate(input: &Grid<u8>, part_one: bool, limit: u8) -> u32 {
52    let width = input.width;
53    let height = input.height;
54    let mut seats = Vec::new();
55
56    for y in 0..height {
57        for x in 0..width {
58            let point = Point::new(x, y);
59            if input[point] == FLOOR {
60                continue;
61            }
62
63            let mut seat = Seat { index: (width * y + x) as u16, size: 0, neighbors: [0; 8] };
64
65            for direction in DIRECTIONS {
66                if part_one {
67                    let next = point + direction;
68                    if input.contains(next) && input[next] != FLOOR {
69                        seat.push((width * next.y + next.x) as u16);
70                    }
71                } else {
72                    let mut next = point + direction;
73                    while input.contains(next) {
74                        if input[next] != FLOOR {
75                            seat.push((width * next.y + next.x) as u16);
76                            break;
77                        }
78                        next += direction;
79                    }
80                }
81            }
82
83            seats.push(seat);
84        }
85    }
86
87    let mut current = vec![0; (width * height) as usize];
88    let mut next = vec![0; (width * height) as usize];
89    let mut change = true;
90
91    while change {
92        change = false;
93
94        for seat in &seats {
95            let index = seat.index as usize;
96            let mut total = 0;
97
98            for i in 0..seat.size {
99                total += current[seat.neighbors[i as usize] as usize];
100            }
101
102            if current[index] == 0 && total == 0 {
103                next[index] = 1;
104                change |= true;
105            } else if current[index] == 1 && total >= limit {
106                next[index] = 0;
107                change |= true;
108            } else {
109                next[index] = current[index];
110            }
111        }
112
113        swap(&mut current, &mut next);
114    }
115
116    current.iter().map(|&n| n as u32).sum()
117}
aoc/year2020/day11.rs

aoc/year2020/
day11.rs
