import Data.Array.Unboxed (UArray)
import Data.Array.Unboxed qualified as A
import Data.Bifunctor

readInput :: String -> UArray (Int, Int) Char
readInput s =
  let rows = lines s
      n = length rows
   in A.listArray ((1, 1), (n, n)) $ concat rows

s1 `eq` s2 = s1 == s2 || s1 == reverse s2

part1 arr = length $ filter isXmas $ concatMap lines $ A.indices arr
  where
    isXmas ps = all (A.inRange $ A.bounds arr) ps && map (arr A.!) ps `eq` "XMAS"
    lines p = [take 4 $ iterate (bimap (+ di) (+ dj)) p | (di, dj) <- [(1, 0), (0, 1), (1, 1), (1, -1)]]

part2 arr = length $ filter isXmas innerPoints
  where
    innerPoints =
      let ((i1, j1), (i2, j2)) = A.bounds arr
       in [(i, j) | i <- [i1 + 1 .. i2 - 1], j <- [j1 + 1 .. j2 - 1]]
    isXmas p = up p `eq` "MAS" && down p `eq` "MAS"
    up (i, j) = map (arr A.!) [(i + 1, j - 1), (i, j), (i - 1, j + 1)]
    down (i, j) = map (arr A.!) [(i - 1, j - 1), (i, j), (i + 1, j + 1)]

main = do
  input <- readInput <$> readFile "input04"
  print $ part1 input
  print $ part2 input

  

 haskell

    

import Data.List qualified as List

collectDiagonal :: [String] -> Int -> Int -> String
collectDiagonal c y x
        | length c > y && length (c !! y) > x = c !! y !! x : collectDiagonal c (y+1) (x+1)
        | otherwise = []

part1 c = do
        let forwardXMAS  = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ c
        let backwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ c
        let downwardXMAS  = map (length . filter (List.isPrefixOf "XMAS") . List.tails ) . List.transpose $ c
        let upwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse ) . List.transpose $ c
        let leftSideDiagonals = map (\ y -> collectDiagonal c y 0) [0..length c]
        let leftTopDiagonals = map (\ x -> collectDiagonal c 0 x) [1..(length . List.head $ c)]
        let leftDiagonals = leftSideDiagonals ++ leftTopDiagonals
        let rightSideDiagonals = map (\ y -> collectDiagonal (map List.reverse c) y 0) [0..length c]
        let rightTopDiagonals = map (\ x -> collectDiagonal (map List.reverse c) 0 x) [1..(length . List.head $ c)]
        let rightDiagonals = rightSideDiagonals ++ rightTopDiagonals
        let diagonals = leftDiagonals ++ rightDiagonals

        let diagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ diagonals
        let reverseDiagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ diagonals

        print . sum $ [sum forwardXMAS, sum backwardXMAS, sum downwardXMAS, sum upwardXMAS, sum diagonalXMAS, sum reverseDiagonalXMAS]
        return ()

getBlock h w c y x = map (take w . drop x) . take h . drop y $ c

isXBlock b = do
        let diagonal1 = collectDiagonal b 0 0
        let diagonal2 = collectDiagonal (map List.reverse b) 0 0

        diagonal1 `elem` ["SAM", "MAS"] && diagonal2 `elem` ["SAM", "MAS"]

part2 c = do
        
        let lineBlocks = List.map (getBlock 3 3 c) [0..length c - 1]
        let groupedBlocks = List.map (flip List.map [0..(length . head $ c) - 1]) lineBlocks

        print . sum . map (length . filter isXBlock) $ groupedBlocks

        return ()

main = do
        c <- lines <$> getContents

        part1 c
        part2 c

        return ()

  

    
data_file_name =: '4.data'

NB. cutopen yields boxed lines, so unbox them and ravel items to make a letter matrix
grid =: ,. > cutopen fread data_file_name
NB. pad the grid on every side with #'XMAS' - 1 spaces
hpadded_grid =: (('   ' & ,) @: (, & '   '))"1 grid
padded_grid =: (3 1 $ ' ') , hpadded_grid , (3 1 $ ' ')
NB. traversal vectors
directions =: 8 2 $ 1 0 1 1 0 1 _1 1 _1 0 _1 _1 0 _1 1 _1
NB. rpos cpos matches rdir cdir if the string starting at rpos cpos in
NB. direction rdir cdir is the string we want
matches =: 4 : 0
*/ ,'XMAS' -: padded_grid {~ <"1 x +"1 y *"1 0 i. 4
)"1
positions =: (3 + i. 0 { $ grid) ,"0/ (3 + i. 1 { $ grid)
result1 =: +/, positions matches/ directions

NB. pairs of traversal vectors
x_directions =: 4 2 2 $ 1 1 _1 1 1 1 1 _1 _1 _1 _1 1 _1 _1 1 _1
NB. rpos cpos x_matches 2 2 $ rdir1 cdir1 rdir2 cdir2 if there is an 'A' at
NB. rpos cpos and the string in each of dir1 and dir2 centered at rpos cpos
NB. is the string we want
x_matches =: 4 : 0
NB. (2 2 $ rdir1 cdir1 rdir2 cdir2) *"1 0/ (_1 + i.3) yields a matrix
NB. 2 3 $ (_1 * dir1) , (0 * dir1) , (1 * dir1) followed by the same for dir2
*/ ,'MAS' -:"1 padded_grid {~ <"1 x +"1 y *"1 0/ _1 + i. 3
)"1 2
result2 =: +/, positions x_matches/ x_directions

  

 nim

    
