--- Day 4: Ceres Search ---
"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 waysXMASmight appear, where irrelevant characters have been replaced with.:
..X... .SAMX. .A..A. XMAS.S .X....The actual word search will be full of letters instead. For example:
MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASXIn this word search,
XMASoccurs a total of18times; here's the same word search again, but where letters not involved in anyXMAShave been replaced with.:....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.XMASXTake a look at the little Elf's word search. How many times does
XMASappear?
show i: read0 `4.txt "MMMSXXMASM" "MSAMXMSMSA" "AMXSXMAAMM" "MSAMASMSMX" "XMASAMXAMM" "XXAMMXXAMA" "SMSMSASXSS" "SAXAMASAAA" "MAMMMXMMMM" "MXMXAXMASX"
There are several approaches here. One would be to keep the data as a matrix. The other, which I will take, will be to flatten it, and deal with the flattened representation. Here, we can use sv and vs to convert to/from multidimensional indices and flat indices.
Firstly, we need to prepend a dummy character to each line, it doesn't inadvertently create extra solutions when joining. Then, store the line length, and join.
show n: 1 + count first i; show f: raze "." ,/: i 11 ".MMMSXXMASM.MSAMXMSMSA.AMXSXMAAMM.MSAMASMSMX.XMASAMXAMM.XXAMMXXAMA.SMSMSASXS..
Now, we can treat searching for patterns as searching in this flat array, with various offsets.
First of all, what are the offsets required for our 4x4 search? We can consider starting at the top left corner of a 4x4 grid. In order to avoid looking at the same blocks of 4 twice, we search for the first column, row, and the two diagonals.
XXXX
XXX.
XXX.
X..X
We can check the indices from this 4x4 grid.
4 4#til 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
So the indices we need are (0 1 2 3;0 4 8 12;0 5 10 15;3 6 9 12).
These can be converted into 2d coordinates using 4 vs.
4 vs ids: (0 1 2 3;0 4 8 12;0 5 10 15;3 6 9 12) 0 0 0 0 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 1 2 3 3 2 1 0
Now, we can search for a pattern with given offsets. Let's take the first one as an example.
f (til count f) +/: 0 1 2 3 ".MMMSXXMASM.MSAMXMSMSA.AMXSXMAAMM.MSAMASMSMX.XMASAMXAMM.XXAMMXXAMA.SMSMSASXS.. "MMMSXXMASM.MSAMXMSMSA.AMXSXMAAMM.MSAMASMSMX.XMASAMXAMM.XXAMMXXAMA.SMSMSASXSS.. "MMSXXMASM.MSAMXMSMSA.AMXSXMAAMM.MSAMASMSMX.XMASAMXAMM.XXAMMXXAMA.SMSMSASXSS... "MSXXMASM.MSAMXMSMSA.AMXSXMAAMM.MSAMASMSMX.XMASAMXAMM.XXAMMXXAMA.SMSMSASXSS.S..
Now we can look for occurrences of "XMAS"
all "XMAS" = f (til count f) +/: 0 1 2 3 00000010000000000000000000000000000000000000010000000000000000000000000000000..
We can now apply this to all 4 of our indices, and search for both "XMAS" and "SAMX".
The first step is to convert our indices into the correct offsets for our input.
n sv 4 vs ids 0 1 2 3 0 11 22 33 0 12 24 36 3 13 23 33
Now, we can define a function to search for these patterns.
S:{(f(til count f)+\:/:n sv count[y] vs x)in(y;reverse y)}
And apply it to our indices, looking for "XMAS"
S[ids; "XMAS"]
The total sum of all occurrences is our desired solution.
sum sum S[ids; "XMAS"] 18i
--- Part Two ---
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
XMASpuzzle; it's anX-MASpuzzle in which you're supposed to find twoMASin the shape of anX. One way to achieve that is like this:M.S .A. M.SIrrelevant characters have again been replaced with
.in the above diagram. Within theX, eachMAScan be written forwards or backwards.Here's the same example from before, but this time all of the
X-MASes have been kept instead:.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-MASappears9times.Flip the word search from the instructions back over to the word search side and try again. How many times does an
X-MASappear?
Now, we need to search for a different pattern. Let's generate the 3x3 grid to see what the indices should be.
3 3#til 9 0 1 2 3 4 5 6 7 8
So the new indices are (0 4 8;2 4 6).
ids:(0 4 8;2 4 6)
We can reuse our search function to find the new occurrences, this time looking for "MAS"
S[ids; "MAS"] 00100000000000000110000010100000000100000000000000000000000010000001010101000.. 00100000000000000110000010100000000001000000001000010000000000000001010101100..
This time both of them need to occur, so we use all before summing.
sum all S[ids; "MAS"] 9i
i: read0 `4.txt
n: 1 + count first i; f: raze "." ,/: i
ids: (0 1 2 3;0 4 8 12;0 5 10 15;3 6 9 12)
S:{(f(til count f)+\:/:n sv count[y] vs x)in(y;reverse y)}
/part 1
sum sum S[ids; "XMAS"]
/part 2
ids:(0 4 8;2 4 6)
sum all S[ids; "MAS"]