Ceres Search

Advent of Code 2024 Day 4

Part 1

X marks the (hundreds of?) spots

I'm surprised there hasn't been a literal word search puzzle like this until now.

It seems daunting, but my strategy will be:

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

Checking this strategy on the example leads me to believe it's a winning approach.

Now for the exciting part: coding this whole thing from scratch!

Find the index of each X in a grid...eventually

First, I have to parse the input into a 2D array of characters:

let grid = input.split('\n').map(line => line.split(''))

An obstacle I often face in grid puzzles is accounting for out-of-bounds indices.

If I start from a border cell - or a cell close to the border - and walk so far in a direction toward the edge, I'm eventually going to encounter a row or column that is out-of-bounds.

I have two strategies for dealing with this:

1. Add checks to my conditions for non-existent rows or columns
2. Pad the grid with enough rows and columns that there is no risk of going out-of-bounds

For this challenge, I opt for #2.

Padding my grid with a 3-cell thick border looks like this:

grid = grid.map(line => ['.','.','.',...line,'.','.','.'])
grid = [
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  ...grid,
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.')
]

The example grid now looks like this:

................
................
................
...MMMSXXMASM...
...MSAMXMSMSA...
...AMXSXMAAMM...
...MSAMASMSMX...
...XMASAMXAMM...
...XXAMMXXAMA...
...SMSMSASXSS...
...SAXAMASAAA...
...MAMMMXMMMM...
...MXMXAXMASX...
................
................
................

Now I'm ready to catalogue the coordinates of each X in the padded grid:

let Xs = []
for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == "X") {
      Xs.push([row, col])
    }
  }
}

Success: it found all 19 of the Xs in the example grid!

Walking three steps in eight directions from each X

All eight relative coordinates are coded as an 8-element array:

let dirs = [
  [-1,-1],
  [-1,0],
  [-1,1],
  [0,-1],
  [0,1],
  [1,-1],
  [1,0],
  [1,1]
]

Now for the main algorithm:

For each X
  For each direction
    Create an array that starts with X
    Do 3 times
      Move one cell in this direction
      Add the value of that cell to the array
    Check whether the concatenation of all four values is "XMAS"
      If it is, increment a tally

And in JavaScript:

Xs.reduce((total, coord) => {
  dirs.forEach((dir) => {
    let [row, col] = coord;
    let [y, x] = dir;
    let word = ["X"];
    for (let i = 0; i < 3; i++) {
      row += y;
      col += x;
      word.push(grid[row][col]);
    }
    if (word.join("") == "XMAS") {
      total++;
    }
  });
  return total;
}, 0);

It generates the correct answer for the example input!

What will happen when I run it on my puzzle input??!!

I get a number: a couple thousand 'XMAS's

Is it the correct answer?

IT IS!!!

Woohooo!!!

Can't wait to see what Part 2 has up its sleeve...

Part 2

Ohhh my. This got a bit more complicated. But doable!

In Part 1 I was looking for Xs.

Now, I am looking for Ms.

In Part 1 I recorded letters in a straight line to make a word.

Now, I am looking for four configurations of a 5-cell phrase:

M S   M M   S M   S S
 A     A     A     A
M S   S S   S M   M M

A single M could be part of several X-MAS's.

By checking every M, I'm likely to encounter several multiple times.

I'll need to build a Set() of stringified coordinates for each match. That way, I only account for an X-MAS instance once.

A sudden - brilliant! - idea

I'm not going to check every M.

I'll check every A.

And I'll check the four cells diagonally adjacent, in clockwise order.

X-MAS matches will fit one of these four patterns:

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

`

Phew! This will be a lot less tedious than my original idea.

And I should be able to repurpose most of my Part 1 code!

Copy-Paste-Tweak

Finding all As in the grid:
js
let As = [];
for (let row = 0; row < grid.length; row ) {
for (let col = 0; col < grid[0].length; col ) {
if (grid[row][col] == "A") {
As.push([row, col]);
}
}
}

Establishing the order of relative coordinates to check:
js
let Adirs = [
[-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

Adding up the tally of matches:
js
let part2 = As.reduce((total, coord) => {
let clockwise = Adirs.map((dir) => {
let [row, col] = coord;
let [y, x] = dir;
return grid[row y][col x];
});
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(clockwise.join(""))) {
total ;
}
return total;
}, 0);

It generates the correct answer for the example input!

Now to check on my puzzle input...

Indeed!!! The correct answer!!!

I'm so glad it struck me to use the As instead of the Ms.

Saved me hours of troubleshooting headaches, I'm sure.

That was another fun and accessible puzzle!

I wonder what Day 5 has in store.

The above is the detailed content of Ceres Search. For more information, please follow other related articles on the PHP Chinese website!