Before we look at the Day 04 puzzle, please make sure you take a look at the problem statement before reading further. Here’s a generated image to prevent you from accidentally seeing the solution below.

Part 1

In Day 4, you are asked to find which “rolls of paper” can be removed from a grid. A roll of paper can be removed if and only if it has less than four adjacent rolls of paper among its eight surrounding cells. The goal is to return the total count of removable rolls.

For example, the following center roll has three rolls of paper around it; thus, it can be removed:

. . .
@ @ .
. @ @

Where as this one cannot:

. . @
@ @ .
. @ @

Our initial solution will use a straightforward two-pass approach. First, we calculate the sum of rolls for each triplet (current cell + left + right). The second pass iterates column-wise, marking cells for removal if they meet the specified criteria. Pre-calculating triplet sums in the first pass simplifies the second pass, as we only need to consider the current cell, the one directly above it, and the one directly below it.

Arrays and Memory

Before diving into the code, let’s consider how we’ll structure our input data. When dealing with a grid, a natural inclination is to use a 2D array and access cells with arr[i][j]. This approach is perfectly functional.

However, the in-memory storage of arrays varies significantly across programming languages:

• Contiguous: all items are stored sequentially.
• Jagged: array segments are distributed across different memory locations.

Furthermore, languages typically employ either Row-Major (row by row) or Column-Major (column by column) storage, which dictates data access patterns.

Here’s a summary (LLM generated) of the how different languages store 2d arrays:

Some notes:

• It’s interesting to note that Fortran remains a leader in true dynamically allocated multidimensional arrays, which explains why projects like MUMPS continue to be written in it.
• Python is the only language for which I included a library, given its widespread use. Of course, most languages offer similar libraries (e.g., Rust’s ndarray).
• Java is noted as not supporting static in this context. While Java has a static keyword, it doesn’t imply stack allocation for data structures. Only primitives and object references are typically stack-allocated; objects themselves (including arrays) reside on the heap.

But why is the access order and storage layout important? Because computer memory is fundamentally a single linear address space, not a grid. Your CPU is optimized to fetch data in contiguous chunks (known as cache lines), not one item at a time. When you iterate through a matrix in the same order it’s physically stored, you leverage data locality. This means the next piece of data you require is probably already present in the CPU’s cache. Conversely, accessing data in an unaligned order (e.g., jumping across rows in a column-major language) forces the CPU to repeatedly discard pre-fetched cache lines and incur the latency of retrieving data from RAM.

Therefore, if we want our arrays to be dynamically allocated, do we simply bite the bullet and use Vec<Vec<T>> in Rust? An alternative, applicable across languages lacking native contiguous dynamically allocated multidimensional arrays (quite a mouthful!), is to use a one-dimensional array. You then compute element positions manually: row * width + column for row-major storage, or column * height + row for column-major.

Back to the Solution

We’ll be using u8 since our data values don’t exceed 9. While we could further improve space efficiency by packing up to seven items into a single byte, this would offload more work onto the CPU. For simplicity, we’ll stick with u8.

Now to our solution. If we map a roll of paper to 1 and none to 0; create a row-major ordered vector for our grid. We can write our triplet summation function to take row: &[u8] (a view of a grid row) and out: &mut [u8] (a mutable view of the output buffer):

/// use the provided `out` array to avoid allocating memory for each tripplet
fn calc_triplets(row: &[u8], out: &mut [u8]) {
    let width = row.len();
    for j in 0..width {
        let mut s = row[j];
        if j > 0 {
            s += row[j - 1];
        }
        if j < width - 1 {
            s += row[j + 1];
        }
        out[j] = s;
    }
}

This structure enables our multi-pass solution (where input is the grid in row-major order):

fn sums(input: &mut [u8], width: usize) -> u64 {
    let len = input.len();
    let height = len / width;

    // Full-size buffer to store the triplets for the entire grid
    let mut row_triplets = vec![0u8; len];
    let mut removals = 0u64;

    // PASS 1: Calculate Horizontal Triplets (Self + Left + Right)
    // `chunks` simplifies range handling, thanks Rust! :)
    let in_rows = input.chunks(width);
    let out_rows = row_triplets.chunks_mut(width);

    // `zip` combines the two iterators into pairs (tuples).
    in_rows.zip(out_rows).for_each(|(row, out)| calc_triplets(row, out));


    // PASS 2: Calculate Vertical Sums & Solve
    for row_idx in 0..height {
        for column_idx in 0..width {
            let idx = row_idx * width + column_idx;

            if input[idx] == 0 {
                continue;
            }

            // Sum = (TopRow + MidRow + BotRow) - Self
            let mut s = row_triplets[idx] - input[idx];

            if row_idx > 0 {
                s += row_triplets[idx - width]; // Add TopRow
            }
            if row_idx < height - 1 {
                s += row_triplets[idx + width]; // Add BotRow
            }

            if s < 4 {
                removals += 1;
            }
        }
    }

    removals
}

Observe that in the second pass, we frequently jump to previous and next rows, which can impact performance on large datasets. One way to mitigate this is by delaying row computations until the next row is reached, employing a sliding window technique. When the loop is at row i, you compute triplets for i and then use that data to make decisions for row i-1. This effectively transforms it into a one-pass solution. I’ll leave this optimization for the reader to implement! 😄

Part 2

Part 2 of the puzzle is identical to Part 1, with one addition: after the initial cleanup of the grid, the process must be repeated until no more rolls can be removed.

This implies a straightforward external loop that continues the process until removals == 0. However, be mindful of the following:

• You cannot directly alter the input buffer while it’s being used for triplet calculations unless you’ve implemented the sliding window approach.
• Your removals should become an array of indices to remove, rather than just a counter. After the second pass, you’ll need another pass to actually flag these cells as removed.