proc solve(input: string): AOCSolution[int, int] =
  var lines = input.splitLines()

  block p1:
    # horiz
    for line in lines:
      for i in 0..line.high-3:
        if line[i..i+3] in ["XMAS", "SAMX"]:
          inc result.part1

    for y in 0..lines.high-3:
      #vert
      for x in 0..lines[0].high:
        let word = collect(for y in y..y+3: lines[y][x])
        if word in [@"XMAS", @"SAMX"]:
          inc result.part1

      #diag \
      for x in 0..lines[0].high-3:
        let word = collect(for d in 0..3: lines[y+d][x+d])
        if word in [@"XMAS", @"SAMX"]:
          inc result.part1

      #diag /
      for x in 3..lines[0].high:
        let word = collect(for d in 0..3: lines[y+d][x-d])
        if word in [@"XMAS", @"SAMX"]:
          inc result.part1

  block p2:
    for y in 0..lines.high-2:
      for x in 0..lines[0].high-2:
        let diagNW = collect(for d in 0..2: lines[y+d][x+d])
        let diagNE = collect(for d in 0..2: lines[y+d][x+2-d])
        if diagNW in [@"MAS", @"SAM"] and diagNE in [@"MAS", @"SAM"]:
          inc result.part2


  

 haskell

    
import Control.Arrow
import Data.Array.Unboxed
import Data.List

type Pos = (Int, Int)
type Board = Array Pos Char
data Dir = N | NE | E | SE | S | SW | W | NW

target = "XMAS"

parse s = listArray ((1, 1), (n, m)) [l !! i !! j | i <- [0 .. n - 1], j <- [0 .. m - 1]]
  where
    l = lines s
    (n, m) = (length $ head l, length l)

move N = first pred
move S = first succ
move E = second pred
move W = second succ
move NW = move N . move W
move SW = move S . move W
move NE = move N . move E
move SE = move S . move E

check :: Board -> Pos -> Int -> Dir -> Bool
check b p i d =
    i >= length target
        || ( inRange (bounds b) p
                && (b ! p) == (target !! i)
                && check b (move d p) (succ i) d
           )

checkAllDirs :: Board -> Pos -> Int
checkAllDirs b p = length . filter (check b p 0) $ [N, NE, E, SE, S, SW, W, NW]

check2 :: Board -> Pos -> Bool
check2 b p =
    all (inRange (bounds b)) moves && ((b ! p) == 'A') && ("SSMM" `elem` rotations)
  where
    rotations = rots $ (b !) <$> moves
    moves = flip move p <$> [NE, SE, SW, NW]

    rots xs = init $ zipWith (++) (tails xs) (inits xs)

part1 b = sum $ checkAllDirs b <$> indices b
part2 b = length . filter (check2 b) $ indices b

main = getContents >>= print . (part1 &&& part2) . parse

  

 uiua

    
Row    ← ⌕ "XMAS"
RevRow ← ⌕"SAMX"
Sum    ← /+/+
Count  ← +∩Sum⊃Row RevRow

PartOne ← (
  &rs ∞ &fo "input-4.txt"
  ⊜∘≠@\n.
  ⊙+⟜∩Count⟜⍉ # horizontal and vertical search
  ⟜(/+⧈(Count⍉≡⬚@ ↻⇡⧻.)4)
  /+⧈(Count⍉≡⬚@ ↻¯⇡⧻.)4
  ++
)

Mask ← °⊚×2⇡5
# Create variations of X-MAS
Vars ← (
  ["M S"
   " A "
   "M S"]
  ≡♭[∩⟜⍉]≡⇌.
  Mask
  ⊏0⊞▽¤
)

PartTwo ← (
  &rs ∞ &fo "input-4.txt"
  ⊜∘≠@\n.
  ⧈(/+♭⊞≍⊙¤Vars▽Mask♭)3_3
  Sum
)

&p "Day 4:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

  

    
public class Day04 : Solver
{
  private int width, height;
  private char[,] data;

  public void Presolve(string input) {
    var lines = input.Trim().Split("\n").ToList();
    height = lines.Count;
    width = lines[0].Length;
    data = new char[height, width];
    for (int i = 0; i < height; i++) {
      for (int j = 0; j < width; j++) {
        data[i, j] = lines[i][j];
      }
    }
  }

  private static readonly string word = "XMAS";

