Day 4: Ceres Search

2024-12-04

"Looks like the Chief's not here. Next!" One of The Historians pulls out a device and pushes the only button on it. After a brief flash, you recognize the interior of the Ceres monitoring station!

As the search for the Chief continues, a small Elf who lives on the station tugs on your shirt; she'd like to know if you could help her with her word search (your puzzle input). She only has to find one word: XMAS.

This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It's a little unusual, though, as you don't merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:

1
2
3
4
5
..X...
.SAMX.
.A..A.
XMAS.S
.X....

The actual word search will be full of letters instead. For example:

1
2
3
4
5
6
7
8
9
10
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

In this word search, XMAS occurs a total of 18 times; here's the same word search again, but where letters not involved in any XMAS have been replaced with .:

1
2
3
4
5
6
7
8
9
10
....XXMAS.
.SAMXMS...
...S..A...
..A.A.MS.X
XMASAMX.MM
X.....XA.A
S.S.S.S.SS
.A.A.A.A.A
..M.M.M.MM
.X.X.XMASX

Take a look at the little Elf's word search. How many times does XMAS appear?

Progress: 0 / 19600

State: 0

I ended up creating an array of all positions within the matrix, then brute-force checking each position and the surrounding coordinates for the matching characters.

This was very straightforward to implement, if a bit tedious.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const parser = z.array(z.string().transform((value) => value.split("")));
const values = parser.parse(input.split("\n"));

const positions: Array<[number, number]> = [];

values.forEach((value, i) => {
    value.forEach((_, j) => {
        positions.push([i, j]);
    });
});

function matchLeftRight(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x + 1]?.[y] === "M" &&
        values[x + 2]?.[y] === "A" &&
        values[x + 3]?.[y] === "S"
    );
}

function matchRightLeft(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x - 1]?.[y] === "M" &&
        values[x - 2]?.[y] === "A" &&
        values[x - 3]?.[y] === "S"
    );
}

function matchUpDown(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x]?.[y + 1] === "M" &&
        values[x]?.[y + 2] === "A" &&
        values[x]?.[y + 3] === "S"
    );
}

function matchDownUp(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x]?.[y - 1] === "M" &&
        values[x]?.[y - 2] === "A" &&
        values[x]?.[y - 3] === "S"
    );
}

function matchUpLeftDownRight(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x + 1]?.[y + 1] === "M" &&
        values[x + 2]?.[y + 2] === "A" &&
        values[x + 3]?.[y + 3] === "S"
    );
}

function matchUpRightDownLeft(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x - 1]?.[y + 1] === "M" &&
        values[x - 2]?.[y + 2] === "A" &&
        values[x - 3]?.[y + 3] === "S"
    );
}

function matchDownRightUpLeft(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x - 1]?.[y - 1] === "M" &&
        values[x - 2]?.[y - 2] === "A" &&
        values[x - 3]?.[y - 3] === "S"
    );
}

function matchDownLeftUpRight(x: number, y: number) {
    return (
        values[x]?.[y] === "X" &&
        values[x + 1]?.[y - 1] === "M" &&
        values[x + 2]?.[y - 2] === "A" &&
        values[x + 3]?.[y - 3] === "S"
    );
}

The Elf looks quizzically at you. Did you misunderstand the assignment?

Looking for the instructions, you flip over the word search to find that this isn't actually an XMAS puzzle; it's an X-MAS puzzle in which you're supposed to find two MAS in the shape of an X. One way to achieve that is like this:

1
2
3
M.S
.A.
M.S

Irrelevant characters have again been replaced with . in the above diagram. Within the X, each MAS can be written forwards or backwards.

Here's the same example from before, but this time all of the X-MASes have been kept instead:

1
2
3
4
5
6
7
8
9
10
.M.S......
..A..MSMS.
.M.S.MAA..
..A.ASMSM.
.M.S.M....
..........
S.S.S.S.S.
.A.A.A.A..
M.M.M.M.M.
..........

In this example, an X-MAS appears 9 times.

Flip the word search from the instructions back over to the word search side and try again. How many times does an X-MAS appear?

Progress: 0 / 19600

State: 0

Very similar to Part 1, but adjust the coordinates we're checking and the characters we're checking against.

This was actually a bit simpler becuase I didn't need to consider diagonals.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const parser = z.array(z.string().transform((value) => value.split("")));
const values = parser.parse(input.split("\n"));

const positions: Array<[number, number]> = [];

values.forEach((value, i) => {
    value.forEach((_, j) => {
        positions.push([i, j]);
    });
});

function matchLeftRight(x: number, y: number) {
    return (
        values[x]?.[y] === "A" &&
        values[x - 1]?.[y - 1] === "M" &&
        values[x + 1]?.[y - 1] === "S" &&
        values[x - 1]?.[y + 1] === "M" &&
        values[x + 1]?.[y + 1] === "S"
    );
}

function matchRightLeft(x: number, y: number) {
    return (
        values[x]?.[y] === "A" &&
        values[x - 1]?.[y - 1] === "S" &&
        values[x + 1]?.[y - 1] === "M" &&
        values[x - 1]?.[y + 1] === "S" &&
        values[x + 1]?.[y + 1] === "M"
    );
}

function matchUpDown(x: number, y: number) {
    return (
        values[x]?.[y] === "A" &&
        values[x - 1]?.[y - 1] === "M" &&
        values[x + 1]?.[y - 1] === "M" &&
        values[x - 1]?.[y + 1] === "S" &&
        values[x + 1]?.[y + 1] === "S"
    );
}

function matchDownUp(x: number, y: number) {
    return (
        values[x]?.[y] === "A" &&
        values[x - 1]?.[y - 1] === "S" &&
        values[x + 1]?.[y - 1] === "S" &&
        values[x - 1]?.[y + 1] === "M" &&
        values[x + 1]?.[y + 1] === "M"
    );
}

Part 1 Time	Part 1 Rank	Part 2 Time	Part 2 Rank
00:16:41	3,254	00:20:01	1,717

I considered two options for this:

Create new strings that were forwards, backwards, up, down, and diagonals, then do simple searches across those strings for matching text
Iterate over coordinates within the string matrix and check surrounding coordinates

After a few minutes of trying the first idea, I gave up and went for the second one, which was very straightforward to implement. Should've just done that from the start, but oh well.

Fletcher Easton

Day 4: Ceres Search

Part 1 – Prompt #

Part 1 – Solution #

Part 2 – Prompt #

Part 2 – Solution #

Recap #