AOC 2024, Day 04: Ceres Search¶
Day 4 of Advent of Code 2024, Ceres Search, challenges us with a word search on the Ceres monitoring station. In this puzzle, we're tasked with finding instances of the word "XMAS" in various directions, and later, identifying X-MAS patterns shaped as an 'X'.
Elf Shenanigans¶
The input consists of a grid of characters, and we need to find occurrences of the word "XMAS" both normally and in the form of an X-MAS pattern.
Part 1: Word Search¶
For the first part, we are asked to locate every instance of the word "XMAS" in the grid. The word can appear horizontally, vertically, diagonally, or in reverse.
Part 2: X-MAS Pattern¶
In the second part, we're looking for an X-shaped pattern where "MAS" appears in both arms of the X. Each "MAS" can appear forwards or backwards.
Santa's Ingenious Solutions¶
using System.Collections.Frozen;
using System.Numerics;
using AdventOfCode.Lib;
using Map = System.Collections.Frozen.FrozenDictionary<AdventOfCode.Y2024.Point, char>;
namespace AdventOfCode.Y2024;
[AocPuzzle(2024, 4, "Ceres Search", "C#")]
public sealed class Day04 : IAocDay<int>
{
public static int Part1(AocInput input) =>
input.AllLines
.Pipe(ParseMap)
.Pipe(
map =>
from point in map.Keys
from direction in new[] { Point.East, Point.SouthEast, Point.South, Point.SouthWest }
select SearchWord(map, "XMAS", point, direction)
)
.Pipe(matches => matches.Count(m => m));
public static int Part2(AocInput input) =>
input.AllLines
.Pipe(ParseMap)
.Pipe(
map =>
from point in map.Keys
select SearchWord(map, "MAS", point + Point.NorthWest, Point.SouthEast) &&
SearchWord(map, "MAS", point + Point.SouthWest, Point.NorthEast)
)
.Pipe(matches => matches.Count(m => m));
private static bool SearchWord(Map map, string pattern, Point point, Point direction)
{
var len = pattern.Length;
char[] chars = [..Enumerable.Range(0, len).Select(i => map.GetValueOrDefault(point + direction * i))];
return chars.SequenceEqual(pattern) || chars.SequenceEqual(pattern.Reverse());
}
private static Map ParseMap(string[] lines) => (
from y in Enumerable.Range(0, lines.Length)
from x in Enumerable.Range(0, lines[0].Length)
select KeyValuePair.Create(new Point(x, y), lines[y][x])
).ToFrozenDictionary();
}
open AdventOfCode.Lib
[<AocPuzzle(2024, 4, "Ceres Search", "F#")>]
module Fay04 =
open Lib
let parseMap (lines: string array) : Map<Point, char> =
lines
|> Array.indexed
|> Array.collect (fun (y, line) -> [|
for x, c in line |> Seq.toArray |> Array.indexed -> { X = x; Y = y }, c
|])
|> Map.ofArray
let searchWord (map: Map<Point, char>) (pattern: string) (p: Point) (dir: Point) =
let chars = [
for i in 0 .. pattern.Length - 1 -> map.TryFind (p + dir * i) |> Option.defaultValue ' '
]
chars = Seq.toList pattern || chars = Seq.toList (Seq.rev pattern)
let searchXmas (map: Map<Point, char>) =
let directions = [ Point.East; Point.SouthEast; Point.South; Point.SouthWest ]
let searchMapForXmas = searchWord map "XMAS"
map.Keys
|> Seq.collect (fun p -> directions |> Seq.map (searchMapForXmas p))
|> Seq.filter id
let searchXmasShape (map: Map<Point, char>) =
let searchMapForXmasShape = searchWord map "MAS"
map.Keys
|> Seq.filter (fun p ->
searchMapForXmasShape (p + Point.NorthWest) Point.SouthEast
&& searchMapForXmasShape (p + Point.SouthWest) Point.NorthEast)
let part1 (input: AocInput) =
input.AllLines |> parseMap |> searchXmas |> Seq.length
let part2 (input: AocInput) =
input.AllLines |> parseMap |> searchXmasShape |> Seq.length
from aoc.core import AocInput
from collections import defaultdict
from dataclasses import astuple, dataclass
from functools import partial
@dataclass(frozen=True, slots=True)
class Point:
x: int
y: int
def __iter__(self):
return iter(astuple(self))
@staticmethod
def North():
return Point(0, -1)
@staticmethod
def NorthEast():
return Point(1, -1)
@staticmethod
def East():
return Point(1, 0)
@staticmethod
def SouthEast():
return Point(1, 1)
@staticmethod
def South():
return Point(0, 1)
@staticmethod
def SouthWest():
return Point(-1, 1)
@staticmethod
def West():
return Point(-1, 0)
@staticmethod
def NorthWest():
return Point(-1, -1)
def __add__(self, point: "Point") -> "Point":
if isinstance(point, Point) is False:
return NotImplemented
return Point(self.x + point.x, self.y + point.y)
def __mul__(self, factor: int) -> "Point":
if isinstance(factor, int) is False:
return NotImplemented
return Point(self.x * factor, self.y * factor)
Map = defaultdict[Point, str]
def parse_map(lines: list[str]) -> Map:
return defaultdict(str, {Point(x, y): c for y, l in enumerate(lines) for x, c in enumerate(l)})
def search_word(map: Map, pattern: str, p: Point, dir: Point) -> bool:
chars = [map.get(p + dir * i) for i in range(0, len(pattern))]
return chars == list(pattern) or chars == list(reversed(pattern))
def search_xmas(map: Map) -> list[bool]:
directions = [Point.East(), Point.SouthEast(), Point.South(), Point.SouthWest()]
search_map_for_xmas = partial(search_word, map, "XMAS")
return [search_map_for_xmas(p, dir) for p in map.keys() for dir in directions]
def search_xmas_shape(map: Map) -> list[bool]:
search_map_for_xmas_shape = partial(search_word, map, "MAS")
return [
search_map_for_xmas_shape(p + Point.NorthWest(), Point.SouthEast())
and search_map_for_xmas_shape(p + Point.SouthWest(), Point.NorthEast())
for p in map.keys()
]
def part1(input: AocInput) -> int:
return sum(search_xmas(parse_map(input.lines)))
def part2(input: AocInput) -> int:
return sum(search_xmas_shape(parse_map(input.lines)))
Santa's & Elves' Reflections¶
Day 4 of Advent of Code 2024 presents a difficult challenge in pattern matching and grid traversal. The key to solving both parts lies in recognizing all possible directions and orientations of the word "XMAS" and "X-MAS". The problem is a great exercise in multi-directional searching and leveraging grid-based operations.
Check out the repository for solutions: AdventOfCode & AdventOfCode.Lib.