  public string SolveFirst()
  {
    int counter = 0;
    for (int start_i = 0; start_i < height; start_i++) {
      for (int start_j = 0; start_j < width; start_j++) {
        if (data[start_i, start_j] != word[0]) continue;
        for (int di = -1; di <= 1; di++) {
          for (int dj = -1; dj <= 1; dj++) {
            if (di == 0 && dj == 0) continue;
            int end_i = start_i + di * (word.Length - 1);
            int end_j = start_j + dj * (word.Length - 1);
            if (end_i < 0 || end_j < 0 || end_i >= height || end_j >= width) continue;
            for (int k = 1; k < word.Length; k++) {
              if (data[start_i + di * k, start_j + dj * k] != word[k]) break;
              if (k == word.Length - 1) counter++;
            }
          }
        }
      }
    }
    return counter.ToString();
  }

  public string SolveSecond()
  {
    int counter = 0;
    for (int start_i = 1; start_i < height - 1; start_i++) {
      for (int start_j = 1; start_j < width - 1; start_j++) {
        if (data[start_i, start_j] != 'A') continue;
        int even_mas_starts = 0;
        for (int di = -1; di <= 1; di++) {
          for (int dj = -1; dj <= 1; dj++) {
            if (di == 0 && dj == 0) continue;
            if ((di + dj) % 2 != 0) continue;
            if (data[start_i + di, start_j + dj] != 'M') continue;
            if (data[start_i - di, start_j - dj] != 'S') continue;
            even_mas_starts++;
          }
        }
        if (even_mas_starts == 2) counter++;
      }
    }
    return counter.ToString();
  }
}

  

 rust

    
use std::{fs, str::FromStr};

use color_eyre::eyre::{Report, Result};

#[derive(Debug, Copy, Clone)]
enum Direction {
    N,
    NE,
    E,
    SE,
    S,
    SW,
    W,
    NW,
}

impl Direction {
    fn all() -> &'static [Direction] {
        &[
            Direction::N,
            Direction::NE,
            Direction::E,
            Direction::SE,
            Direction::S,
            Direction::SW,
            Direction::W,
            Direction::NW,
        ]
    }
}

#[derive(Debug, PartialEq, Eq)]
struct WordSearch {
    grid: Vec<char>,
    width: usize,
    height: usize,
}

impl FromStr for WordSearch {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let grid: Vec<_> = s.chars().filter(|&ch| ch != '\n').collect();
        let width = s
            .chars()
            .position(|ch| ch == '\n')
            .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?;
        let height = grid.len() / width;
        Ok(Self {
            grid,
            width,
            height,
        })
    }
}

impl WordSearch {
    fn neighbour(&self, i: usize, dir: Direction) -> Option<usize> {
        let width = self.width;
        let length = self.grid.len();
        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            NE if i >= width && i % width != width - 1 => Some(i - width + 1),
            E if i % width != width - 1 => Some(i + 1),
            SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1),
            S if i + width < length => Some(i + width),
            SW if i + width - 1 < length && i % width != 0 => Some(i + width - 1),
            W if i % width != 0 => Some(i - 1),
            NW if i >= width && i % width != 0 => Some(i - width - 1),
            _ => None,
        }
    }

    fn word_count(&self, word: &str) -> Result<usize> {
        let mut found = 0;
        for i in 0..self.grid.len() {
            for dir in Direction::all() {
                if self.word_present(word, i, *dir) {
                    found += 1;
                }
            }
        }
        Ok(found)
    }

    fn x_count(&self) -> Result<usize> {
        let mut found = 0;
        for i in 0..self.grid.len() {
            if self.x_present(i) {
                found += 1;
            }
        }
        Ok(found)
    }

    fn word_present(&self, word: &str, location: usize, dir: Direction) -> bool {
        let mut next = Some(location);
        for ch in word.chars() {
            let i = if let Some(i) = next {
                i
            } else {
                // Off the edge
                return false;
            };

            if self.grid[i] != ch {
                return false;
            }
            next = self.neighbour(i, dir);
        }
        true
    }

    fn x_present(&self, location: usize) -> bool {
        if self.grid.get(location) != Some(&'A') {
            return false;
        }
        let diags = [
            (Direction::NE, Direction::SW),
            (Direction::NW, Direction::SE),
        ];
        diags.iter().all(|(dir_a, dir_b)| {
            let Some(a_idx) = self.neighbour(location, *dir_a) else {
                return false;
            };
            let Some(b_idx) = self.neighbour(location, *dir_b) else {
                return false;
            };
            let a = self.grid[a_idx];
            let b = self.grid[b_idx];
            (a == 'M' && b == 'S') || (b == 'M' && a == 'S')
        })
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let grid = WordSearch::from_str(&input)?;
    grid.word_count("XMAS")
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let grid = WordSearch::from_str(&input)?;
    grid.x_count()
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d04/input.txt")?);
    println!("Part 2: {}", part2("d04/input.txt")?);
    Ok(())
}

  

    
fun part1(input: String): Int {
    return countWordOccurrences(input.lines())
}

fun part2(input: String): Int {
    val grid = input.lines().map(String::toList)
    var count = 0
    for (row in 1..grid.size - 2) {
        for (col in 1..grid[row].size - 2) {
            if (grid[row][col] == 'A') {
                count += countCrossMatch(grid, row, col)
            }
        }
    }
    return count
}

