Day 4: Ceres Search

I have a Grid2D helper class and tried to be fancy with it -- instead of just looping through the grid in eight different directions, I tried to get away with rotating and mirroring the grid, because I have helper methods for that sort of thing. That would have been faster if it had worked, but it didn't (because I had an off-by-one error in the actual counting), so I wasted 15 minutes on that before using the naive approach.

Then I got stuck for a very long time on Part 2, because apparently bending the MAS around the corner isn't allowed, i.e.

S M
 A
M S

is invalid, and the puzzle description did not make that clear. Unfortunately it didn't appear in the test input either (which might have been deliberate), so I was left scratching my head for a good long while.

pub fn part1(input: &PuzzleInput) -> String {
    let mut count = 0;

    let xmas = ['X', 'M', 'A', 'S'];

    for col in 0..input.grid.width {
        for row in 0..input.grid.height {
            for dx in [-1i32, 0, 1] {
                'outer: for dy in [-1i32, 0, 1] {
                    if dx == 0 && dy == 0 {
                        continue;
                    }

                    for (i, &x) in xmas.iter().enumerate() {
                        let c = input
                            .grid
                            .get((col + dx * i as i32, row + dy * i as i32).into())
                            .unwrap_or(&'.');

                        if c != &x {
                            continue 'outer;
                        }
                    }

                    count += 1;
                }
            }
        }
    }

    count.to_string()
}

pub fn part2(input: &PuzzleInput) -> String {
    let mut count = 0;

    for col in 1..(input.grid.width - 1) {
        for row in 1..(input.grid.height - 1) {
            let center = *input.grid.get((col, row).into()).unwrap();
            let tl = *input.grid.get((col - 1, row - 1).into()).unwrap();
            let tr = *input.grid.get((col + 1, row - 1).into()).unwrap();
            let bl = *input.grid.get((col - 1, row + 1).into()).unwrap();
            let br = *input.grid.get((col + 1, row + 1).into()).unwrap();

            if center == 'A' {
                let x = (tl, tr, bl, br);

                if x == ('M', 'S', 'M', 'S')
                    || x == ('S', 'M', 'S', 'M')
                    || x == ('M', 'M', 'S', 'S')
                    || x == ('S', 'S', 'M', 'M')
                {
                    count += 1;
                }
            }
        }
    }

    count.to_string()
}

def compute_p1(input)
  grid = Grid.new(input, default: nil)
  count = 0
  grid.each_index do |x, y|
    # skip any cell that isn't the start of an XMAS
    next unless grid.get(x,y) == "X"

    # check forwards
    forwards = [grid.get(x+1,y), grid.get(x+2,y), grid.get(x+3,y)].join()
    count += 1 if forwards == "MAS"

    # check backwards
    backwards = [grid.get(x-1,y), grid.get(x-2,y), grid.get(x-3,y)].join()
    count += 1 if backwards == "MAS"

    # check down
    down = [grid.get(x,y+1), grid.get(x,y+2), grid.get(x,y+3)].join()
    count += 1 if down == "MAS"

    # check up
    up = [grid.get(x,y-1), grid.get(x,y-2), grid.get(x,y-3)].join()
    count += 1 if up == "MAS"

    # check down_left
    down_left = [grid.get(x-1,y+1), grid.get(x-2,y+2), grid.get(x-3,y+3)].join()
    count += 1 if down_left == "MAS"

    # check down_right
    down_right = [grid.get(x+1,y+1), grid.get(x+2,y+2), grid.get(x+3,y+3)].join()
    count += 1 if down_right == "MAS"

    # check up_left
    up_left = [grid.get(x-1,y-1), grid.get(x-2,y-2), grid.get(x-3,y-3)].join()
    count += 1 if up_left == "MAS"

    # check up_right
    up_right = [grid.get(x+1,y-1), grid.get(x+2,y-2), grid.get(x+3,y-3)].join()
    count += 1 if up_right == "MAS"
  end

  return count
end

def compute_p2(input)
  grid = Grid.new(input, default: nil)
  count = 0
  grid.each_index do |x, y|
    # skip any cell that isn't the center of an X-MAS
    next unless grid.get(x,y) == "A"

    # check \ direction
    down_right = [grid.get(x-1,y-1), grid.get(x,y), grid.get(x+1,y+1)].join
    next unless down_right == "MAS" || down_right == "SAM"

    # check / direction
    down_left = [grid.get(x+1,y-1), grid.get(x,y), grid.get(x-1,y+1)].join
    next unless down_left == "MAS" || down_left == "SAM"

    count += 1

  end
  return count
