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)
}