loading...
Cover image for Advent of Code 2019 Solution Megathread - Day 10: Monitoring Station

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

jbristow profile image Jon Bristow Updated on ・2 min read

No IntCodes today, just too many asteroids.

Day 10 - The Problem

We home in on the distress call to find the elves trying to find the best place to monitor the asteroids. Of course we need to stop and help them, as this is our best chance of getting through the asteroid belt in one piece.

Part 1 has us scanning for a new monitoring station location, optimized for the best view of the spinning rocks.

With slopes and distances safely under our belt, the elves decide to just blow everything up. Part 2 is doing some calculations to settle a bet on the results of their spinning asteroid destruction laser beam.

Ongoing Meta

Dev.to List of Leaderboards

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 09
  • javascript x 3
  • python x 3
  • c
  • clojure
  • kotlin
  • ruby
  • swift
Completion Stats

By applying a best-fit descending power trend-line to the 1 and 2 star columns on the stats page, my estimates predict:

2 stars on day 25: 6358 people

1 star on day 25: 420 people. Nice

If you're still going, take heart in that you are in a rapidly dwindling pool of people.

Doing other questionable statistics gives me: 415/6248

Discussion

pic
Editor guide
Collapse
fossheim profile image
Sarah

Part 1 of day 10:

from input import asteroids
import math
from collections import defaultdict


asteroids_coordinates = []
for row in range(0, len(asteroids)):
    for column in range(0,len(asteroids[row])):
        asteroids_coordinates.append((row, column, asteroids[row][column]))


asteroid_visibility = defaultdict(set)
for asteroid_1 in asteroids_coordinates:
    for asteroid_2 in asteroids_coordinates:
        if asteroid_1 == asteroid_2:
            continue

        if asteroid_1[2] == "#" and asteroid_2[2] == "#":
            angle = math.atan2(asteroid_2[0] - asteroid_1[0], asteroid_2[1] - asteroid_1[1]) % (2 * math.pi)
            asteroid_visibility[asteroid_1].add(angle)


solution = len(max(asteroid_visibility.values(), key=len))
print(solution)
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))
Collapse
rpalo profile image
Ryan Palo

Things have settled down a little bit since Christmas, so I've got some time to actually complete AOC2019. Better 4 months late than never! Here's my solution to Day 10. Had some trouble deciding how to handle vertical slopes gracefully, and switching back and forth from global to relative coordinates, but finally got it handled.

"""Figure out the best asteroid to look at other asteroids.  And then BLAST THEM!"""

from dataclasses import dataclass
from math import gcd
from typing import List, Set


@dataclass(frozen=True)
class Point:
    """An X, Y coordinate on a grid"""
    x: int
    y: int


def parse(text: str) -> Set[Point]:
    """Expects a 2D grid of characters.  '#' denote asteroids.

    Note: Here, Y+ is down.
    """
    asteroids = set()
    rows = text.splitlines()
    for y, row in enumerate(rows):
        for x, cell in enumerate(row):
            if cell == "#":
                asteroids.add(Point(x, y))

    return asteroids


def find_best(asteroids: Set[Point]) -> (Point, int):
    """Finds the asteroid that can see the most other asteroids.

    Returns that asteroid and how many others it can see.
    """
    scores = [(a, count_visible(a, asteroids)) for a in asteroids]
    return max(scores, key=lambda x: x[1])


def count_visible(base: Point, asteroids: Set[Point]) -> int:
    """Counts how many asteroids are in line of sight."""
    return sum(1 for asteroid in asteroids if can_see(base, asteroid, asteroids))


