rotate_grid_90 = (grid) => {
// take first row, map across with indices and reverse the column order
return grid[0].map( (_, i) => grid.map( row => row[i] ).reverse() )
}2024 Day 4: Ceres Search
Advent of Code
Advent of Code
OJS
Part 1
Alright, now we are starting to get a little trickier – today we are doing a word search.
In the past, I have started by just brute forcing a grid traversal, checking all the neighbors as I go. However, I typically get burned by it, as part 2 ends up being more expensive of an operation than part 1. So, this time, I resolved to fins another method, and I landed on rotations!
Instead of checking every direction from each letter, I check the whole grid as is (forward and back), then rotate and repeat – let’s begin:
In the above, this is the simplest of the rotations – we are taking each row and translating it into a column, and vice versa.
Since we are checking forward and backward, it doesn’t matter too much about which direction we spin the 2D array. An issue I had for a while was that I was missing the reverse() call, which led to me reflecting the 2D array across the diagonal instead of rotating. I’m sure that there is a D3 method for some of this (maybe Arquero too?), but I wanted to do it from scratch.
rotate_grid_45 = (grid) => {
// col, row (x, y)
const dims = [ grid[0].length, grid.length ]
// build array of indices of all values in the grids
const pos = Array.from(
new Set( // unique
Array(dims[0]).fill(0).map((_, i) => i)
.concat(Array(dims[1]).fill(0).map((_, i) => (dims[0]-1)+(dims[0]*i)))
// create array and fill with values (indices)
)
) // [0, 1, 2, 3, 4, 5, 6, 7, 8]
// create separate length calculations of pyramid
// based on even odd split
const lengths = pos.length % 2 === 0 ?
// even
new Array(pos.length/2).fill(0).map((_, i) => i)
.concat(new Array(pos.length/2)
.fill(0).map((_, i) => i).reverse()) :
// odd
new Array(Math.floor(pos.length/2) + 1).fill(0).map((_, i) => i)
.concat(new Array(Math.floor(pos.length/2))
.fill(0).map((_, i) => i).reverse())
// [1, 2, 3, 2, 1]
// create index map based on diffs from translation
const all_positions = lengths.map((d, i) => {
return [pos.slice()[i]]
.concat(
new Array(d)
.fill(0)
.map( (_, i) => (i + 1)*(dims[0]-1) )
).reduce(
(acc, nxt, i) => {
return i === 0
? [nxt]
: acc.concat(acc[0] + nxt)
},
[]
)
})
// [[0] // 1 length
// [1, 3] // 2
// [2, 4, 6] // 3
// [5, 7] // 2
// [8]] // 1
const grid_vals = grid.reduce((acc, nxt) => acc.concat(nxt))
return all_positions.map(row => row.map(col => grid_vals[col]))
}Now this function is to rotate 45 degrees to check the diagonals. This ends up being far more complex than a 90 degree rotation because the resultant arrays aren’t of equal length.
First, in pos we need to create an array that has all the indices of the input 2D array. This was easier mentally to arrange, then just substitute at the end, though I’m sure this step could now be refactored if desired. Next, with lengths I wanted to calculate the lengths of each array in the pyramid arrangement of arrays after the rotation. This will allow a mapping function later to iterate through and fill with the needed values.
Finally, the last step of our prepatory steps is to wrap all the indices into the correct positions (thus all_positions). Of note, this includes a calculation to increase the step of each index by the dimensions of the original 2D array – since the example is 3x3, the outer indices are [0, 1, 2, 5, 8], which wraps the first row and last column. With how we are rotating, those become the first indices in each resulting array, as they lead all the diagonals of our 45 degree rotation.
This means that each step is width of array - 1 = 2 in our example. If you picture it, you can concatenate all the arrays into one long number line, and you want 1 less than a perfect row in order to create a diagonal. Lastly, we just map across the resulting indices and substitute our actual values back in.
check_rows = (grid) => {
// check matches for XMAS
const forward = grid
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/XMAS/g)].length, 0 )
// check matches for SAMX -- could also reverse() string I guess
const backward = grid
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/SAMX/g)].length, 0 )
return forward + backward
}
check_cols = (grid) => {
const col_grid = rotate_grid_90(grid)
const up = col_grid
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/XMAS/g)].length, 0 )
const down = col_grid
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/SAMX/g)].length, 0 )
return up + down
}
check_diag = (grid) => {
const up_diag = rotate_grid_45(grid)
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/XMAS/g)].length, 0 )
const down_diag = rotate_grid_45(grid)
.reduce((acc, row) => acc + [...row.join("")
.matchAll(/SAMX/g)].length, 0 )
return up_diag + down_diag
}Finally, all we have to do is create helper functions for each direction – horizontal, vertical (rotated horizontal), and diagonal (rotated 45 horizontal). Each of them checks for both XMAS and SAMX, that way we can minimize rotations.
{
const grid = raw.split('\n').map(d => d.split(""))
return check_rows(grid) + check_cols(grid) +
check_diag(grid) + check_diag(rotate_grid_90(grid))
}Once the helpers are made, we just have to sum them! Note that we have two 45 degree rotations – one is to get the upper-left to lower-right diagonal, and the other is the upper-right to lower-left diagonal. Since we already have a 90 degree rotation, we can get the perpendicular diagonal by combining a 90 + 45 rotation, giving us our 0 degree, 90 degree, 45 degree, and 135 degree totals!
⭐
Part 2
Unfortunately, I out-thought myself. Part 2 was far simpler than part 1 in this case, so I went back and created a new process to walk each cell (excluding the border):
walk_grid_no_border = (grid, fn) => {
// row, col
const inner_dims = [grid.length - 2, grid[0].length - 2]
// copy grid
const output_grid = grid.slice()
// map across every inner cell (not borders)
for (let i = 1; i <= inner_dims[0]; i++) {
for (let k = 1; k <= inner_dims[1]; k++) {
// call function on each cell, store result in new grid
output_grid[i][k] = fn(grid.slice(), i, k)
}
}
return output_grid
}As mentioned, this walks each cell, and performs a lambda function on it, passed through as an argument. This way, if I need to walk a grid in the future, I should be able to reuse this one!
check_cell = (grid, row, col) => {
// get cell
const cell = grid[row][col]
// A will always be the intersection
if (cell !== "A") return cell
// look up diagonal characters
const diags = [
[ grid[row-1][col-1], grid[row+1][col+1] ],
[ grid[row+1][col-1], grid[row-1][col+1] ]
]
// make sure each diagonal has an 'M' and an 'S'
return diags.map(d => d.includes("M") && d.includes("S")).every(elem => elem)
}Again, fairly straightforward, for each cell, I want to check each adjacent diagonal to see if they qualify, using A as the pivot point. I also had to pass a shallow copy of the the grid in so that when I replace a cell value with the boolen answer, it won’t impact further checks in the next row(s).
{
const grid = raw.split('\n').map(d => d.split(""))
return walk_grid_no_border(grid, check_cell)
.flatMap(d => d.filter(elem => elem == 1))
.length
}Once we have those two functions, it’s just a matter of mapping them across the input! We should be fairly well set up for future grid questions where we have to walk the input – and any rotations!
⭐
-CH