✨ Day 04 - Ceres Search Link to heading

Today was the first challenging day of the year, and it took me a while to get a working solution. Be prepared for some yank!

Today, we have to help a little Elf working on the Ceres monitoring station to decipher his word search:
We have a list of 140x140 characters (10x10 for the example) that contains the word XMAS in many forms, forwards, backwards, vertical, diagonal and overlapping.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Part 1 Link to heading

Part one is - in theory - very simple. We have to count the occurrences of XMAS in the text. I treated the strings as a Matrix of chars, as the input will always be same-sided. For forward and backward in the horizontal rows it’s very straight-forwards, just use a simple regex like (?=(XMAS|SAMX)) and sum the finds of the rows:

val regex = Regex("(?=(XMAS|SAMX))")

val horizontal = input.lines()

horizontal.sumOf { re.findAll(it).count() }

But what do we do now for the vertical and diagonal lines? Some might have taken a smarter approach for doing this, but I decided to just transpose the char matrix and reuse the same regex. Sadly, the kotlin standard library does not provide Matrix functions (I could have used Multik, but I think that would have been overkill and normal transposition is not enough as you will see in a moment), so I had to create my own, which was simple enough:

inline fun <reified T> List<List<T>>.transpose(): List<List<T>> = List(this[0].size) { i -> List(this.size) { j -> this[j][i] } }

and was then able to just repeat my code from before:

val regex = Regex("(?=(XMAS|SAMX))")

val vertical = input.lines().map { it.toList() }.transpose().map { it.joinToString { "" } }

vertical.sumOf { re.findAll(it).count() }

I know the double map is not very aesthetically pleasing and may introduce overhead, but I wanted to make the function abstract to maybe reuse it later on.

Now, for the diagonal lines, I had to think a bit more about how to “transpose” (It’s technically not transposing anymore, but for the lack of a better term we’ll just call it “diagonal transpose”) them, and with the help of some friendly Large Language Models I was able to come up with this bad boy

inline fun <reified T> List<List<T>>.diagonalTranspose(): List<List<T>> {
    val rows = this.size
    val cols = this.first().size

    return (0 until cols).map { col ->
        generateSequence(0 to col) { (i, j) -> (i + 1) to (j - 1) }
            .takeWhile { (i, j) -> i < rows && j >= 0 }
            .map { (i, j) -> this[i][j] }
            .toList()
    } + (1 until rows).map { row ->
        generateSequence(row to cols - 1) { (i, j) -> (i + 1) to (j - 1) }
            .takeWhile { (i, j) -> i < rows && j >= 0 }
            .map { (i, j) -> this[i][j] }
            .toList()
    }
}

And a lightly modified version to transpose on the anti-diagonal:

inline fun <reified T> List<List<T>>.antiDiagonalTranspose(): List<List<T>> {
    val rows = this.size
    val cols = this.first().size

    return (cols - 1 downTo 0).map { col ->
        generateSequence(0 to col) { (i, j) -> (i + 1) to (j + 1) }
            .takeWhile { (i, j) -> i < rows && j < cols }
            .map { (i, j) -> this[i][j] }
            .toList()
    } + (1 until rows).map { row ->
        generateSequence(row to 0) { (i, j) -> (i + 1) to (j + 1) }
            .takeWhile { (i, j) -> i < rows && j < cols }
            .map { (i, j) -> this[i][j] }
            .toList()
    }
}

And now I could just sum the occurrences in the 4 matrices using the aforementioned regex and I was done!

horizontal.sumOf { re.findAll(it).count() } +
vertical.sumOf { re.findAll(it).count() } +
diagonalLtoR.sumOf { re.findAll(it).count() } +
diagonalRtoL.sumOf { re.findAll(it).count() }

Which outputs 18 and gets us our first star for today!

Part 2 Link to heading

Now, after we did all this mumbo jumbo just because an elf can’t write like a normal person, he then has the audacity to tell us that we made a massive mistake and have to start over. That little sh*thead. Basically, instead of searching for XMAS, we have to search for two words MAS in an X-Configuration like this:

S.M
.A.
S.M

I first started with a very complicated approach containing more matrix operations, complicated regex’s and weird calculation, but after taking a brief pause and talking to a colleague that already solved today’s puzzle, I just went ahead and checked every A in the text for the matching character configuration around it:

var result = 0
(1..lines.size - 2).forEach { i ->
    (1..lines[i].length - 2).forEach inner@{ j ->
        if (lines[i][j] != 'A') return@inner
        if (!((lines[i - 1][j - 1] == 'S' && lines[i + 1][j + 1] == 'M') || (lines[i - 1][j - 1] == 'M' && lines[i + 1][j + 1] == 'S'))) return@inner
        if (!((lines[i + 1][j - 1] == 'S' && lines[i - 1][j + 1] == 'M') || (lines[i + 1][j - 1] == 'M' && lines[i - 1][j + 1] == 'S'))) return@inner
        result++
    }
}

Which finally gave us the second star for today

Today was the most challenging for this year, I was already concerned that this year’s puzzles will be disappointing, but today took a good couple of hours to solve. Very excited for the following days!