end

#!/usr/bin/env ruby

class Grid
  attr_accessor :grid
  attr_accessor :width
  attr_accessor :height
  attr_accessor :default

  def initialize(input, default: nil)
    @grid = input.lines
              .map(&:strip)
              .map(&:chars)
    @width = @grid[0].size
    @height = @grid.size
    @default = default
  end

  def in_bounds?(x, y)
    x >= 0 && x < @width && y >= 0 && y < @height
  end

  def get(x,y)
    if x < 0 || x >= @width || y < 0 || y >= @height
      @default
    else
      @grid[y][x]
    end
  end

  def set(x,y,val)
    if x < 0 || x >= @width || y < 0 || y >= @height
      raise "Tried to write out of bounds"
    else
      @grid[y][x] = val
    end
  end

  def all_coords
    (0...width).to_a.product((0...height).to_a)
  end

  def coords_where
    all_coords.filter { |x, y| yield(@grid[y][x]) }
  end

  def each_index
    all_coords.each do |x,y|
      yield(x,y)
    end
  end

  def update
    each_index do |x, y|
      @grid[y][x] = yield(x, y, @grid[y][x])
    end
  end

  def ==(other)
    return false if other.class != Grid
    return other.grid == @grid
  end

  def all?(value)
    return @grid.flatten.all?(value)
  end

  def neighbors(x,y)
    [
      [-1, -1], [0, -1], [+1, -1],
      [-1,  0],          [+1, 0],
      [-1, +1], [0, +1], [+1, +1]
    ].map { |dx, dy| get(x+dx, y+dy) }
  end

  def to_s
    s = ""
    height.times do |y|
      width.times do |x|
        s << get(x,y) || default.to_s
      end
      s << "\n"
    end
    return s
  end

  def count(value)
    if block_given?
      @grid.flatten.count(&block)
    else
      @grid.flatten.count(value)
    end
  end
end

My approach here was to locate X's and look for occurrences of "MAS" in all directions. I generally would have used loops for this, but I was in a rush so I just hard-coded everything. Quick and dirty.

#!/usr/bin/awk -f
BEGIN {
	FS = ""
	total = ""
}
{
	for (i = 1; i <= NF; ++i)
		grid[i, NR] = $i
}
END {
	for (i in grid) {
		if (grid[i] == "X") {
			split(i, xy, SUBSEP)
			print(xy[1], xy[2])
			x = xy[1]
			y = xy[2]
			# upper-left
			if (grid[x-1, y-1] == "M" && grid[x-2, y-2] == "A" && grid[x-3, y-3] == "S")
				total += 1
			# upper-right
			if (grid[x+1, y-1] == "M" && grid[x+2, y-2] == "A" && grid[x+3, y-3] == "S")
				total += 1
			# lower-left
			if (grid[x-1, y+1] == "M" && grid[x-2, y+2] == "A" && grid[x-3, y+3] == "S")
				total += 1
			# lower-right
			if (grid[x+1, y+1] == "M" && grid[x+2, y+2] == "A" && grid[x+3, y+3] == "S")
				total += 1
			# left
			if (grid[x-1, y] == "M" && grid[x-2, y] == "A" && grid[x-3, y] == "S")
				total += 1
			# right
			if (grid[x+1, y] == "M" && grid[x+2, y] == "A" && grid[x+3, y] == "S")
				total += 1
			# up
			if (grid[x, y-1] == "M" && grid[x, y-2] == "A" && grid[x, y-3] == "S")
				total += 1
			# down
			if (grid[x, y+1] == "M" && grid[x, y+2] == "A" && grid[x, y+3] == "S")
				total += 1
		}
	}
	print total
}

I was expecting to have to switch to a smarter approach, but this was even easier than part 1 for me. I locate A's and look around diagonally for M/S pairs.

#!/usr/bin/awk -f
BEGIN {
	FS = ""
	total = ""
}
{
	for (i = 1; i <= NF; ++i)
		grid[i, NR] = $i
}
END {
	for (i in grid) {
		if (grid[i] == "A") {
			split(i, xy, SUBSEP)
			x = xy[1]
			y = xy[2]
			if ((grid[x-1, y-1] == "M" && grid[x+1, y+1] == "S") || (grid[x-1, y-1] == "S" && grid[x+1, y+1] == "M"))
				if ((grid[x+1, y-1] == "M" && grid[x-1, y+1] == "S") || (grid[x+1, y-1] == "S" && grid[x-1, y+1] == "M"))
					total += 1
		}
	}
	print total
}