private fun countCrossMatch(grid: List<List<Char>>, row: Int, col: Int): Int {
    val surroundingCorners = listOf(
        grid[row - 1][col - 1], // upper left
        grid[row - 1][col + 1], // upper right
        grid[row + 1][col - 1], // lower left
        grid[row + 1][col + 1], // lower right
    )
    // no matches:
    //   M S   S M
    //    A     A
    //   S M   M S
    return if (surroundingCorners.count { it == 'M' } == 2
        && surroundingCorners.count { it == 'S' } == 2
        && surroundingCorners[0] != surroundingCorners[3]
    ) 1 else 0
}

private fun countWordOccurrences(matrix: List<String>): Int {
    val rows = matrix.size
    val cols = if (rows > 0) matrix[0].length else 0
    val directions = listOf(
        Pair(0, 1),   // Horizontal right
        Pair(1, 0),   // Vertical down
        Pair(1, 1),   // Diagonal down-right
        Pair(1, -1),  // Diagonal down-left
        Pair(0, -1),  // Horizontal left
        Pair(-1, 0),  // Vertical up
        Pair(-1, -1), // Diagonal up-left
        Pair(-1, 1)   // Diagonal up-right
    )

    fun isWordAt(row: Int, col: Int, word: String, direction: Pair<Int, Int>): Boolean {
        val (dx, dy) = direction
        for (i in word.indices) {
            val x = row + i * dx
            val y = col + i * dy
            if (x !in 0 until rows || y !in 0 until cols || matrix[x][y] != word[i]) {
                return false
            }
        }
        return true
    }

    var count = 0

    for (row in 0 until rows) {
        for (col in 0 until cols) {
            for (direction in directions) {
                if (isWordAt(row, col, "XMAS", direction)) {
                    count++
                }
            }
        }
    }

    return count
}

  

    
namespace Day04;

static class Program
{
    public record struct Point(int Row, int Col);

    static void Main(string[] args)
    {
        var sample = File.ReadAllLines("sample.txt");
        var data = File.ReadAllLines("data.txt");

        Console.WriteLine($"Part 1 (sample): {SolvePart1(sample)}");
        Console.WriteLine($"Part 1 (data): {SolvePart1(data)}");

        Console.WriteLine($"Part 2 (sample): {SolvePart2(sample)}");
        Console.WriteLine($"Part 2 (data): {SolvePart2(data)}");
    }

    private static readonly string Search = "XMAS";

    private static readonly Func<Point, Point>[] DirectionalMoves =
    {
        p => new Point(p.Row + 1, p.Col),
        p => new Point(p.Row + 1, p.Col + 1),
        p => new Point(p.Row, p.Col + 1),
        p => new Point(p.Row - 1, p.Col + 1),
        p => new Point(p.Row - 1, p.Col),
        p => new Point(p.Row - 1, p.Col - 1),
        p => new Point(p.Row, p.Col - 1),
        p => new Point(p.Row + 1, p.Col - 1),
    };

    private static readonly Func<Point, Point>[] ForwardSlashMoves =
    {
        p => new Point(p.Row - 1, p.Col - 1),
        p => new Point(p.Row + 1, p.Col + 1),
    };
    
    private static readonly Func<Point, Point>[] BackSlashMoves =
    {
        p => new Point(p.Row + 1, p.Col - 1),
        p => new Point(p.Row - 1, p.Col + 1),
    };

    static long SolvePart1(string[] data)
    {
        return Enumerable
            .Range(0, data.Length)
            .SelectMany(row => Enumerable.Range(0, data[row].Length)
                .Select(col => new Point(row, col)))
            .Where(p => IsMatch(data, p, Search[0]))
            .Sum(p => DirectionalMoves
                .Count(move => DeepMatch(data, move(p), move, Search, 1)));
    }

    static long SolvePart2(string[] data)
    {
        return Enumerable
            .Range(0, data.Length)
            .SelectMany(row => Enumerable.Range(0, data[row].Length)
                .Select(col => new Point(row, col)))
            .Where(p => IsMatch(data, p, 'A'))
            .Count(p => CheckDiagonalMoves(data, p, ForwardSlashMoves)
                        && CheckDiagonalMoves(data, p, BackSlashMoves));
    }

    static bool CheckDiagonalMoves(string[] data, Point p, Func<Point, Point>[] moves)
        => (IsMatch(data, moves[0](p), 'S') && IsMatch(data, moves[1](p), 'M'))
           || (IsMatch(data, moves[0](p), 'M') && IsMatch(data, moves[1](p), 'S'));

    static bool DeepMatch(string[] data, Point p, Func<Point, Point> move, string search, int searchIndex) =>
        (searchIndex >= search.Length) ? true :
        (!IsMatch(data, p, search[searchIndex])) ? false :
        DeepMatch(data, move(p), move, search, searchIndex + 1);

    static bool IsMatch(string[] data, Point p, char searchChar)
        => IsInBounds(data, p) && (data[p.Row][p.Col] == searchChar);

    static bool IsInBounds(string[] data, Point p) =>
        (p.Row >= 0) && (p.Col >= 0) && (p.Row < data.Length) && (p.Col < data[0].Length);
}

  

 python

    
with open('input') as data:
    lines = [l.strip() for l in data.readlines()]
