aoc/year2018/
day11.rs

1//! # Chronal Charge
2//!
3//! Building a [summed-area table](https://en.wikipedia.org/wiki/Summed-area_table) allows us
4//! to compute the power of any rectangle with only 4 array lookups.
5//!
6//! This makes the total complexity `O(n³)`, however the calculation for each size is independent
7//! so we can parallelize over multiple threads.
8use crate::util::parse::*;
9use crate::util::thread::*;
10
11pub struct Result {
12    size: usize,
13    x: usize,
14    y: usize,
15    power: i32,
16}
17
18pub fn parse(input: &str) -> Vec<Result> {
19    let grid_serial_number: i32 = input.signed();
20
21    // Build Summed-area table. Add a little extra buffer to the end for the SIMD variant.
22    let mut sat = vec![0; 301 * 301 + 32];
23
24    for y in 1..301 {
25        for x in 1..301 {
26            let rack_id = x + 10;
27            let power_level = ((rack_id * y + grid_serial_number) * rack_id / 100) % 10 - 5;
28
29            let index = (301 * y + x) as usize;
30            sat[index] = power_level + sat[index - 1] + sat[index - 301] - sat[index - 302];
31        }
32    }
33
34    // Use as many cores as possible to parallelize the search.
35    // Smaller sizes take more time so use work stealing to keep all cores busy.
36    let items: Vec<_> = (1..301).collect();
37    let result = spawn_parallel_iterator(&items, |iter| {
38        iter.map(|&size| square(&sat, size)).collect::<Vec<_>>()
39    });
40    result.into_iter().flatten().collect()
41}
42
43pub fn part1(input: &[Result]) -> String {
44    let Result { x, y, .. } = input.iter().find(|r| r.size == 3).unwrap();
45    format!("{x},{y}")
46}
47
48pub fn part2(input: &[Result]) -> String {
49    let Result { size, x, y, .. } = input.iter().max_by_key(|r| r.power).unwrap();
50    format!("{x},{y},{size}")
51}
52
53/// Find the (x,y) coordinates and max power for a square of the specified size.
54#[cfg(not(feature = "simd"))]
55fn square(sat: &[i32], size: usize) -> Result {
56    let mut max_power = i32::MIN;
57    let mut max_x = 0;
58    let mut max_y = 0;
59
60    for y in size..301 {
61        for x in size..301 {
62            let index = 301 * y + x;
63
64            let power =
65                sat[index] - sat[index - size] - sat[index - 301 * size] + sat[index - 302 * size];
66
67            if power > max_power {
68                max_power = power;
69                max_x = x - size + 1;
70                max_y = y - size + 1;
71            }
72        }
73    }
74
75    Result { size, x: max_x, y: max_y, power: max_power }
76}
77
78/// Same as the scalar version but processing 16 lanes simultaneously.
79#[cfg(feature = "simd")]
80fn square(sat: &[i32], size: usize) -> Result {
81    use std::simd::cmp::SimdPartialOrd as _;
82    use std::simd::*;
83
84    const LANE_WIDTH: usize = 16;
85    type Vector = Simd<i32, LANE_WIDTH>;
86
87    let mut max_power = i32::MIN;
88    let mut max_x = 0;
89    let mut max_y = 0;
90
91    for y in size..301 {
92        for x in (size..301).step_by(LANE_WIDTH) {
93            let index = 301 * y + x;
94
95            let power: Vector = Simd::from_slice(&sat[index..])
96                - Simd::from_slice(&sat[index - size..])
97                - Simd::from_slice(&sat[index - 301 * size..])
98                + Simd::from_slice(&sat[index - 302 * size..]);
99
100            if power.simd_gt(Simd::splat(max_power)).any() {
101                let limit = 301 - x;
102                for (offset, power) in power.to_array().into_iter().enumerate().take(limit) {
103                    if power > max_power {
104                        max_power = power;
105                        max_x = x - size + 1 + offset;
106                        max_y = y - size + 1;
107                    }
108                }
109            }
110        }
111    }
112
113    Result { size, x: max_x, y: max_y, power: max_power }
114}
aoc/year2018/day11.rs

aoc/year2018/
day11.rs
