--- Day 4: Ceres Search ---

"Looks like the Chief's not here. Next!" One of The Historians pulls out a device and pushes the only button on it. After a brief flash, you recognize the interior of the Ceres monitoring station!

As the search for the Chief continues, a small Elf who lives on the station tugs on your shirt; she'd like to know if you could help her with her word search (your puzzle input). She only has to find one word: XMAS.

This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It's a little unusual, though, as you don't merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:

..X...
.SAMX.
.A..A.
XMAS.S
.X....
The actual word search will be full of letters instead. For example:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
In this word search, XMAS occurs a total of 18 times; here's the same word search again, but where letters not involved in any XMAS have been replaced with .:

....XXMAS.
.SAMXMS...
...S..A...
..A.A.MS.X
XMASAMX.MM
X.....XA.A
S.S.S.S.SS
.A.A.A.A.A
..M.M.M.MM
.X.X.XMASX
Take a look at the little Elf's word search. How many times does XMAS appear?
const fs = require('fs');

// Read the input file
const data = fs.readFileSync('input.txt', 'utf8');
const lines = data.trim().split('\n');
const grid = lines.map(line => line.trim().split(''));

const numRows = grid.length;
const numCols = grid[0].length;
const word = 'XMAS';
let count = 0;

// Directions: N, NE, E, SE, S, SW, W, NW
const directions = [
  [-1,  0], // N
  [-1,  1], // NE
  [ 0,  1], // E
  [ 1,  1], // SE
  [ 1,  0], // S
  [ 1, -1], // SW
  [ 0, -1], // W
  [-1, -1]  // NW
];

for (let row = 0; row < numRows; row++) {
  for (let col = 0; col < numCols; col++) {
    for (let [dx, dy] of directions) {
      let match = true;
      for (let k = 0; k < word.length; k++) {
        const x = row + k * dx;
        const y = col + k * dy;
        if (x < 0 || x >= numRows || y < 0 || y >= numCols || grid[x][y] !== word[k]) {
          match = false;
          break;
        }
      }
      if (match) {
        count++;
      }
    }
  }
}

console.log(`The word "XMAS" appears ${count} times in the grid.`);