# Remove empty line
class Result():
    def __init__(self):
        self.count = 0


def analyze_lines(lines: list[str]):
    ans.count += get_rights(lines)
    ans.count += get_ups(lines)
    ans.count += get_downs(lines)
    ans.count += get_down_rights(lines)
    ans.count += get_down_lefts(lines)
    ans.count += get_up_lefts(lines)
    ans.count += get_up_rights(lines)
    for line in lines:
        ans.count += get_lefts(line)




def get_ups(lines: list[str]) -> int:
    up_count = 0
    for i_l, line in enumerate(lines):
        result = ""
        if i_l < 3:
            continue
        for i_c, char in enumerate(line):
            if char == "X":
                result = char
                result += "".join([lines[i_l - n][i_c] for n in range(1, 4)])
                if result == "XMAS":
                    up_count += 1
                else:
                    result = ""
    return up_count


def get_downs(lines: list[str]) -> int:
    down_count = 0
    for i_l, l in enumerate(lines):
        result = ""
        for i_c, c in enumerate(l):
            if c == "X":
                result += c
                try:
                    result += "".join([lines[i_l + n][i_c] for n in range(1, 4)])
                except IndexError:
                    result = ""
                    continue
                finally:
                    if result == "XMAS":
                        down_count += 1
                    result = ""
    return down_count


        
def get_lefts(line: str) -> int:
    left_count = 0
    for i, char in enumerate(line):
        if i < 3:
            continue
        elif char == "X" and line[i-1] == "M" and line[i-2] == "A" and line[i-3] == "S":
            left_count += 1
    return left_count


def get_rights(lines: list[str]) -> int:
    right_counts = 0
    for l in lines:
        right_counts += l.count("XMAS")
    return right_counts

def get_down_rights(lines: list[str]) -> int:
    down_right_count = 0
    for i_l, l in enumerate(lines):
        result = ""
        for i_c, c in enumerate(l):
            if c == "X":
                result += c
                try:
                    result += "".join(
                            [lines[i_l + n][i_c + n] for n in range(1,4)]
                            )
                except IndexError:
                    result = ""
                    continue
                finally:
                    if result == "XMAS":
                        down_right_count += 1
                    result = ""
    return down_right_count

def get_down_lefts(lines: list[str]) -> int:
    down_left_count = 0
    for i_l, l in enumerate(lines):
        result = ""
        for i_c, c in enumerate(l):
            if i_c < 3:
                continue
            if c == "X":
                result += c
                try:
                    result += "".join(
                            [lines[i_l + n][i_c - n] for n in range(1,4)]
                            )
                except IndexError:
                    result = ""
                    continue
                finally:
                    if result == "XMAS":
                        down_left_count += 1
                    result = ""
    return down_left_count

def get_up_rights(lines: list[str]) -> int:
    up_right_count = 0
    for i_l, l in enumerate(lines):
        result = ""
        if i_l < 3:
            continue
        for i_c, c in enumerate(l):
            if c == "X":
                result += c
                try:
                    result += "".join(
                            [lines[i_l - n][i_c + n] for n in range(1,4)]
                            )
                except IndexError:
                    result = ""
                    continue
                finally:
                    if result == "XMAS":
                        up_right_count += 1
                    result = ""
    return up_right_count


def get_up_lefts(lines: list[str]) -> int:
    up_left_count = 0
    for i_l, l in enumerate(lines):
        result = ""
        if i_l < 3:
            continue
        for i_c, c in enumerate(l):
            if i_c < 3:
                continue
            if c == "X":
                result = c
                try:
                    result += "".join(
                            [lines[i_l - n][i_c - n] for n in range(1,4)]
                            )
                except IndexError as e:
                    result = ""
                    continue
                finally:
                    if result == "XMAS":
                        up_left_count += 1
                    result = ""
    return up_left_count

ans = Result()
analyze_lines(lines)
print(ans.count)

  

 python

    
with open('input') as data:
    lines = list(filter(lambda x: x != '', [l.strip() for l in data.readlines()]))
    
xmases = 0
for i in range(1, len(lines)):
    for j in range(1, len(lines[i])):
        if lines[i][j] == "A":
            try:
                up_back = lines[i-1][j-1]
                down_over = lines[i+1][j+1]
                up_over = lines[i-1][j+1]
                down_back = lines[i+1][j-1]
            except IndexError:
                continue
            else:
                if {up_back, down_over} == set("MS") and {up_over, down_back} == set("MS"):
                    xmases += 1

print(xmases)

  

 smalltalk

    
day4p1: input
    | lines sum w h|
    
    sum := ('XMAS' asRegex matchesIn: input) size. "forward"
    sum := sum + ('SAMX' asRegex matchesIn: input) size. "backwards sep cause overlapping"
    
    lines := input lines.
    h := lines size.
    w := (lines at: 1) size.
    
    1 to: h-3 do: [ :p1 |
        1 to: w do: [ :p2 |
            sum := sum + (self d4diag: lines p1: p1 p2: p2 dir: -1).
            sum := sum + (self d4diag: lines p1: p1 p2: p2 dir: 0).
            sum := sum + (self d4diag: lines p1: p1 p2: p2 dir: 1).    
        ]
    ].
    
    ^ sum.


  

 smalltalk

    