def can_see(a: Point, b: Point, asteroids: Set[Point]) -> bool:
    """Determines whether or not an asteroid can see another in an asteroid field."""

    # Asteroids can't see themselves.
    if a == b:
        return False

    dx = b.x - a.x
    dy = b.y - a.y

    divisor = gcd(dy, dx)

    if divisor != 0:
        # Line isn't vertical or horizontal.  Get basic slope.
        dx //= divisor
        dy //= divisor
    else:
        # Line is vertical or horizontal.  Divisor becomes simply
        # the magnitude of the non-zero component.
        divisor = max(dx, dy)

    # Step over every cell on the line between a and b and see if
    # it's an asteroid.  If any of them are, then b can't be seen from a.
    for step in range(1, divisor):
        if Point(a.x + step*dx, a.y + step*dy) in asteroids:
            return False

    return True


@dataclass(order=True)
class LaserPriority:
    """A helper class for prioritizing which asteroids get blasted first.

    Quadrant assumes X+ is right and Y+ is up, with base at the origin.
    Slope uses Y/X, but gets multiplied by -1 so that Laser Priorities
    get sorted based on quadrant and then slope in descending order.
    """
    quadrant: int
    slope: float


def laser_priority_sort_key(asteroid: Point) -> LaserPriority:
    """Prioritize asteroids based on how they clock around the origin.

    Starting at Y+ (up) and going CW.
    This function assumes all asteroids being compared are visible.
    """
    result = LaserPriority(0, 0)

    # Simulate vertical slope as ">> size of grid"
    # because ~~~InFiNiTy Is HaRd FoR cOmPuTeRs~~~
    if asteroid.x == 0:
        result.slope = 1000
    else:
        result.slope = asteroid.y / asteroid.x

    result.slope *= -1  # Flip so sort goes largest to smallest

    if asteroid.x >= 0 and asteroid.y > 0:
        result.quadrant = 1
    elif asteroid.x > 0 and asteroid.y <= 0:
        result.quadrant = 2
    elif asteroid.x <= 0 and asteroid.y < 0:
        result.quadrant = 3
    else:
        result.quadrant = 4

    return result


def create_laser_plan(base: Point, asteroids: Set[Point]) -> List[Point]:
    """Specify the order in which asteroids get BLASTED, assuming we start
    at 12 o'clock and go CW, blasting only one asteroid at a time for a
    particular clocking before moving on.
    """
    asteroids = asteroids - {base}

    # Convert everything so that Y+ is up and base is at 0, 0
    relative_asteroids = {Point(a.x - base.x, -(a.y - base.y))
                          for a in asteroids}

    plan = []
    # Blast asteroids in rounds, removing the ones that get blasted
    # after every cycle
    while relative_asteroids:
        visible = {a for a in relative_asteroids if can_see(
            Point(0, 0), a, relative_asteroids)}
        plan += sorted(visible, key=laser_priority_sort_key)
        relative_asteroids -= visible

    # Unconvert back to global coordinates with Y+ down
    plan = [Point(base.x + a.x, base.y - a.y) for a in plan]
    return plan


if __name__ == "__main__":
    with open("data/day10.txt") as f:
        grid = f.read()

    asteroids = parse(grid)
    best, score = find_best(asteroids)
    print(f"Best is {best} with {score} visible.")

    plan = create_laser_plan(best, asteroids)
    answer = plan[199]  # O-based counting!!!

    print(f"Lucky number 200 is {answer}.")
    print(f"Magic number is {answer.x * 100 + answer.y}.")
Collapse
rizzu26 profile image
Rizwan

Done with part one in swift. need bit more time for part two


struct Point: CustomStringConvertible, Equatable, Hashable {
    var x: Int
    var y: Int

    var description: String {
        get {
            return "X: \(self.x) Y: \(self.y)"
        }
    }
}

var grid: [Point] = []
input.enumerated().map { (x,layer) in
    layer.enumerated().map { (y,point) in
        if point == "#" {
            grid.append(Point.init(x: x, y: y))
        }
    }
}

extension Array where Element : Hashable {
    var unique: [Element] {
        return Array(Set(self))
    }
}

func angle(_ x: Point, _ y: Point) -> Double {
    return atan2(Double(x.y - y.y), Double(x.x - y.x))
}

