Day 4

prelude

https://adventofcode.com/2024/day/4

import { inputDay, transpose } from "./lib/utilities.js"

Really ugly answers today! Nothing in here is as clean as I'd like it to be.

part 1

const test = `MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX`

Let's write a function to convert our string to a matrix, and parse today's test string and full input

function parser(s: string): any[][] {
  return s.split("\n").map(row => row.split(""))
}

const t = parser(test)
display(t)

const input = await inputDay(4, { parser })

brute-force

I initially tried to something fancier (read on for that), but settled on the simple brute-force solution:

function count2(m) {
  let total = 0
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      // horizontal
      if (m[i][j] == "X" && m[i]?.[j+1] == "M" && m[i]?.[j+2] == "A" && m[i]?.[j+3] == "S")       total += 1
      if (m[i][j] == "S" && m[i]?.[j+1] == "A" && m[i]?.[j+2] == "M" && m[i]?.[j+3] == "X")       total += 1
      // vertical
      if (m[i][j] == "X" && m[i+1]?.[j] == "M" && m[i+2]?.[j] == "A" && m[i+3]?.[j] == "S")       total += 1
      if (m[i][j] == "S" && m[i+1]?.[j] == "A" && m[i+2]?.[j] == "M" && m[i+3]?.[j] == "X")       total += 1
      // diag right
      if (m[i][j] == "X" && m[i+1]?.[j+1] == "M" && m[i+2]?.[j+2] == "A" && m[i+3]?.[j+3] == "S") total += 1
      if (m[i][j] == "S" && m[i+1]?.[j+1] == "A" && m[i+2]?.[j+2] == "M" && m[i+3]?.[j+3] == "X") total += 1
      // diag left
      if (m[i][j] == "X" && m[i+1]?.[j-1] == "M" && m[i+2]?.[j-2] == "A" && m[i+3]?.[j-3] == "S") total += 1
      if (m[i][j] == "S" && m[i+1]?.[j-1] == "A" && m[i+2]?.[j-2] == "M" && m[i+3]?.[j-3] == "X") total += 1
    }
  }
  return total
}
display(count2(t))
display(count2(input))

rotations

This part is the one I didn't finish! It still seems conceptually right to me, and the rotate function seems to work, but i'm missing a few matches in the result.

We could count this in eight directions, which is tedious but not difficult. Instead, let's figure out how to rotate the matrix so we can just write two checks, then spin the matrix around four times to find our total.

Rotation of a matrix can be accomplished by transposing it, then reversing the columns. We've already got a transpose function, so let's reuse it:

/** rotate the matrix 90° clockwise */
function rotate(matrix: any[][]) {
  const width = matrix[0].length
  return transpose(matrix).map(row => row.map((_, col) => row[width - col - 1]))
}

For illustrative purposes, let's write a function to show our matrix, and rotate it a few times

function show2(ms) {
  return Plot.plot({
    height: 250,
    width: 190 * ms.length,
    y: { tickFormat: () => "", tickSize: 0, reverse: true },
    x: { tickFormat: () => "", tickSize: 0 },
    insetRight: 60 * (ms.length - 1),
    marks: [
      Plot.text(
        ms.flatMap((m, mi) => m.map((row, rowi) => [mi, rowi, row.join("")])),
        {
          y: d => d[1],
          x: d => d[0],
          text: d => d[2],
          fontFamily: "monospace",
          fontSize: 20,
          textAnchor: "start",
        },
      ),
    ],
  })
}
display(show2([t, rotate(t), rotate(rotate(t))]))

Now we can count the XMAS occurrences in any horizontal or vertical direction plus any diagonal direction, rotate the matrix four times, and sum the total to get our answer

function count(m) {
  let total = 0
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      if (m[i].slice(j, j + 4).join("") == "XMAS") total += 1
      if (
        m[i]?.[j] == "X" &&
        m[i + 1]?.[j + 1] == "M" &&
        m[i + 2]?.[j + 2] == "A" &&
        m[i + 3]?.[j + 3] == "S"
      )
        total += 1
    }
  }
  return total
}
display(
  count(t) +
    count(rotate(t)) +
    count(rotate(rotate(t))) +
    count(rotate(rotate(rotate(t)))),
)

That looks right, so let's try it on our input:

