Advent of Code 2024, Day 4

2025-01-10 (updated 2025-01-14)

Update See Appendix B below for a commentary.

Part One

This puzzle is a word search. You are asked how many times does the word “XMAS” appear.

The first 10 lines and 50 columns of my puzzle input are the following. The total input is 140 × 140.

XSXMAAXXSSMMMXMXSXMSXMXSAMXSXMASMMSSMMSASXSAAXAAMX
XXAMMSMMXMAMAASXSAMAMSAMASASMSASAAAAAXSASAMMMXSMXS
SSSMAAXAAXAMMXSASXMAMMASAMXSAMAXMMSMMMMAMXMAXXAAAS
XAAMSSSSMSSXSAMAMAMXMSXMASAXMMAMXMXMMAMAMXSAMSMMMS
MSMMAXXAAXAAMXMASAMXASXSXMASXSXMASXAXMAXXXMMMMAAAX
XMASMMSMMMMMMAXAXMSMMSAMXAMXXASMAMMMMSSSMSSMASXMMS
SSMMMAMXAAAAXMMMSMXAXMAMXSXMAMAMASAMXXAAAAAMXSAAXA
MAASMSMSSSSSMSAAAXMAMMXMAXAMXXMSASASMMSMMSSMASXMMS
SSMMAAAAAXXAASMSMMMSMSSMMXAMAMXXXSMMXAAXMMAXAMMSMA
AAAMXMASMMMMMMAAXAAXAAXAMSMMASMMMMASMSSSSSSMXSAAMA

Reading all the lines into a matrix (list of lists) of characters is a one-liner.

wordSearch = Characters /@ Import["input.txt", "Lines"]

In order to count occurrences of “XMAS”, I coded a standard word search algorithm. At a given position i, j (row, column), I look for the word “XMAS” in all 8 directions: left to right (east), bottom left to top right (north-east), bottom to top (north), etc. While iterating over i and j, when I find an “X” at the current position, I look for the remaining “MAS” in a given direction using the masDirQ function. Function masDirQ first checks if “XMAS” fits in the that direction.

directions = {{0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1},
	{1, 0}, {1, 1}}

masChars = {"M", "A", "S"}

masDirQ[grid_, m_, n_, i_, j_, {di_, dj_}] :=
	1 ≤ i + 3 di ≤ m && 1 ≤ j + 3 dj ≤ n && AllTrue[Range[3],
		(grid[[i + # di, j + # dj]] == masChars[[#]])&]

Pair di, dj in each call to masDirQ comes from the pairs in directions as seen in the following code.

I tried to implement the iterative search in functional style (e.g., no state, no loops). In that sense, I coded the iteration logic in a helper function called countXmasIter. I think I read about this in the Lisp edition of SCIP. Note that Boole converts a boolean to integer, and Total accounts for several matches (in different directions) at a same position i, j. Function countXmasIter was designed to work with higher-order function NestWhile[f, expr, test] that evaluates f[f[…f[expr]…]] until test yields False.

countXmasIter[{grid_, m_, n_, i_, j_, num_}] :=
	{
		grid, m, n,
		If[j < n, i, i + 1],
		If[j < n, j + 1, 1],
		num +
			If[grid[[i, j]] == "X",
				directions //
				Map[masDirQ[grid, m, n, i, j, #]&] //
				Map[Boole] //
				Total
				,
				0
			]
	}

countXmas[wordSearch_] :=
	With[{n = Length[wordSearch], m = Length[First[wordSearch]]},
		Last[NestWhile[countXmasIter, {wordSearch, n, m, 1, 1, 0},
			(#[[4]] ≤ n)&]]
	]

numXmas = countXmas[wordSearch]

The number of times that “XMAS” appear is 2575.

Part Two

It is revealed that the puzzle is not about finding the word “XMAS” but finding two instances of “MAS” in the shape of an “X”, i.e., an “X-MAS”.

Here we don’t need directions, just checking if each diagonal contains “M” and “S”. I wrote the helper function countXmasIter2 to iterate from row 2 to row n - 1 (likewise for columns) because an “X-MAS” is always 3 × 3.

xmasQ[diag1_, diag2_] :=
	Count[diag1, "M"] == 1 && Count[diag1, "S"] == 1 && Count[diag2,
		"M"] == 1 && Count[diag2, "S"] == 1

countXmasIter2[{grid_, m_, n_, i_, j_, num_}] :=
	{
		grid, m, n,
		If[j < n - 1, i, i + 1],
		If[j < n - 1, j + 1, 2],
		num +
			If[grid[[i, j]] == "A",
				xmasQ[grid[[i - #, j + #]]& /@ {-1, 1},
					grid[[i - #, j - #]]& /@ {-1, 1}] // Boole
				,
				0
			]
	}

countXmas2[wordSearch_] :=
	With[{n = Length[wordSearch], m = Length[First[wordSearch]]},
		Last[NestWhile[countXmasIter2, {wordSearch, n, m, 2, 2, 0},
			(#[[4]] ≤ n - 1)&]]
	]

numXmas2 = countXmas2[wordSearch]

There was a total of 2041 “X-MAS”.

Appendix A – Using recursion

I tried using recursion (when a function calls itself) for the iterative process since it is the most natural way to implement it in functional programming (NestWhile is new to me).

My recursive solution for the first part was the following:

countXmasIterRec[grid_, m_, n_, i_, j_, num_, niter_] :=
	If[i ≤ 140,
		countXmasIterRec[
			grid, m, n,
			If[j < n, i, i + 1],
			If[j < n, j + 1, 1],
			num +
				If[grid[[i, j]] == "X",
					directions //
					Map[masDirQ[grid, m, n, i, j, #]&] //
					Total
					,
					0
				]
			,
			niter + 1
		]
		,
		{num, niter}
	]

countXmasRec[wordSearch_] :=
	countXmasIterRec[wordSearch, Length[wordSearch],
		Length[First[wordSearch]], 1, 1, 0, 0]

numXmasRec = countXmasRec[wordSearch]

I was sure that my recursive function was correct; however, I got the following error in Wolfram Language:

$IterationLimit::itlim: Iteration limit of 4096 exceeded.

My first attempt to solve the issue was to increase the iteration limit. Since the word search grid is 140 × 140 = 19600, I tried with $IterationLimit = 20000. This wasn’t enough, so I tried with 40000 and got the correct result. Then I changed $IterationLimit until I found the exact value of 39205 iterations.

In order to check my code, I added the niter variable to count the recursive function calls and the result was 19600!

Interestingly, (140 × 140) × 2 + 5 = 39205, so I don’t know what is considered an iteration in Wolfram Language. If I find out, I will update the post.

Appendix B – The root of all evil

In Day 5 I acknowledged that Day 4 solutions were inelegant because they sacrifice readability in favor of machine efficiency. I should have used a better approach: using the Table function to count/find XMAS/X-MAS for each cell and find the total with the (surprise!) Total function. I won’t update these solutions as a reminder of my foolishness. Still, I learned a lot while coding the recursive solutions.

I finish with the following quote from Donald Knuth’s The Art of Computer Programming:

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.