question: --- 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?
solution: with open("./day_04.in") as fin:
      lines = fin.read().strip().split("\n")
  
  n = len(lines)
  m = len(lines[0])
  
  # Generate all directions
  dd = []
  for dx in range(-1, 2):
      for dy in range(-1, 2):
          if dx != 0 or dy != 0:
              dd.append((dx, dy))
  
  # dd = [(-1, -1), (-1, 0), (-1, 1),
  #       (0, -1),           (0, 1),
  #       (1, -1), (1, 0), (1, 1)]
  
  def has_xmas(i, j, d):
      dx, dy = d
      for k, x in enumerate("XMAS"):
          ii = i + k * dx
          jj = j + k * dy
          if not (0 <= ii < n and 0 <= jj < m):
              return False
          if lines[ii][jj] != x:
              return False
      return True
  
  # Count up every cell and every direction
  ans = 0
  for i in range(n):
      for j in range(m):
          for d in dd:
              ans += has_xmas(i, j, d)
  
  print(ans)
  