// 2415 is too low
display(
  count(input) +
    count(rotate(input)) +
    count(rotate(rotate(input))) +
    count(rotate(rotate(rotate(input)))),
)

Unfortunately that's too low! I don't quite know why, but it's missing a few correct answers.

part 2

Another brute-force counter:

function count3(m) {
  let total = 0
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      if (m[i][j] != 'A') continue;
      if (m[i-1]?.[j-1] == "M" && m[i-1]?.[j+1] == "M" && m[i+1]?.[j-1] == "S" && m[i+1]?.[j+1] == "S")
        total += 1
      if (m[i-1]?.[j-1] == "M" && m[i-1]?.[j+1] == "S" && m[i+1]?.[j-1] == "M" && m[i+1]?.[j+1] == "S")
        total += 1
      if (m[i-1]?.[j-1] == "S" && m[i-1]?.[j+1] == "M" && m[i+1]?.[j-1] == "S" && m[i+1]?.[j+1] == "M")
        total += 1
      if (m[i-1]?.[j-1] == "S" && m[i-1]?.[j+1] == "S" && m[i+1]?.[j-1] == "M" && m[i+1]?.[j+1] == "M")
        total += 1
    }
  }
  return total
}
display(count3(t))
display(count3(input))

visualize part 1

const m = test.split("\n").map(row => row.split(""))
const width = m[0].length
let cells = []
const n = Math.floor(((now / 1000) % width) * m.length)
const hits = vizcount(m, n)
for (let i = 0; i < m.length; i++) {
  for (let j = 0; j < width; j++) {
    const bg = i * width + j == n ? "background:white" : ""
    const fg = hits.includes(`${i},${j}`) ? "color: #D35FB7" : ""
    const s = [bg, fg].join(";")
    cells.push(html`<span style="${s}">${m[i][j]}</span>`)
  }
  cells.push(html`<br />`)
}
display(html`<span style="font-family: monospace">${cells}</span>`)

visualize part 2

const m = test.split("\n").map(row => row.split(""))
const width = m[0].length
let cells = []
const n = Math.floor(((now / 1000) % width) * m.length)
const hits = vizcount2(m, n)
for (let i = 0; i < m.length; i++) {
  for (let j = 0; j < width; j++) {
    const bg = i * width + j == n ? "background:white" : ""
    const fg = hits.includes(`${i},${j}`) ? "color: #D35FB7" : ""
    const s = [bg, fg].join(";")
    cells.push(html`<span style="${s}">${m[i][j]}</span>`)
  }
  cells.push(html`<br />`)
}
display(
  html`<span style="font-family: monospace; line-height: .8">${cells}</span>`,
)

// const m = input
// const width = m[0].length
// let cells = []
// const n = Math.floor(((now / 1000) % width) * m.length)
// const hits = count4(m, n)
// display(hits)
// for (let i = 0; i < m.length; i++) {
//   for (let j = 0; j < width; j++) {
//     const bg = i * width + j == n ? "background:white" : ""
//     const fg = hits.includes(`${i},${j}`) ? "color: pink" : ""
//     const s = [bg, fg].join(";")
//     cells.push(html`<span style="${s}; font-size:10px">${m[i][j]}</span>`)
//   }
//   cells.push(html`<br />`)
// }
// display(html`<span style="font-family: monospace">${cells}</span>`)

const m = test.split("\n").map(row => row.split(""))
const ctx = pt2.getContext("2d")
ctx.clearRect(0, 0, 1000, 1000)
ctx.font = "25px monospace"
const width = m[0].length
let cells = []
const n = Math.floor(((now / 1000) % width) * m.length)
// const n = 1
const hits = vizcount2(m, n)
const rowH = 20
const colW = 20
for (let i = 0; i < m.length; i++) {
  for (let j = 0; j < width; j++) {
    if (i * width + j == n) {
      ctx.fillStyle = "#4269d0"
      ctx.fillRect(j * colW, i * rowH + rowH * 0.1, 20, 20)
    }
    ctx.fillStyle = hits.includes(`${i},${j}`) ? "#D35FB7" : "#FFFFFF33"
    const c = hits.includes(`${i},${j}`) ? "🎄" : m[i][j]
    ctx.fillText(c, j * colW, i * rowH + rowH)
  }
}