func partOne() {
    let result = grid.map { point -> Int in
        let filter = grid.filter { (aPoint) -> Bool in
            return aPoint != point
        }

        return filter.map { p in
            return angle(p, point)
        }.unique.count
    }.max()?.description
    print("Result is :\(result ?? "")")
}

partOne()
Collapse
rizzu26 profile image
Rizwan

Took so much time for part two. Actually went ahead and rewrote part one as well. Solution in swift


struct Point: CustomStringConvertible, Equatable, Hashable {
    var x: Int
    var y: Int

    var description: String {
        get {
            return "X: \(self.x) Y: \(self.y)"
        }
    }
}

var grid: [Point] = []
_ = input.enumerated().map { (y,layer) in
    _ = layer.enumerated().map { (x,point) in
        if point == "#" {
            grid.append(Point.init(x: x, y: y))
        }
    }
}

func angleBtw(_ x: Point, _ y: Point) -> Double {
    return (atan2(Double(x.y - y.y), Double(x.x - y.x)) * 180) / Double.pi
}
struct Los: CustomStringConvertible{
    var point: Point
    var angle: Double

    var description: String {
        get {
            return "point: \(self.point) angle: \(self.angle)"
        }
    }
}

func getAstroidsInLOS(_ base: Point) -> [Los] {
    var los: [Los] = []
    let astroids = grid.filter{ $0 != base }
    _ = astroids.map { point in
        let angle = angleBtw(base, point)
        var blocked = false
        _ = los.map { aLos in
            if aLos.angle == angle {
                blocked = true
            }
        }

        if !blocked {
            los.append(Los.init(point: point, angle: angle))
        }
    }
    return los
}

func partOne() {
    let result = grid.map { point -> Int in
        return getAstroidsInLOS(point).count
    }.max()
    print("Part One answer is :\(result ?? 0)")
}

func partTwo() {
    let root = grid.map { point -> (Point,Int) in
        return (point,getAstroidsInLOS(point).count)
    }.max { (p1, p2) -> Bool in
        return p1.1 < p2.1
        }!.0
    var los = getAstroidsInLOS(root)
    los.sort{ a, b in a.angle < b.angle}
    let base = los.firstIndex { (aLos) -> Bool in
        return aLos.angle == 90
    }
    let result = los[199 + (base ?? 0) - los.count]
    print("Part Two is \(result.point.x * 100 + result.point.y)")
}

partOne()
partTwo()
Collapse
jbristow profile image
Jon Bristow Author

An ugly kotlin solution.

I'll clean it up tomorrow.

import Day10.destruction
import Day10.mostVisible
import java.nio.file.Files
import java.nio.file.Paths
import kotlin.math.*

object Day10 {

    private fun slope(a: Point, b: Point) = (a.y - b.y).toDouble() / (a.x - b.x).toDouble()

    private fun distance(a: Point, b: Point) = sqrt(
        abs(a.x.toDouble() - b.x.toDouble()).pow(2.0)
                + abs(a.y.toDouble() - b.y.toDouble()).pow(2.0)
    )

    private fun List<String>.allAsteroids() =
        mapIndexed { y, row -> row.mapIndexed { x, c -> (x to y) to c } }
            .flatten()
            .filter { (_, v) -> v == '#' }
            .map { it.first }

    fun mostVisible(data: List<Point>) =
        data.map { station ->
            val others = data.filter { it != station }
            val right = others.filter { it.y == station.y && it.x > station.x }
            val left = others.filter { it.y == station.y && it.x < station.x }
            val down = others.filter { it.x == station.x && it.y > station.y }
            val up = others.filter { it.x == station.x && it.y < station.y }
            val upRight = others.filter { it.x > station.x && it.y < station.y }.groupBySlope(station)
            val downRight = others.filter { it.x > station.x && it.y > station.y }.groupBySlope(station)
            val upLeft = others.filter { it.x < station.x && it.y < station.y }.groupBySlope(station)
            val downLeft = others.filter { it.x < station.x && it.y > station.y }.groupBySlope(station)

            station to (
                    min(1, right.size) +
                            min(1, left.size) +
                            min(1, down.size) +
                            min(1, up.size) +
                            upRight.sumBy { min(1, it.second.size) } +
                            upLeft.sumBy { min(1, it.second.size) } +
                            downRight.sumBy { min(1, it.second.size) } +
                            downLeft.sumBy { min(1, it.second.size) }

                    )
        }.maxBy { it.second }