d4diag: input p1: p1 p2: p2 dir: dir
    | reverse xm ii |
    
    xm := 'XMAS'.
    
    reverse := ((input at: p1) at: p2) = $S.
    
    0 to: 3 do: [ :i |
        ii := reverse ifTrue: [ 4 - i ] ifFalse: [ i + 1 ].
                                                    "if out of bounds, obv not possible"
        ((xm at: ii) = ((input at: p1 + i) at: i * dir + p2 ifAbsent: [^ 0])) ifFalse: [^ 0]
    ].

    ^ 1.


  

 smalltalk

    
day4p2: input
    | lines sum w h pos |
    "Find all diag mas, then check of 1 . -1 (we can look back on every -1"
    
    sum := 0.
    lines := input lines.
    h := lines size.
    w := (lines at: 1) size.
    
    1 to: h-2 do: [ :p1 |
        pos := Array new: w withAll: false.
        1 to: w do: [ :p2 |
            (self d42: lines p1: p1 p2: p2 dir: -1)
                ifTrue: [
                    sum := sum + ((pos at: p2-2) ifTrue:[1] ifFalse:[0]).
                ].
            
            (self d42: lines p1: p1 p2: p2 dir: 1) ifTrue: [pos at: p2 put: true].
        ]
    ].
    
    ^ sum.


  

 smalltalk

    
d42: input p1: p1 p2: p2 dir: dir
    | reverse xm ii |
    
    xm := 'MAS'.
    
    reverse := ((input at: p1) at: p2) = $S.
    
    0 to: 2 do: [ :i |
        ii := reverse ifTrue: [ 3 - i ] ifFalse: [ i + 1 ].
                                                    "if out of bounds, obv not possible"
        ((xm at: ii) = ((input at: p1 + i) at: i * dir + p2 ifAbsent: [^ false])) ifFalse: [^ false]
    ].

    ^ true.

  

    
defmodule AdventOfCode.Solution.Year2024.Day04 do
  use AdventOfCode.Solution.SharedParse

  defmodule Map do
    defstruct [:chars, :width, :height]
  end

  @impl true
  def parse(input) do
    chars = String.split(input, "\n", trim: true) |> Enum.map(&String.codepoints/1)
    %Map{chars: chars, width: length(Enum.at(chars, 0)), height: length(chars)}
  end

  def at(%Map{} = map, x, y) do
    cond do
      x < 0 or x >= map.width or y < 0 or y >= map.height -> ""
      true -> map.chars |> Enum.at(y, []) |> Enum.at(x, "")
    end
  end

  def part1(map) do
    dirs = for dx <- -1..1, dy <- -1..1, {dx, dy} != {0, 0}, do: {dx, dy}
    xmas = String.codepoints("XMAS") |> Enum.with_index() |> Enum.drop(1)

    for x <- 0..(map.width - 1),
        y <- 0..(map.height - 1),
        "X" == at(map, x, y),
        {dx, dy} <- dirs,
        xmas
        |> Enum.all?(fn {c, n} -> at(map, x + dx * n, y + dy * n) == c end),
        reduce: 0 do
      t -> t + 1
    end
  end

  def part2(map) do
    for x <- 0..(map.width - 1),
        y <- 0..(map.height - 1),
        "A" == at(map, x, y),
        (at(map, x - 1, y - 1) <> at(map, x + 1, y + 1)) in ["MS", "SM"],
        (at(map, x - 1, y + 1) <> at(map, x + 1, y - 1)) in ["MS", "SM"],
        reduce: 0 do
      t -> t + 1
    end
  end
end

  

 zig

    
const std = @import("std");
const List = std.ArrayList;

const tokenizeScalar = std.mem.tokenizeScalar;
const parseInt = std.fmt.parseInt;
const print = std.debug.print;
const eql = std.mem.eql;

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const alloc = gpa.allocator();

const Point = struct {
    x: isize,
    y: isize,
    fn add(self: *const Point, point: *const Point) Point {
        return Point{ .x = self.x + point.x, .y = self.y + point.y };
    }
};

// note: i have no idea how to use this or if it's even possible
// const DirectionType = enum(u8) { Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight };
// const Direction = union(DirectionType) {
//     up: Point = .{ .x = 0, .y = 0 },
// };

const AllDirections = [_]Point{
    .{ .x = 0, .y = -1 }, // up
    .{ .x = 0, .y = 1 }, // down
    .{ .x = -1, .y = 0 }, // left
    .{ .x = 1, .y = 0 }, // right
    .{ .x = -1, .y = -1 }, // up left
    .{ .x = 1, .y = -1 }, // up right
    .{ .x = -1, .y = 1 }, // down left
    .{ .x = 1, .y = 1 }, // down right
};

const Answer = struct {
    xmas: u32,
    mas: u32,
};

