DEV Community

Discussion on: Advent of Code 2019 Solution Megathread - Day 10: Monitoring Station

View post
Collapse
 
nordfjord profile image
Einar Norðfjörð •

JS, spent way too long on this because I was mutating state in a for loop!

const input = require('fs')
  .readFileSync(0)
  .toString()

const grid = input.split('\n').map(x => x.split('').map(x => x === '#'))

const asteroids = (() => {
  const result = []
  for (let y = 0; y < grid.length; ++y) {
    for (let x = 0; x < grid[0].length; ++x) {
      const point = { x, y, isAsteroid: grid[y][x] }
      if (point.isAsteroid) result.push(point)
    }
  }
  return result
})()

const angle = (x, y) => Math.atan2(x.y - y.y, x.x - y.x)
const distance = (x, y) => Math.sqrt((x.x - y.x) ** 2 + (x.y - y.y) ** 2)
const modulo = (x, n) => ((x % n) + n) % n

const radToDeg = rad => modulo(rad * (180 / Math.PI), 360)
const clockwiseDegrees = (x, y) => {
  const angleRad = angle(y, x)
  const angleInDegrees = radToDeg(angleRad)
  const degreesClockwise = modulo(angleInDegrees - 270, 360)
  return degreesClockwise
}

const descend = fn => (a, b) => {
  var aa = fn(a)
  var bb = fn(b)
  return aa > bb ? -1 : aa < bb ? 1 : 0
}
const ascend = fn => (a, b) => {
  var aa = fn(a)
  var bb = fn(b)
  return aa < bb ? -1 : aa > bb ? 1 : 0
}

function part1(asteroids) {
  const uniqueAsteroidDistances = asteroids.map(point => {
    const otherAsteroids = asteroids.filter(x => x !== point)
    const visibleCount = new Set(otherAsteroids.map(x => angle(point, x))).size
    return { point, visibleCount }
  })
  const maxAsteroids = uniqueAsteroidDistances.reduce(
    (p, v) => (p.visibleCount > v.visibleCount ? p : v),
    { visibleCount: 0 }
  )
  return maxAsteroids
}

function part2(asteroids, laserLocation, indexToFind) {
  const angles = asteroids
    .filter(x => x !== laserLocation)
    .map(p => {
      const angleDeg = clockwiseDegrees(laserLocation, p)
      return {
        angle: angleDeg,
        distance: distance(laserLocation, p),
        point: p
      }
    })
    .sort(ascend(p => p.angle))

  const grouped = angles
    .reduce((p, v) => {
      if (p.length === 0) {
        p[0] = [v]
      } else if (p[p.length - 1][0].angle === v.angle) {
        p[p.length - 1].push(v)
      } else {
        p.push([v])
      }
      return p
    }, [])
    .map(x => x.slice().sort(descend(x => x.distance)))

  const order = []
  for (let i = 0; i < angles.length; ++i) {
    const value = grouped[i % grouped.length].pop()
    if (value) order.push(value)
  }

  const toFind = order[indexToFind - 1]
  return toFind.point.x * 100 + toFind.point.y
}

const part1Answer = part1(asteroids)
console.log(part1Answer.visibleCount)
console.log(part2(asteroids, part1Answer.point, 200))