    private fun List<Point>.groupBySlope(station: Point) =
        map { it to slope(station, it) }
            .groupBy { it.second }.toList()

    private const val FILENAME = "src/main/resources/day10.txt"
    val fileData = Files.readAllLines(Paths.get(FILENAME)).allAsteroids()

    fun destruction(data: List<Point>): Int {
        val station = 20 to 20
        val others = data.filter { it != station }
        val right = others.filter { it.y == station.y && it.x > station.x }
            .sortedBy { distance(it, station) }
        val left = others.filter { it.y == station.y && it.x < station.x }
            .sortedBy { distance(it, station) }
        val down = others.filter { it.x == station.x && it.y > station.y }
            .sortedBy { distance(it, station) }
        val up = others.filter { it.x == station.x && it.y < station.y }
            .sortedBy { distance(it, station) }
        val upRight = others.filter { it.x > station.x && it.y < station.y }
            .map { p -> (atan(slope(p, station)) + PI / 2) to p }
            .groupBy { it.first }
            .map { (k, v) -> k to v.map { it.second }.sortedBy { distance(it, station) } }

        val downRight = others.filter { it.x > station.x && it.y > station.y }
            .map { p -> (atan(slope(p, station)) + PI / 2) to p }
            .groupBy { it.first }
            .map { (k, v) -> k to v.map { it.second }.sortedBy { distance(it, station) } }
        val upLeft = others.filter { it.x < station.x && it.y < station.y }
            .map { p -> (atan(slope(p, station)) + 3 * PI / 2) to p }
            .groupBy { it.first }
            .map { (k, v) -> k to v.map { it.second }.sortedBy { distance(it, station) } }

        val downLeft = others.filter { it.x < station.x && it.y > station.y }
            .map { p -> (atan(slope(p, station)) + 3 * PI / 2) to p }
            .groupBy { it.first }
            .map { (k, v) -> k to v.map { it.second }.sortedBy { distance(it, station) } }

        val groupedAsteroids = listOf(
            0.0 to up,
            PI to down,
            PI / 2 to right,
            3 * PI / 2 to left
        ) + upLeft + upRight + downLeft + downRight

        val biggestList = groupedAsteroids.maxBy { it.second.size }?.second?.size ?: 0
        return (0..biggestList).fold(emptyList<Point>() to groupedAsteroids.sortedBy { it.first }) { (destroyed, remaining), i ->
            (destroyed + remaining.flatMap { it.second.take(1) }) to (remaining.map { it.first to it.second.drop(1) })
        }.first.let {

            it[199].x * 100 + it[199].y
        }
    }
}


fun main() {
    println(mostVisible(Day10.fileData))
    println(destruction(Day10.fileData))
}
Collapse
jbristow profile image
Jon Bristow Author

Ahh... that's better... More Sealed Classes/Discriminated Unions to the rescue. Managed to cut a lot of duplicated code out.

import Day10.destruction
import Day10.mostVisible
import arrow.core.andThen
import java.nio.file.Files
import java.nio.file.Paths
import kotlin.math.PI
import kotlin.math.abs
import kotlin.math.atan
import kotlin.math.pow
import kotlin.math.sqrt

data class Point(val x: Int, val y: Int)

private fun Point.slope(b: Point) = (y - b.y).toDouble() / (x - b.x).toDouble()
private fun Point.distance(b: Point) =
    sqrt(abs(x.toDouble() - b.x.toDouble()).pow(2.0) + abs(y.toDouble() - b.y.toDouble()).pow(2.0))