pub fn searchXmas(letters: List([]const u8), search_char: u8, position: Point, direction: Point) u32 {
    const current_char = getChar(letters, position);
    if (current_char == search_char) {
        const next = position.add(&direction);
        if (current_char == 'M') {
            return searchXmas(letters, 'A', next, direction);
        } else if (current_char == 'A') {
            return searchXmas(letters, 'S', next, direction);
        } else if (current_char == 'S') {
            return 1; // found all letters
        }
    }
    return 0;
}

pub fn countXmas(letters: List([]const u8), starts: List(Point)) u32 {
    var counter: u32 = 0;
    for (starts.items) |start| {
        for (AllDirections) |direction| {
            const next = start.add(&direction);
            counter += searchXmas(letters, 'M', next, direction);
        }
    }
    return counter;
}

pub fn countMas(letters: List([]const u8), starts: List(Point)) u32 {
    var counter: u32 = 0;
    for (starts.items) |start| {
        const a_char = getChar(letters, start) orelse continue;
        const top_left_char = getChar(letters, start.add(&AllDirections[4])) orelse continue;
        const down_right_char = getChar(letters, start.add(&AllDirections[7])) orelse continue;
        const top_right_char = getChar(letters, start.add(&AllDirections[5])) orelse continue;
        const down_left_char = getChar(letters, start.add(&AllDirections[6])) orelse continue;

        const tldr = [3]u8{ top_left_char, a_char, down_right_char };
        const trdl = [3]u8{ top_right_char, a_char, down_left_char };
        if ((eql(u8, &tldr, "MAS") or eql(u8, &tldr, "SAM")) and (eql(u8, &trdl, "MAS") or eql(u8, &trdl, "SAM"))) {
            counter += 1;
        }
    }
    return counter;
}

pub fn getChar(letters: List([]const u8), point: Point) ?u8 {
    if (0 > point.x or point.x >= letters.items.len) {
        return null;
    }
    const row = @as(usize, @intCast(point.x));

    if (0 > point.y or point.y >= letters.items[row].len) {
        return null;
    }
    const col = @as(usize, @intCast(point.y));
    return letters.items[row][col];
}

pub fn solve(input: []const u8) !Answer {
    var rows = tokenizeScalar(u8, input, '\n');

    var letters = List([]const u8).init(alloc);
    defer letters.deinit();
    var x_starts = List(Point).init(alloc);
    defer x_starts.deinit();
    var a_starts = List(Point).init(alloc);
    defer a_starts.deinit();

    var x: usize = 0;
    while (rows.next()) |row| {
        try letters.append(row);
        for (row, 0..) |letter, y| {
            if (letter == 'X') {
                try x_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
            } else if (letter == 'A') {
                try a_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
            }
        }
        x += 1;
    }

    // PART 1
    const xmas = countXmas(letters, x_starts);

    // PART 2
    const mas = countMas(letters, a_starts);

    return Answer{ .xmas = xmas, .mas = mas };
}

pub fn main() !void {
    const answer = try solve(@embedFile("input.txt"));
    print("Part 1: {d}\n", .{answer.xmas});
    print("Part 2: {d}\n", .{answer.mas});
}

test "test input" {
    const answer = try solve(@embedFile("test.txt"));
    try std.testing.expectEqual(18, answer.xmas);
}


  

 python

    
from pathlib import Path


def parse_input(input: str) -> list[str]:
    return input.strip().splitlines()


def extract_strings_one(m: int, n: int, haystack: list[str], l: int = 4) -> list[str]:
    result = []
    # Right
    if m + l <= len(haystack[n]):
        result.append(haystack[n][m : m + l])
    # Up-Right
    if m + l <= len(haystack[n]) and n > l - 2:
        result.append("".join([haystack[n - i][m + i] for i in range(l)]))
    # Up
    if n > l - 2:
        result.append("".join([haystack[n - i][m] for i in range(l)]))
    # Up-Left
    if m > l - 2 and n > l - 2:
        result.append("".join([haystack[n - i][m - i] for i in range(l)]))
    # Left
    if m > l - 2:
        result.append("".join([haystack[n][m - i] for i in range(l)]))
    # Down-Left
    if m > l - 2 and n + l <= len(haystack):
        result.append("".join([haystack[n + i][m - i] for i in range(l)]))
    # Down
    if n + l <= len(haystack):
        result.append("".join([haystack[n + i][m] for i in range(l)]))
    # Down-Right
    if m + l <= len(haystack[n]) and n + l <= len(haystack):
        result.append("".join([haystack[n + i][m + i] for i in range(l)]))
    return result


def extract_strings_two(m: int, n: int, haystack: list[str], d: int = 1) -> list[str]:
    result = []
    if 0 <= m - d and m + d < len(haystack[n]) and 0 <= n - d and n + d < len(haystack):
        result.append("".join([haystack[n + i][m + i] for i in range(-d, d + 1)]))
        result.append("".join([haystack[n - i][m + i] for i in range(-d, d + 1)]))
    return result


def part_one(input: str) -> int:
    lines = parse_input(input)
    xmas_count = 0
    for i, line in enumerate(lines):
        x = line.find("X", 0)
        while x != -1:
            xmas_count += len(
                list(filter(lambda s: s == "XMAS", extract_strings_one(x, i, lines)))
            )
            x = line.find("X", x + 1)
    return xmas_count


