 # Advent of Code 2019 Solution Megathread - Day 10: Monitoring Station 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

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

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  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 == "#" and asteroid_2 == "#":
angle = math.atan2(asteroid_2 - asteroid_1, asteroid_2 - asteroid_1) % (2 * math.pi)

solution = len(max(asteroid_visibility.values(), key=len))
print(solution)
`````` Einar Norðfjörð

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

``````const input = require('fs')
.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.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 clockwiseDegrees = (x, y) => {
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 = [v]
} else if (p[p.length - 1].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]
}

`````` 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 == "#":

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)

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.
"""
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:
elif asteroid.x > 0 and asteroid.y <= 0:
elif asteroid.x <= 0 and asteroid.y < 0:
else:

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:

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

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

`````` 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()
`````` 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()
`````` Jon Bristow

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"

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.x * 100 + it.y
}
}
}

fun main() {
println(mostVisible(Day10.fileData))
println(destruction(Day10.fileData))
}
`````` Jon Bristow

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"

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
.let { it.x * 100 + it.y }
}
}

fun main() {
println(mostVisible(Day10.fileData))
println(destruction(Day10.fileData))
}
`````` 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 === '#') {
}
});
});

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)) {
} 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);
``````  