--- 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?
# Read input file
lines = File.read("input.txt").strip.split("\n")

n = lines.length
m = lines[0].length

# Generate all directions
dd = []
(-1..1).each do |dx|
  (-1..1).each do |dy|
    dd << [dx, dy] unless dx == 0 && dy == 0
  end
end

# Function to check if 'XMAS' is found at a given position (i, j) in a given direction (dx, dy)
def has_xmas(i, j, dx, dy, lines, n, m)
  "XMAS".each_char.with_index do |char, k|
    ii = i + k * dx
    jj = j + k * dy
    return false unless ii.between?(0, n - 1) && jj.between?(0, m - 1)
    return false if lines[ii][jj] != char
  end
  true
end

# Count up every cell and every direction
ans = 0
(0...n).each do |i|
  (0...m).each do |j|
    dd.each do |dx, dy|
      ans += 1 if has_xmas(i, j, dx, dy, lines, n, m)
    end
  end
end

puts ans