def part_two(input: str) -> int:
    lines = parse_input(input)
    x_mas_count = 0
    for i, line in enumerate(lines[1:-1], 1):
        a = line.find("A", 0)
        while a != -1:
            if (
                len(
                    list(
                        filter(
                            lambda s: s in ("MAS", "SAM"),
                            extract_strings_two(a, i, lines),
                        )
                    )
                )
                == 2
            ):
                x_mas_count += 1
            a = line.find("A", a + 1)
    return x_mas_count


if __name__ == "__main__":
    input = Path("input").read_text("utf-8")
    print(part_one(input))
    print(part_two(input))

  

 nim

    
import ../aoc, strutils

type
  Cell* = tuple[x,y:int]

#the 8 grid direction
const directions : array[8, Cell] = [
  (1, 0), (-1, 0),
  (0, 1), ( 0,-1),
  (1, 1), (-1,-1),
  (1,-1), (-1, 1)
]

const xmas = "XMAS"

#part 1
proc searchXMAS*(grid:seq[string], x,y:int):int =
  #search in all 8 directions (provided we can find a full match in that direction)
  let w = grid[0].len
  let h = grid.len
  
  for dir in directions:
    # check if XMAS can even fit
    let xEnd = x + dir.x * 3
    let yEnd = y + dir.y * 3
    if xEnd < 0 or xEnd >= w or
       yEnd < 0 or yEnd >= h:
      continue;
    
    #step along direction
    var matches = 0
    for s in 0..3:
      if grid[y + dir.y * s][x + dir.x * s] == xmas[s]:
        inc matches
        
    if matches == xmas.len:
      inc result

#part 2
proc isMAS(grid:seq[string], c, o:Cell):bool=
  let ca : Cell = (c.x+o.x, c.y+o.y)
  let cb : Cell = (c.x-o.x, c.y-o.y)
  let a = grid[ca.y][ca.x]
  let b = grid[cb.y][cb.x]
  (a == 'M' and b == 'S') or (a == 'S' and b == 'M')

proc searchCrossMAS*(grid:seq[string], x,y:int):bool =
  grid[y][x] == 'A' and
  grid.isMAS((x,y), (1,1)) and
  grid.isMAS((x,y), (1,-1))

proc solve*(input:string): array[2,int] =
  let grid = input.splitLines
  let w = grid[0].len
  let h = grid.len
  
  #part 1
  for y in 0..<h:
    for x in 0..<w:
      result[0] += grid.searchXMAS(x, y)
  
  #part 2, skipping borders
  for y in 1..<h-1:
    for x in 1..<w-1:
      result[1] += (int)grid.searchCrossMAS(x, y)

  

 rust

    
use std::iter::zip;

use crate::utils::read_lines;

pub fn solution1() {
    let puzzle = read_puzzle();

    let horizontal_sum = puzzle
        .iter()
        .map(|line| {
            line.windows(4)
                .filter(|window| {
                    matches!(window, [b'X', b'M', b'A', b'S'] | [b'S', b'A', b'M', b'X'])
                })
                .count() as u32
        })
        .sum::<u32>();
    let vertical_and_diagonal_sum = puzzle
        .windows(4)
        .map(|window| {
            count_xmas(window, (0, 0, 0, 0))
                + count_xmas(window, (0, 1, 2, 3))
                + count_xmas(window, (3, 2, 1, 0))
        })
        .sum::<u32>();

    println!(
        "XMAS count = {}",
        horizontal_sum + vertical_and_diagonal_sum
    );
}

pub fn solution2() {
    let puzzle = read_puzzle();

    let sum = puzzle
        .windows(3)
        .map(|window| {
            zip(
                window[0].windows(3),
                zip(window[1].windows(3), window[2].windows(3)),
            )
            .map(|(a, (b, c))| (a, b, c))
            .filter(|tuple| {
                matches!(
                    tuple,
                    ([b'M', _, b'M'], [_, b'A', _], [b'S', _, b'S'])
                        | ([b'S', _, b'M'], [_, b'A', _], [b'S', _, b'M'])
                        | ([b'M', _, b'S'], [_, b'A', _], [b'M', _, b'S'])
                        | ([b'S', _, b'S'], [_, b'A', _], [b'M', _, b'M'])
                )
            })
            .count() as u32
        })
        .sum::<u32>();

    println!("X-MAS count = {sum}");
}

fn count_xmas(
    window: &[Vec<u8>],
    (skip0, skip1, skip2, skip3): (usize, usize, usize, usize),
) -> u32 {
    zip(
        window[0].iter().skip(skip0),
        zip(
            window[1].iter().skip(skip1),
            zip(window[2].iter().skip(skip2), window[3].iter().skip(skip3)),
        ),
    )
    .map(|(a, (b, (c, d)))| (a, b, c, d))
    .filter(|tup| matches!(tup, (b'X', b'M', b'A', b'S') | (b'S', b'A', b'M', b'X')))
    .count() as u32
}

fn read_puzzle() -> Vec<Vec<u8>> {
    read_lines("src/day4/input.txt")
        .map(|line| line.into_bytes())
        .collect()
}