/* Advent of Code 2024
 * Day 04: Ceres Search
 */

#import "Basic";
#import "File";
#import "String";

// The Vector2 struct in the Math module uses floats, which we don't want since
// we're using this struct as a modifier for array indices.
Vector2_Int :: struct {
    x, y: int;
}

main :: () {
    input, success := read_entire_file("inputs/day_04.txt");
    assert(success);

    rows := split(input, "\n");
    rows.count -= 1; // We're assuming a trailing newline.

    xmas_count := 0;
    for row, y: rows {
        for char, x: row {
            if char == #char "X" {
                // There's no point checking for the remaining letters if there
                // isn't space for them anyway.
                right_allowed := x <= row.count - 4;
                left_allowed  := x >= 3;

                if right_allowed && slice(row, x + 1, 3) == "MAS" {
                    xmas_count += 1;
                }

                if left_allowed && slice(row, x - 3, 3) == "SAM" {
                    xmas_count += 1;
                }

                directions: [..] Vector2_Int;

                if y <= rows.count - 4 {
                    array_add(*directions, .{0, 1});
                    if right_allowed array_add(*directions, .{1, 1});
                    if left_allowed  array_add(*directions, .{-1, 1});
                }

                if y >= 3 {
                    array_add(*directions, .{0, -1});
                    if right_allowed array_add(*directions, .{1, -1});
                    if left_allowed  array_add(*directions, .{-1, -1});
                }

                for direction: directions {
                    found_letters: [3] u8;

                    scan_x := x;
                    scan_y := y;

                    for 0..2 {
                        scan_x += direction.x;
                        scan_y += direction.y;
                        found_letters[it] = rows[scan_y][scan_x];
                    }

                    if xx found_letters == "MAS" {
                        xmas_count += 1;
                    }
                }
            }
        }
    }

    print("Part 1: %\n", xmas_count);

    x_mas_count := 0;
    for y: 1..rows.count - 2 {
        for x: 1..rows[y].count - 2 {
            // The middle character will always be A.
            if rows[y][x] == #char "A" {
                // Maybe there's a better way to do this.
                if (
                    (
                        rows[y - 1][x - 1] == #char "M"
                        && rows[y + 1][x + 1] == #char "S"
                    ) || (
                        rows[y - 1][x - 1] == #char "S"
                        && rows[y + 1][x + 1] == #char "M"
                    )
                ) && (
                    (
                        rows[y + 1][x - 1] == #char "M"
                        && rows[y - 1][x + 1] == #char "S"
                    ) || (
                        rows[y + 1][x - 1] == #char "S"
                        && rows[y - 1][x + 1] == #char "M"
                    )
                ) {
                    x_mas_count += 1;
                }
            }
        }
    }

    print("Part 2: %\n", x_mas_count);
}

import "utils" as utils;

let input = utils::get_input(4, false);

let grid = input.split("\n").map(|line| line.to_chars());
let height = grid.len();
let width = grid[0].len();

let total = 0;
for y in 0..height {
    for x in 0..width {
        for vy in range(-1, 2, 1) {
            for vx in range(-1, 2, 1) {
                if vy == 0 && vx == 0 {
                    continue;
                }
                if has_xmas!(x, y, vx, vy) {
                    total += 1;
                }
            }
        }
    }
}

fn has_xmas(x, y, vx, vy) {
    x+vx*3 < width && y+vy*3 < height
      && x+vx*3 >= 0 && y+vy*3 >= 0
      &&grid[y][x] == 'X'
      && grid[y+vy*1][x+vx*1] == 'M'
      && grid[y+vy*2][x+vx*2] == 'A'
      && grid[y+vy*3][x+vx*3] == 'S'
}

print(`part 1: ${total}`);

let total = 0;
for y in 0..height {
    for x in 0..width {
        if grid[y][x] != 'A' || x-1 < 0 || x+1 >= width || y-1 < 0 || y+1 >= height {
            continue;
        }
        let first_diag = grid[y-1][x-1] + grid[y][x] + grid[y+1][x+1];
        let second_diag = grid[y-1][x+1] + grid[y][x] + grid[y+1][x-1];
        if (first_diag == "MAS" || first_diag == "SAM") && (second_diag == "MAS" || second_diag == "SAM") {
            total += 1;
        }
    }
}

