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::*;
10use std::sync::Mutex;
11
12pub struct Result {
13    x: usize,
14    y: usize,
15    size: usize,
16    power: i32,
17}
18
19struct Shared {
20    sat: Vec<i32>,
21    mutex: Mutex<Vec<Result>>,
22}
23
24pub fn parse(input: &str) -> Vec<Result> {
25    let grid_serial_number: i32 = input.signed();
26
27    // Build Summed-area table.
28    let mut sat = vec![0; 301 * 301];
29
30    for y in 1..301 {
31        for x in 1..301 {
32            let rack_id = x + 10;
33
34            let mut power_level = rack_id * y;
35            power_level += grid_serial_number;
36            power_level *= rack_id;
37            power_level = (power_level / 100) % 10;
38            power_level -= 5;
39
40            let index = (301 * y + x) as usize;
41            sat[index] = power_level + sat[index - 1] + sat[index - 301] - sat[index - 302];
42        }
43    }
44
45    // Use as many cores as possible to parallelize the search.
46    // Smaller sizes take more time so use work stealing to keep all cores busy.
47    let items: Vec<_> = (1..301).collect();
48    let shared = Shared { sat, mutex: Mutex::new(Vec::new()) };
49    spawn_parallel_iterator(&items, |iter| worker(&shared, iter));
50    shared.mutex.into_inner().unwrap()
51}
52
53pub fn part1(input: &[Result]) -> String {
54    let Result { x, y, .. } = input.iter().find(|r| r.size == 3).unwrap();
55    format!("{x},{y}")
56}
57
58pub fn part2(input: &[Result]) -> String {
59    let Result { x, y, size, .. } = input.iter().max_by_key(|r| r.power).unwrap();
60    format!("{x},{y},{size}")
61}
62
63fn worker(shared: &Shared, iter: ParIter<'_, usize>) {
64    let result: Vec<_> = iter
65        .map(|&size| {
66            let (power, x, y) = square(&shared.sat, size);
67            Result { x, y, size, power }
68        })
69        .collect();
70
71    shared.mutex.lock().unwrap().extend(result);
72}
73
74/// Find the (x,y) coordinates and max power for a square of the specified size.
75fn square(sat: &[i32], size: usize) -> (i32, usize, usize) {
76    let mut max_power = i32::MIN;
77    let mut max_x = 0;
78    let mut max_y = 0;
79
80    for y in size..301 {
81        for x in size..301 {
82            let index = 301 * y + x;
83            let power =
84                sat[index] - sat[index - size] - sat[index - 301 * size] + sat[index - 302 * size];
85
86            if power > max_power {
87                max_power = power;
88                max_x = x - size + 1;
89                max_y = y - size + 1;
90            }
91        }
92    }
93
94    (max_power, max_x, max_y)
95}
aoc/year2018/day11.rs

aoc/year2018/
day11.rs
