Day 4: Ceres Search
Part 1
Day 4 requires us to count how many times XMAS appears within a word search. The word can appear horizontal, vertical, diagonal or backwards.
I wanted to a try a reductive approach for this task, in that I will try to eliminate cases where XMAS cannot appear to be left over with only XMAS, rather than searching for XMAS immediately.
I begin by trimming and splitting the input. This allows me to work with it as a 2D array.
const rows = input.trim().split('\n');
Next, I start my loops going over each and every cell.
for (let row = 0; row < rows.length; row++) {
for (let col = 0; col < rows[row].length; col++) {
The first check I use is to see if the current cell is X, if I am not currently at X I can skip to the next cell.
if (rows[row][col] !== 'X') continue;
I then define the directions I need to check for each of the next letters.
for (const rowDir of [-1, 0, 1]) {
for (const colDir of [-1, 0, 1]) {
This idea is that, if I am currently at X then the next cell in any direction for XMAS to be present must be M, then A, then S. If the pattern fails I immediately continue to the next check, and ultimately then try the next cell.
To this end, I also skip if the direction is zero, aka the current cell.
if (rowDir === 0 && colDir === 0) continue;
It is also important to add boundary checks, as we firstly do not want to query outside of our array and cause an error, but also if we know that the 4th letter e.g. S is outside the boundary then we can simply skip now.
if (row + (3 * rowDir) < 0 || row + (3 * rowDir) >= rows.length) continue;
if (col + (3 * colDir) < 0 || col + (3 * colDir) >= rows[row].length) continue;
Finally I do the letter checks.
if (rows[row + rowDir][col + colDir] !== 'M') continue;
if (rows[row + (rowDir * 2)][col + (colDir * 2)] !== 'A') continue;
if (rows[row + (rowDir * 3)][col + (colDir * 3)] !== 'S') continue;
After which, I can increment total, as we have found an "XMAS".
total++;
Below is the complete function.
function findXMAS(input: string) {
let total = 0;
const rows = input.trim().split('\n');
for (let row = 0; row < rows.length; row++) {
for (let col = 0; col < rows[row].length; col++) {
// if the current cell isn't X then skip immediately
if (rows[row][col] !== 'X') continue;
for (const rowDir of [-1, 0, 1]) {
for (const colDir of [-1, 0, 1]) {
// skip immediately if we are not checking anything different to the current cell
if (rowDir === 0 && colDir === 0) continue;
// boundary checks, check if we are outside the grid when fully extended
if (row + (3 * rowDir) < 0 || row + (3 * rowDir) >= rows.length) continue;
if (col + (3 * colDir) < 0 || col + (3 * colDir) >= rows[row].length) continue;
// then remove the failures to be left with the count
if (rows[row + rowDir][col + colDir] !== 'M') continue;
if (rows[row + (rowDir * 2)][col + (colDir * 2)] !== 'A') continue;
if (rows[row + (rowDir * 3)][col + (colDir * 3)] !== 'S') continue;
// at this point we must be at a valid XMAS so increment total
total++;
}
}
}
}
return total;
}
Part 2
Part 2 changes our search to be that we are now looking for X-MAS.
M.S
.A.
M.S
This is the strings of "MAS" or "SAM" in an X formation.
I begin by re-using my code foundation.
function findMAS(input: string) {
let total = 0;
const rows = input.trim().split('\n');
for (let row = 0; row < rows.length; row++) {
for (let col = 0; col < rows[row].length; col++) {
It is here I decide to take a similar approach to part 1 in that, if we start at the position of "A" each time, then the diagonal cells must either be M or S in some combination. As such, if we are not at "A" we skip to the next cell.
if (rows[row][col] !== 'A') continue;
I then also add boundary checks to ensure our current cell is not on the border of the grid, as if it is then at least one corner is missing, therefore it is invalid.
if (row === rows.length - 1 || row === 0) continue;
if (col === rows[row].length - 1 || col === 0) continue;
Finally, I use an "if" statement to check our current cell's diagonals for valid "MAS" combinations, incrementing a total when one is found.
const topLeft = rows[row - 1][col - 1];
const topRight = rows[row - 1][col + 1];
const bottomLeft = rows[row + 1][col - 1];
const bottomRight = rows[row + 1][col + 1];
if (
((topLeft === 'S' && bottomRight === 'M') || (topLeft === 'M' && bottomRight === 'S'))
&& ((topRight === 'S' && bottomLeft === 'M') || (topRight === 'M' && bottomLeft === 'S'))
) total++;
This then completed part 2. Please see the final code below.
function findMAS(input: string) {
let total = 0;
const rows = input.trim().split('\n');
for (let row = 0; row < rows.length; row++) {
for (let col = 0; col < rows[row].length; col++) {
// start at the "A"'s, the center of the MAS and search outwards
if (rows[row][col] !== 'A') continue;
// boundary check to ensure we are padded 1 cell from the border
if (row === rows.length - 1 || row === 0) continue;
if (col === rows[row].length - 1 || col === 0) continue;
// define the target cells to check
const topLeft = rows[row - 1][col - 1];
const topRight = rows[row - 1][col + 1];
const bottomLeft = rows[row + 1][col - 1];
const bottomRight = rows[row + 1][col + 1];
// check to see if valid MAS combinations are found and increment
if (
((topLeft === 'S' && bottomRight === 'M') || (topLeft === 'M' && bottomRight === 'S'))
&& ((topRight === 'S' && bottomLeft === 'M') || (topRight === 'M' && bottomLeft === 'S'))
) total++;
}
}
return total;
}