print(`part 2: ${total}`);

#! /usr/bin/env racket
#lang racket

(require "common.rkt" math/base rackunit)

; return the value at grid[i][j]
; null if i or j are invalid
(define (grid-ref grid i j)
  (cond
    [(negative? i) null]
    [(>= i (length grid)) null]
    [(negative? j) null]
    [(>= j (length (list-ref grid i))) null]
    [else (list-ref (list-ref grid i) j)]))

;; we assume input is a non-empty rectangle,
;; i.e. width and height are even for all rows and colums, respectively, and
;;      min(width, height) >= 1
(define (day04/run-part01 input)
  ;; really... these could just be made with a loop and adding an extra parameter for the direction
  (define (check-up grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-up grid (- i 1) j 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-up grid (- i 1) j 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-down grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-down grid (+ i 1) j 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-down grid (+ i 1) j 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-left grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-left grid i (- j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-left grid i (- j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-right grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-right grid i (+ j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-right grid i (+ j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-up-left grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-up-left grid (- i 1) (- j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-up-left grid (- i 1) (- j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-up-right grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-up-right grid (- i 1) (+ j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-up-right grid (- i 1) (+ j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-down-left grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-down-left grid (+ i 1) (- j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-down-left grid (+ i 1) (- j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  (define (check-down-right grid i j [cur 0])
    (cond
      [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j))
                       (check-down-right grid (+ i 1) (+ j 1) 1)
                       0)]
      [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j))
                       (check-down-right grid (+ i 1) (+ j 1) 2)
                       0)]
      [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j))
                       1
                       0)]
      [else 0]))
  ;; loop through the whole grid,
  ;; for each X, recursively check each direction
  (for*/fold ([total 0])
             ([i (length input)]
              [j (length (list-ref input 0))])
    ;; If we find an 'X', let's check for XMASes
    (let ([cur (list-ref (list-ref input i) j)])
      (if (eq? cur #\X)
          (+ total
             (check-up input (- i 1) j)
             (check-down input (+ i 1) j)
             (check-left input i (- j 1))
             (check-right input i (+ j 1))
             (check-up-left input (- i 1) (- j 1))
             (check-up-right input (- i 1) (+ j 1))
             (check-down-left input (+ i 1) (- j 1))
             (check-down-right input (+ i 1) (+ j 1)))
          total))))

(define (day04/run-part02 input)
  (define (check-x-mas grid i j)
    (if (eq? 2 (sum (list (check-updown-leftright grid i j)
                          (check-updown-rightleft grid i j)
                          (check-downup-leftright grid i j)
                          (check-downup-rightleft grid i j))))
        1
        0))

  (define (check-updown-leftright grid i j)
    (if (and (eq? #\M (grid-ref grid (- i 1) (- j 1)))
             (eq? #\S (grid-ref grid (+ i 1) (+ j 1))))
        1
        0))
  (define (check-updown-rightleft grid i j)
    (if (and (eq? #\M (grid-ref grid (- i 1) (+ j 1)))
             (eq? #\S (grid-ref grid (+ i 1) (- j 1))))
        1
        0))
  (define (check-downup-leftright grid i j)
    (if (and (eq? #\M (grid-ref grid (+ i 1) (- j 1)))
             (eq? #\S (grid-ref grid (- i 1) (+ j 1))))
        1
        0))
  (define (check-downup-rightleft grid i j)
    (if (and (eq? #\M (grid-ref grid (+ i 1) (+ j 1)))
             (eq? #\S (grid-ref grid (- i 1) (- j 1))))
        1
        0))

  ;; loop through the whole grid,
  ;; for each X, recursively check each direction
  (for*/fold ([total 0])
             ([i (length input)]
              [j (length (list-ref input 0))])
    ;; If we find an 'X', let's check for XMASes
    (let ([cur (list-ref (list-ref input i) j)])
      ;; A is always the center
      (if (eq? cur #\A)
          (+ total
             (check-x-mas input i j))
          total))))

(let* ([input (input->list (open-input-file "inputs/day04.in"))]
       [part1 (day04/run-part01 input)]
       [part2 (day04/run-part02 input)])
  (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))

#!/usr/bin/env python

import sys
from typing import List

sys.path.insert(1, '../utils/')
from point2d import *

def read_file(file: str) -> List[str]:
    '''Read a file into a list of lines'''
    with open(file) as f:
        return f.read().splitlines()

# Define directions
up = Point2D( 0,-1)
dn = Point2D( 0,+1)
lf = Point2D(-1, 0)
rt = Point2D(+1, 0)
ur = Point2D(+1,-1)
dr = Point2D(+1,+1)
ul = Point2D(-1,-1)
dl = Point2D(-1,+1)
dirs = [up, dn, lf, rt, ur, dr, ul, dl]

def get_char(map: List[str], pt: Point2D) -> str:
    '''Pull the character at the point defined by Point2D'''
    if pt.x < 0 or pt.y < 0: return None
    if pt.x >= len(map[0]) or pt.y >= len(map): return None
    return map[pt.y][pt.x]

def find_word(map: List[str], pt: Point2D, dir: Point2D, word: str) -> bool:
    '''Check if word exists starting from pt in the direction of dir'''
    for step in range(0,len(word)):
        new_pt = pt + dir.mag_mult(step)
        if not get_char(map, new_pt) == word[step]: return False
    return True

def is_mas(map: List[str], pt: Point2D, dir1: Point2D, dir2: Point2D) -> bool:
    '''Checks one full diagonal of the X-MAS for M-S; find_xmas calls is_mas for both diagonals'''
    if (get_char(map, pt+dir1) == 'M' and get_char(map, pt+dir2) == 'S') or \
       (get_char(map, pt+dir1) == 'S' and get_char(map, pt+dir2) == 'M'): return True
    return False

def find_xmas(map: List[str], pt: Point2D) -> bool:
    '''Checks both diagonals of the X-MAS'''
    if is_mas(map, pt, ul, dr) and \
       is_mas(map, pt, ur, dl): return True
    return False

def part1(puzzle: List[str]) -> int:
    result = 0
    for y,line in enumerate(puzzle):
        for x,c in enumerate(line):
            if c == 'X':
                pt = Point2D(x,y)
                for direction in dirs:
                    if find_word(puzzle, pt, direction, 'XMAS'): result += 1
    return result

def part2(puzzle: List[str]) -> int:
    result = 0
    for y,line in enumerate(puzzle):
        for x,c in enumerate(line):
            if c == 'A':
                pt = Point2D(x,y)
                if find_xmas(puzzle, pt): result += 1
    return result

def main(file: str):
    # Input
    puzzle = read_file(file)

    # Part 1
    p1 = part1(puzzle)
    print(f'Part 1: {p1}')

    # Part 2
    p2 = part2(puzzle)
    print(f'Part 2: {p2}')

if __name__ == '__main__':
    main(sys.argv[1])

class Point2D:

    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point2D(self.x + other.x, self.y + other.y)

    def mag_mult(self, multiplier: int) -> None:
        return Point2D(self.x * multiplier, self.y * multiplier)

    def distance(self, other) -> int:
        return abs(self.x - other.x) + abs(self.y - other.y)

import sys

DIRECTIONS = (
    (0, 1, 2, 3),                       # up
    (0, -1j, -2j, -3j),                 # down
    (0, -1, -2, -3),                    # left
    (0, 1j, 2j, 3j),                    # right
    (0, -1 - 1j, -2 - 2j, -3 - 3j),     # diagonal down and left
    (0, -1 + 1j, -2 + 2j, -3 + 3j),     # diagonal up and left
    (0, 1 + 1j, 2 + 2j, 3 + 3j),        # diagonal up and right
    (0, 1 - 1j, 2 - 2j, 3 - 3j),        # diagonal down and right
)

grid = {}
for a, line in enumerate(sys.stdin):
    for b, char in enumerate(line.strip()):
        grid[complex(a, b)] = char

total = 0
for coord in grid:
    for direction in DIRECTIONS:
        if ''.join(grid.get(coord + d, '') for d in direction) == 'XMAS':
            total += 1

print(total)

import sys

DIRECTIONS = (
    (-1 + 1j, 0, 1 - 1j),   # diagonal upper left to lower right
    (-1 - 1j, 0, 1 + 1j),   # diagonal lower left to upper right
)

grid = {}
for a, line in enumerate(sys.stdin):
    for b, char in enumerate(line.strip()):
        grid[complex(a, b)] = char

total = 0
for coord in grid:
    diag1 = ''.join(grid.get(coord + d, '') for d in DIRECTIONS[0])
    diag2 = ''.join(grid.get(coord + d, '') for d in DIRECTIONS[1])
    if diag1 in ('MAS', 'SAM') and diag2 in ('MAS', 'SAM'):
        total += 1

print(total)