Day 8

prelude

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

import { inputDay } from "./lib/utilities.js"
const test = `............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............`.split("\n")
display(test)

const input = await inputDay(8, { parser: inp => inp.trim().split("\n") })

part 1

Parse the grid into an object containing locations of antennae

function getAntennae(m) {
  const antennae = {}
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      if (m[i][j] != ".") {
        if (!Object.hasOwn(antennae, m[i][j])) antennae[m[i][j]] = []
        antennae[m[i][j]].push([i, j])
      }
    }
  }
  return antennae
}
display(getAntennae(test))
display(getAntennae(input))

Today I decided to play with generators, so let's start with a generator for 2-combinations, since we're going to need to iterate over all pairs of antennae

function* comb(ps) {
  for (let i = 0; i < ps.length; i++) {
    for (let j = 0; j < i; j++) {
      yield [ps[i], ps[j]]
    }
  }
}
display([...comb(getAntennae(test).A)])

Now we can write a function that takes a list of locations for a single antenna, iterates over it, and generates antinodes for each pair

function* antinodes(as) {
  for (const [a, b] of comb(as)) {
    const dy = a[0] - b[0]
    const dx = a[1] - b[1]
    yield [a[0] + dy, a[1] + dx]
    yield [b[0] - dy, b[1] - dx]
  }
}
display([...antinodes(getAntennae(test).A)])

And a function to accept a list of locations for a single antenna, iterate over the antinodes, and limit them to ones contained in the map.

function* valid(as, height, width) {
  for (const [y, x] of antinodes(as)) {
    if (y >= 0 && y < height && x >= 0 && x < width) yield [y, x]
  }
}
display([...valid(getAntennae(test).A, test.length, test[0].length)])

We're going to get duplicate antennas, so how about a function to remove duplicates. This has horrible O(n) memory performance, but should do fine for us in this problem.

Because of javascript equality rules ([1] != [1]), we'll need to coerce our arrays into strings.

function dedupe(xs) {
  const seen = new Set()
  const ret = []
  for (const x of xs) {
    if (seen.has(String(x))) continue
    seen.add(String(x))
    ret.push(x)
  }
  return ret
}
display(dedupe([[1], [1], [2]]))

Now, finally, we can count all our antinodes

function allAntinodes(m) {
  return dedupe(
    Object.values(getAntennae(m)).flatMap(as => [
      ...valid(as, m.length, m[0].length),
    ]),
  )
}
display(allAntinodes(test).length)
display(allAntinodes(input).length)

part 2

Let's rewrite our antinode generator to yield points until they're invalid

function* antinodes2(as, height, width) {
  const valid = ([y, x]) => y >= 0 && y < height && x >= 0 && x < width
  for (const [a, b] of comb(as)) {
    const dy = a[0] - b[0]
    const dx = a[1] - b[1]
    let i = 0
    while (true) {
      const p1 = [a[0] + dy * i, a[1] + dx * i]
      const p2 = [b[0] - dy * i, b[1] - dx * i++]
      if (valid(p1)) yield p1
      if (valid(p2)) yield p2
      if (!valid(p1) && !valid(p2)) break
    }
  }
}
const gen = antinodes2(getAntennae(test).A, test.length, test[0].length)
display(gen.next().value)
display(gen.next().value)
display(gen.next().value)

And now we can answer part 2

function allAntinodes2(m) {
  return dedupe(
    Object.values(getAntennae(m)).flatMap(as => [
      ...antinodes2(as, m.length, m[0].length),
    ]),
  )
}
display(allAntinodes2(test).length)
display(allAntinodes2(input).length)

visualize part 2


const map = []
const grid = input.map(row => row.split(""))
for (const [y, x] of allAntinodes2(input)) {
  grid[y][x] = "#"
}
document.getElementById("map").innerText = grid
  .map(row => row.join(""))
  .join("\n")

const map = []
const m = input
const size = 640
const [colw, colh] = [size / m[0].length, size / m.length]
const ctx = c.getContext("2d")
ctx.font = "10px monospace"
ctx.clearRect(0, 0, size, size)
const grid = input.map(row => row.split(""))
for (let i = 0; i < grid.length; i++) {
  for (let j = 0; j < grid[0].length; j++) {
    if (grid[i][j] == ".") continue
    ctx.fillStyle = "#FEFE62"
    ctx.fillText(grid[i][j], j * colw, (i + 1) * colh)
  }
}
const antennae = Object.values(getAntennae(m))
let i = 1
for (const as of antennae) {
  // ctx.fillRect(6 * colw, 2 * colh, colw, colh)
  setTimeout(() => {
    for (const [y, x] of as) {
      for (const [yy, xx] of antinodes2(as, m.length, m[0].length)) {
        setTimeout(() => {
          ctx.fillStyle = "#D35FB7"
          ctx.fillRect(xx * colw, yy * colh, colw, colh)
          ctx.fillStyle = "#4269d0"
          ctx.fillRect(x * colw, y * colh, colw, colh)
        }, i++ * 1000)
      }
      ctx.fillStyle = "#D35FB7"
      ctx.fillRect(x * colw, y * colh, colw, colh)
    }
  }, i++ * 1000)
}