year2018/
day11.rs

1use utils::prelude::*;
2
3/// Locating the optimal square subregion.
4///
5/// See <https://en.wikipedia.org/wiki/Summed-area_table>, which allows computing the sum of any
6/// square in constant time with only 4 lookups.
7#[derive(Clone, Debug)]
8pub struct Day11 {
9    summed_area_table: Vec<i32>,
10}
11
12impl Day11 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        let serial_num = parser::number_range(0..=9999).parse_complete(input)?;
15
16        let mut table = vec![0i32; 301 * 301];
17        for y in 1..301 {
18            for x in 1..301 {
19                let rack_id = x + 10;
20                let power_level = ((rack_id * y + serial_num) * rack_id) / 100 % 10 - 5;
21                let index = (y * 301 + x) as usize;
22                table[index] =
23                    power_level + table[index - 1] + table[index - 301] - table[index - 302];
24            }
25        }
26
27        Ok(Self {
28            summed_area_table: table,
29        })
30    }
31
32    #[must_use]
33    pub fn part1(&self) -> String {
34        let (_, x, y) = self.largest_total_power(3);
35        format!("{x},{y}")
36    }
37
38    #[must_use]
39    pub fn part2(&self) -> String {
40        let (mut max_size, mut max_total, mut max_x, mut max_y) = (0, i32::MIN, 0, 0);
41        let mut sizes: Vec<i32> = Vec::with_capacity(300);
42
43        for size in 1usize..=300 {
44            // Try to split the N*N square into Y X*X squares to calculate an upper bound.
45            // For example, if the best 5x5 is 100, then the best 10x10 must be <= 400.
46            if let Some(divisor) = (2..=size / 2).rev().find(|&d| size.is_multiple_of(d)) {
47                let copies = (size / divisor) * (size / divisor);
48                let upper_bound = sizes[divisor - 1].saturating_mul(copies as i32);
49                if upper_bound < max_total {
50                    sizes.push(upper_bound);
51                    continue;
52                }
53            };
54
55            let (total, x, y) = self.largest_total_power(size);
56            sizes.push(total);
57
58            if total > max_total {
59                max_size = size;
60                max_total = total;
61                max_x = x;
62                max_y = y;
63            }
64        }
65
66        format!("{max_x},{max_y},{max_size}")
67    }
68
69    fn largest_total_power(&self, size: usize) -> (i32, u32, u32) {
70        let (mut max_total, mut max_x, mut max_y) = (i32::MIN, 0, 0);
71        let mut row_totals = [0; 301];
72
73        for y in 0..301 - size {
74            // Avoids bounds checks, allowing the inner loop to be vectorized
75            let mut found_new_max = false;
76            for ((((total, &top_left), &top_right), &bottom_left), &bottom_right) in row_totals
77                [..301 - size]
78                .iter_mut()
79                .zip(self.summed_area_table[y * 301..].iter())
80                .zip(self.summed_area_table[y * 301 + size..].iter())
81                .zip(self.summed_area_table[(y + size) * 301..].iter())
82                .zip(self.summed_area_table[(y + size) * 301 + size..].iter())
83            {
84                *total = top_left + bottom_right - top_right - bottom_left;
85                found_new_max |= *total > max_total;
86            }
87
88            // Only perform scalar comparisons when a new max has been found
89            if found_new_max {
90                for (x, &total) in row_totals[..301 - size].iter().enumerate() {
91                    if total > max_total {
92                        max_total = total;
93                        max_x = x as u32 + 1;
94                        max_y = y as u32 + 1;
95                    }
96                }
97            }
98        }
99        (max_total, max_x, max_y)
100    }
101}
102
103examples!(Day11 -> (&'static str, &'static str) [
104    {input: "18", part1: "33,45", part2: "90,269,16"},
105    {input: "42", part1: "21,61", part2: "232,251,12"},
106]);
year2018/day11.rs

year2018/
day11.rs
