MATL Advent of Code

December 4, 2024

Part 1

Solution (39 bytes): 4:"G@X!t0ysnhYay!sn:2&YSh4YC!'XMAS'Xmvs

Online Demo

Explanation

To solve the word search, we take the input character array as a 2D matrix of characters, we then use im2col to create a sliding window of 4 characters (the size of our match string XMAS). We then count the number of times that the sliding window matched the match string exactly. The sliding window only operates in a single direction (down the columns) and we need to match words in all 4 directions but also along the diagonals.

For example, for the following input:

ABCD
EFGH
IJKL
MNOP
QRST

The sliding windows look like this (one per row)

AEIM
EIMQ
BFJN
FJNR
CGKO
GKOS
DHLP
HLPT

To handle the four primary directions, we add an outer for loop that rotates the input character array by 90 degrees (G@X!) each time before searching for matches.

To handle the diagonals, we create a version of the input where each row is shifted by 1, effectively making each diagonal a column in our input where we then apply the sliding window technique. We have to apply padding to each row of the input to prevent wrap-around of the shifting operation since MATL uses the circshift under the hood.

The padded and subsequently shifted matrix looks like the following:

      ABCD
       EFGH
        IJKL
         MNOP
          QRST

For each 90 degree rotation of the input, we horizontally concatenate the rotated matrix with the shifted version of the rotated matrix to search both columns and the diagonals simultaneously. This increases execution time, but reduces the code size.

The concatenated matrix (for a single rotation) that we search using the sliding window approach is shown below:

ABCD      ABCD
EFGH       EFGH
IJKL        IJKL
MNOP         MNOP
QRST          QRST

The annotated code is shown below:

4:"           % Loop 4 times (once for each direction)
  G@X!        % For each loop, rotate the input by 90 x (loop index) degrees (A)
  t           % Duplicate the rotated matrix, A
  0ysnh       % Create an array that is [0, nRows(A)]
  Ya          % Apply horizontal padding to each row (nRows of padding)
  y!sn:       % Create an array that is [1..nColumns(A)]
  2&YS        % Shift each row of the padded matrix right of the one above it
  h           % Horizontally concatenate the rotated and the shifted matrices
  4YC!        % Perform a 4-element sliding window operation
  'XMAS'      % The string literal that we're searching for 'XMAS'
  Xm          % Find the sliding windows that match, 0 if no match, 1 if match
  v           % Vertically concatenate this boolean array with all previous rotations
  s           % Sum the result, essentially keeping a running count of matches
              % Implicitly display the result

---