aoc day 11 2018

solution.rs

use rayon::iter::{IntoParallelIterator, ParallelIterator};
pub fn part1(serial_number: usize) -> (usize, usize) {unsafe{
    let mut cells = vec![[0isize; 300]; 300];
    for y in 1..=300 {
        let id = 11;
        *cells.get_unchecked_mut(y-1).get_unchecked_mut(0) = ((id*y+serial_number)*id/100%10) as isize - 5;
        if y != 1 {
            *cells.get_unchecked_mut(y-1).get_unchecked_mut(0) += *cells.get_unchecked_mut(y-2).get_unchecked_mut(0);
        }
    }
    for x in 1..=300 {
        let id = x+10;
        *cells.get_unchecked_mut(0).get_unchecked_mut(x-1) = ((id*1+serial_number)*id/100%10) as isize - 5;
        if x != 1 {
            *cells.get_unchecked_mut(0).get_unchecked_mut(x-1) += *cells.get_unchecked_mut(0).get_unchecked_mut(x-2);
        }
    }
    for y in 2..=300 {
        for x in 2..=300 {
            let id = x+10;
            *cells.get_unchecked_mut(y-1).get_unchecked_mut(x-1) = ((id*y+serial_number)*id/100%10) as isize - 5
                + *cells.get_unchecked_mut(y-2).get_unchecked_mut(x-1)
                + *cells.get_unchecked_mut(y-1).get_unchecked_mut(x-2)
                - *cells.get_unchecked_mut(y-2).get_unchecked_mut(x-2);
        }
    }
    let mut max_c = (0, 0);
    let mut max_sum = -9999999999;
    for y in 0..300-3 {
        for x in 0..300-3 {
            let sum = *cells.get_unchecked_mut(y+3).get_unchecked_mut(x+3)
                - *cells.get_unchecked_mut(y+3).get_unchecked_mut(x)
                - *cells.get_unchecked_mut(y).get_unchecked_mut(x+3)
                + *cells.get_unchecked_mut(y).get_unchecked_mut(x);
            if sum > max_sum { max_sum = sum; max_c = (x+2,y+2); }
        }
    }
    (max_c.0, max_c.1)
}}

pub fn part2(serial_number: usize) -> (usize, usize, usize) {unsafe{
    let mut cells_prefix_sum = vec![[0isize; 300]; 300];
    let mut max_coord = (0, 0);
    let mut max_sum = isize::min_value();
    let mut max_size = 0;
    // populate the left column
    for y in 1..=300 {
        let id = 11;
        let p = ((id*y+serial_number)*id/100%10) as isize - 5;
        *cells_prefix_sum.get_unchecked_mut(y-1).get_unchecked_mut(0) = p;
        if y != 1 {
            *cells_prefix_sum.get_unchecked_mut(y-1).get_unchecked_mut(0) += *cells_prefix_sum.get_unchecked_mut(y-2).get_unchecked_mut(0);
        }
        // we're doing the 1x1 check as we populate the prefix sum table
        if p > max_sum { max_sum = p; max_coord = (1,y); max_size = 1; }
    }
    // populate the top row
    for x in 1..=300 {
        let id = x+10;
        let p = ((id*1+serial_number)*id/100%10) as isize - 5;
        *cells_prefix_sum.get_unchecked_mut(0).get_unchecked_mut(x-1) = p;
        if x != 1 {
            *cells_prefix_sum.get_unchecked_mut(0).get_unchecked_mut(x-1) += *cells_prefix_sum.get_unchecked_mut(0).get_unchecked_mut(x-2);
        }
        // we're doing the 1x1 check as we populate the prefix sum table
        if p > max_sum { max_sum = p; max_coord = (x,1); max_size = 1; }
    }
    // populate the rest of the table
    for y in 2..=300 {
        for x in 2..=300 {
            let id = x+10;
            let p = ((id*y+serial_number)*id/100%10) as isize - 5;
            *cells_prefix_sum.get_unchecked_mut(y-1).get_unchecked_mut(x-1) = p
                + *cells_prefix_sum.get_unchecked_mut(y-2).get_unchecked_mut(x-1)
                + *cells_prefix_sum.get_unchecked_mut(y-1).get_unchecked_mut(x-2)
                - *cells_prefix_sum.get_unchecked_mut(y-2).get_unchecked_mut(x-2);
            // we're doing the 1x1 check as we populate the prefix sum table
            if p > max_sum { max_sum = p; max_coord = (x,y); max_size = 1; }
        }
    }
    // find the max sum
    let (c,s,z) = (2usize..301).into_par_iter().map(|size| {
        let mut max_coord = (0, 0);
        let mut max_sum = isize::min_value();
        let mut max_size = 0;
        for y in 0usize..300-size {
            for x in 0..300-size {
                // x and y represent the coordinate to the immediate top left of the coordinate we are
                // testing. This is why we did the 1x1 check earlier instead of now.
                let sum: isize = *cells_prefix_sum.get_unchecked(y+size).get_unchecked(x+size)
                    - *cells_prefix_sum.get_unchecked(y+size).get_unchecked(x)
                    - *cells_prefix_sum.get_unchecked(y).get_unchecked(x+size)
                    + *cells_prefix_sum.get_unchecked(y).get_unchecked(x);
                if sum > max_sum { max_sum = sum; max_coord = (x+2,y+2); max_size = size; }
            }
        }
         (max_coord, max_sum, max_size)
    }).max_by_key(|v| v.1).unwrap();
    if s > max_sum { max_sum = s; max_coord = (c.0 as usize, c.1 as usize); max_size = z; }
    (max_coord.0, max_coord.1, max_size as usize)
}}