AoC 24 - Day 4: Ceres Search

Day 4 - Ceres Search

Today's challenge was a good old word search challenge.

Part 1 was a classic word search, so it required us to search for the matching word "XMAS" in a unilateral direction (up, down, left, right, diagonal and reverse).

I have a tool I've used in the past for things like this, a helper class library where we have a Point struct and Directions class and a ParseGridFromFile method that aids in mapping string inputs to the grid.

Brief Intro to Tools:

public struct Point => A Point struct is used to represent a 2D point with X and Y coordinates.

We then overload the operators to define what we do when using the Point struct and call +, '-', '*' on them e.g. (1,2) + (2,3).

---

The Directions class exposes some commonly used methods for traversing a grid-like structure.

Part 1 :

using SolutionTools;

namespace Day4_Csharp
{
    public class Part1
    {
        private int _mapWidth;
        private int _mapHeight;

        private readonly char[,] _map = Tools.ParseGridFromFile("input1.txt");


        public int Solve()
        {
            _mapHeight = _map.GetLength(0);
            _mapWidth = _map.GetLength(1);

            var foundCount = 0;


            for (var x = 0; x < _mapWidth; x++)
            {
                for (var y = 0; y < _mapHeight; y++)
                {
                    foundCount += Directions.WithDiagonals.Count(direction =>
                        IsWordFoundAtStartingPoint((x, y), direction, "XMAS"));
                }
            }

            return foundCount;
        }


        private bool IsWordFoundAtStartingPoint(Point startingPoint, Point direction, string word)
        {
            for (var characterIndex = 0; characterIndex < word.Length; characterIndex++)
            {
                var currentPosition = startingPoint + direction * characterIndex;

                if (IsOutOfBounds(currentPosition) ||
                    _map[currentPosition.X, currentPosition.Y] != word[characterIndex])
                {
                    return false;
                }
            }

            return true;
        }


        private bool IsOutOfBounds(Point position)
        {
            return position.X < 0 || position.X >= _mapWidth || position.Y < 0 || position.Y >= _mapHeight;
        }
    }
}

This code solves the puzzle by searching for the word "XMAS" in a 2D grid parsed from the input string.

Searching for "XMAS": The program loops through each character (point) in the grid, checking if the word "XMAS" can be found in any direction using a helper method IsWordFoundAtStartingPoint, using the Directions helpers.

Bounds Checking: Before checking each character of the word, it ensures the current position is within the grid bounds using IsOutOfBounds, to prevent going outside the grid whilst searching.

Counting Matches: If "XMAS" is found in any direction, it increments the foundCount.

Part 2:

Part 2 was a bit more difficult, as you now only had to concern yourself with the word "MAS" in the shape of an 'X'.

Luckily for us, I have a helper tool for this exact scenario DiagonalsOnly. We gather the opposite direction by multiplying the current direction by -1 to switch it.

Now you may be thinking, why do we start in the opposite direction, I can explain.

startingPoint = (x, y) + oppositeDirection:

The purpose of this is to move backwards a step from the current grid point before starting the search for the word. For example, if we are searching for "MAS" starting from (x, y), we want to make sure the entire word fits in the grid by ensuring we have room to move in the direction we are searching.

Example
Let's say we're checking from position (3, 3) on a grid and the direction is (1, 1) (i.e. down-right).

The opposite direction would be (-1, -1) (up-left).
We calculate the starting point as (3, 3) + (-1, -1) = (2, 2) (which is one step up-left).

Now, we check if the word "MAS" fits by moving in the (1, 1) direction (down-right) from the new starting point (2, 2).
This adjustment ensures the search covers the full word from a valid starting point within the bounds of the grid.

using Day4_Csharp;
using SolutionTools;

namespace Day4_Csharp;

public class Part2
{
    private int _mapWidth;
    private int _mapHeight;
    private readonly char[,] _map = Tools.ParseGridFromFile("input1.txt");


    public int Solve()
    {
        _mapHeight = _map.GetLength(0);
        _mapWidth = _map.GetLength(1);

        var foundCount = 0;


        for (var x = 0; x < _mapWidth; x++)
        {
            for (var y = 0; y < _mapHeight; y++)
            {
                var diagonalMatchCount = 0;
                foreach (var diagonalDirection in Directions.DiagonalsOnly)
                {
                    Point oppositeDirection = diagonalDirection * -1;
                    Point startingPoint = (x, y) + oppositeDirection;
                    if (IsWordFoundAtStartingPoint(startingPoint, diagonalDirection, "MAS")) diagonalMatchCount++;
                }

                if (diagonalMatchCount == 2)
                {
                    foundCount++;
                }
            }
        }

        return foundCount;
    }

    private bool IsWordFoundAtStartingPoint(Point startingPoint, Point direction, string word)
    {
        for (var characterIndex = 0; characterIndex < word.Length; characterIndex++)
        {
            // Head in this direction for each letter in search word
            var currentPosition = startingPoint + direction * characterIndex;

            if (IsOutOfBounds(currentPosition) ||
                _map[currentPosition.X, currentPosition.Y] != word[characterIndex])
            {
                return false;
            }
        }

        return true;
    }


    private bool IsOutOfBounds(Point position)
    {
        return position.X < 0 || position.X >= _mapWidth || position.Y < 0 || position.Y >= _mapHeight;
    }
}

You could replace the foreach loop for a more "elegant" looking LINQ statement, however, this can be less legible/familiar for some other developers to understand. So I like to keep it simple

var diagonalMatchCount = (from diagonalDirection in Directions.DiagonalsOnly
    let oppositeDirection = diagonalDirection * -1
    let startingPoint = (x, y) + oppositeDirection
    where IsWordFoundAtStartingPoint(startingPoint, diagonalDirection, "MAS")
    select diagonalDirection).Count();

Didn't have time to do the Python variation of this today, if I get time I'll return and add it in.

Thanks and as always you can follow on twitter and see all other solutions in my repo at GitHub