private fun Point.anglePair(entry: Map.Entry<EuclideanGrouping, List<Point>>) = entry.key.anglePair(this, entry.value)

private fun Point.countByGroup(entry: Map.Entry<EuclideanGrouping, List<Point>>) = entry.key.count(this, entry.value)

sealed class EuclideanGrouping
object Down : EuclideanGrouping()
object DownLeft : EuclideanGrouping()
object DownRight : EuclideanGrouping()
object Left : EuclideanGrouping()
object Right : EuclideanGrouping()
object Up : EuclideanGrouping()
object UpLeft : EuclideanGrouping()
object UpRight : EuclideanGrouping()

fun Point.mapEuclideanGroup(other: Point): EuclideanGrouping {
    return when {
        other.x > x && other.y > y -> DownRight
        other.x > x && other.y < y -> UpRight
        other.x > x && other.y == y -> Right
        other.x < x && other.y > y -> DownLeft
        other.x < x && other.y < y -> UpLeft
        other.x < x && other.y == y -> Left
        other.x == x && other.y > y -> Down
        other.x == x && other.y < y -> Up
        else -> throw Error("Invalid point comparison: $this to $other")
    }
}

fun Point.sortByDistanceFromKeyValue(entry: Map.Entry<Double, List<Point>>) =
    entry.key to entry.value.sortedBy(this::distance)

fun Point.radiansConverter(offset: Double) = { p: Point -> (atan(p.slope(this)) + offset) }

private fun EuclideanGrouping.anglePair(station: Point, list: List<Point>) =
    when (this) {
        Up -> listOf(0.0 to list)
        Down -> listOf(PI to list)
        DownLeft, UpLeft -> list.groupBy(station.radiansConverter(3 * PI / 2))
            .map(station::sortByDistanceFromKeyValue)
            .toList()
        DownRight, UpRight -> list.groupBy(station.radiansConverter(PI / 2))
            .map(station::sortByDistanceFromKeyValue)
            .toList()
        Left -> listOf(3 * PI / 2 to list)
        Right -> listOf(PI / 2 to list)
    }

fun EuclideanGrouping.count(station: Point, list: List<Point>) = when (this) {
    Up, Down, Left, Right -> list.take(1).count()
    DownLeft, DownRight, UpLeft, UpRight -> list.groupBy { station.slope(it) }.count { (_, v) -> v.any() }
}

object Day10 {

    private const val FILENAME = "src/main/resources/day10.txt"
    val fileData = Files.readAllLines(Paths.get(FILENAME)).onlyAsteroids()

    private fun List<String>.onlyAsteroids() =
        mapIndexed { y, row -> row.mapIndexed { x, c -> Point(x, y) to c } }.flatten()
            .filter(Pair<Point, Char>::second andThen '#'::equals)
            .map(Pair<Point, Char>::first)

    fun mostVisible(data: List<Point>) =
        data.map { station ->
            station to data.asSequence().filterNot(station::equals).groupBy(station::mapEuclideanGroup).asSequence()
                .sumBy(station::countByGroup)
        }.maxBy { it.second }

    fun destruction(data: List<Point>): Int {
        val station = Point(20, 20)
        val groupedAsteroids =
            data.asSequence().filterNot(station::equals)
                .groupBy(station::mapEuclideanGroup)
                .flatMap(station::anglePair)

        val initial = emptyList<Point>() to groupedAsteroids.sortedBy { it.first }
        return (0..(groupedAsteroids.maxBy { it.second.size }?.second?.size ?: 0))
            .fold(initial) { (destroyed, remaining), _ ->
                val nextDestroyed = destroyed + remaining.flatMap { (_, list) -> list.take(1) }
                val nextRemaining = remaining.map { (angle, list) -> angle to list.drop(1) }
                nextDestroyed to nextRemaining
            }.first[199]
            .let { it.x * 100 + it.y }
    }
}

fun main() {
    println(mostVisible(Day10.fileData))
    println(destruction(Day10.fileData))
}
Collapse
maxart2501 profile image
Massimo Artizzu

