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

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)

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

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

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

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

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

// `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);