Things are getting complicated now! I like it!

In the first part I tried an arithmetic approach, trying to find - for each asteroid - if there was another one in line with the target location. JavaScript as usual:

const PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; // Enough primes...
const spaceMap = input.trim().split('\n');

const asteroids = new Set();
spaceMap.flatMap((line, row) => {
  line.split('').forEach((char, column) => {
    if (char === '#') {
      asteroids.add(column + ',' + row);
    }
  });
});

function simplifyFraction(numerator, denominator) {
  for (const prime of PRIMES) {
    while (numerator % prime === 0 && denominator % prime === 0) {
      numerator /= prime;
      denominator /= prime;
    }
  }
  return [numerator, denominator];
}

function countVisibile(coords, _, astArray) {
  const [ row, column ] = coords.split(',').map(Number);
  const visible = astArray.filter(astCoords => {
    if (astCoords !== coords) {
      const [ astRow, astColumn ] = astCoords.split(',').map(Number);
      const diffRow = astRow - row;
      const diffColumn = astColumn - column;
      const [ baseColumn, baseRow ] = simplifyFraction(diffColumn, diffRow);
      let checkRow = row + baseRow;
      let checkColum = column + baseColumn;
      while (checkRow !== astRow || checkColum !== astColumn) {
        if (asteroids.has(checkColum + ',' + checkRow)) {
          break;
        }
        checkRow += baseRow;
        checkColum += baseColumn;
      }
      return checkRow === astRow && checkColum === astColumn;
    }
  });
  return visible.length;
}

const asteroidCounts = [ ...asteroids ].map(countVisibile);

console.log(Math.max(...asteroidCounts));

The second part showed that it would have been too complex. So I just converted all the coordinates in polar, sorted them out and counted to the 200th asteroid. Finally, converted back to orthogonal coordinates:

// `asteroids` defined as above...
const stationRow = 29;
const stationColumn = 23;

const polarCoords = new Map();
asteroids.forEach(([ column, row ]) => {
  if (column === stationColumn && row === stationRow) {
    return;
  }
  const diffColumn = stationColumn - column;
  const diffRow = stationRow - row;
  const theta = (Math.atan2(diffColumn, -diffRow) + Math.PI) % (Math.PI * 2);
  const rho = Math.sqrt(diffColumn ** 2 + diffRow ** 2);
  if (polarCoords.has(theta)) {
    polarCoords.get(theta).add(rho);
  } else {
    polarCoords.set(theta, new Set([ rho ]));
  }
});

function* getTargets() {
  const sortedAngles = new Set([ ...polarCoords.keys() ].sort((a, b) => a - b));
  while (sortedAngles.size) {
    for (const theta of sortedAngles) {
      const rhos = polarCoords.get(theta);
      if (rhos.size === 1) {
        sortedAngles.delete(theta);
        yield [theta, ...rhos];
      } else {
        const nearest = Math.min(...rhos);
        rhos.delete(nearest);
        yield [theta, nearest];
      }
    }
  }
}

function toOrtho(theta, rho) {
  return [
    stationColumn + Math.round(Math.sin(theta) * rho),
    stationRow - Math.round(Math.cos(theta) * rho)
  ]
}

const targets = getTargets();
let value;
for (let i = 0; i < 200; i++) {
  ({ value } = targets.next());
}
const [ resColumn, resRow ] = toOrtho(...value);
console.log(resColumn * 100 + resRow);
Collapse
neilgall profile image
Neil Gall

Python today. And what a tough problem, especially part 2. Glad that's over.

Collapse
rizzu26 profile image
Rizwan

@jon Guess you added wrong title for this post. It should be Day 10!

Collapse
jbristow profile image
Jon Bristow Author

I was fixing it just as you noticed! That’s what I get for posting past my bedtime.

Collapse
thibpat profile image
Thibaut Patel

JS, I like and hate that you could pass part 1 with a bug in your code, that got me thinking for a while when doing part 2!!