Day 10: Monitoring Station

https://adventofcode.com/2019/day/10



In [1]:

    
inputLines = lines <$> readFile "input/day10.txt"

Represent asteroid positions and connections with 2d vectors



In [2]:

    
type Vector = (Int, Int)



In [3]:

    
asteroidConnection :: Vector -> Vector -> Vector
asteroidConnection (x1, y1) (x2, y2) = (x2 - x1, y2 - y1)

Parse the given map



In [4]:

    
import Control.Monad (guard)

parseMap :: [String] -> [Vector]
parseMap allLines = do
    (y, line) <- zip [0..] allLines
    (x, point) <- zip [0..] line
    guard $ point == '#'
    return (x, y)

Find connections with the same direction

Dividing the x and y coordinate of a vector by their greatest common divisor makes it possible to find asteroids which are in the same direction from a given origin.



In [5]:

    
direction :: Vector -> Vector
direction (dx, dy) = (dx `div` g, dy `div` g)
    where
        g = gcd dx dy

Find the number of visible asteroids from a given origin

This is equal to the number of distinct directions for connections from the origin to other asteroids.



In [6]:

    
import qualified Data.Set as Set

numberOfVisibleAsteroids :: Vector -> [Vector] -> Int
numberOfVisibleAsteroids origin = countDistinct . map getDirection . filter (/=origin)
    where
        countDistinct = Set.size . Set.fromList
        getDirection = direction . asteroidConnection origin

Find the best position

bestPosition returns a pair which consists of the maximum number of visible asteroids and the corresponding origin positions.



In [7]:

    
bestPosition asteroids = maximum . map resultForOrigin $ asteroids
    where
        resultForOrigin origin = (numberOfVisibleAsteroids origin asteroids, origin)

Verify first given example



In [8]:

    
bestPosition . parseMap $ [ ".#..#"
                          , "....."
                          , "#####"
                          , "....#"
                          , "...##" ]









    





(8,(3,4))

Verify last given example



In [9]:

    
largeMap = parseMap [ ".#..##.###...#######"
                    , "##.############..##."
                    , ".#.######.########.#"
                    , ".###.#######.####.#."
                    , "#####.##.#.##.###.##"
                    , "..#####..#.#########"
                    , "####################"
                    , "#.####....###.#.#.##"
                    , "##.#################"
                    , "#####.##.###..####.."
                    , "..######..##.#######"
                    , "####.##.####...##..#"
                    , ".#####..#.######.###"
                    , "##...#.##########..."
                    , "#.##########.#######"
                    , ".####.#.###.###.#.##"
                    , "....##.##.###..#####"
                    , ".#.#.###########.###"
                    , "#.#.#.#####.####.###"
                    , "###.##.####.##.#..##" ]



In [10]:

    
bestPosition largeMap









    





(210,(11,13))

Solution, part 1



In [11]:

    
bestPosition . parseMap <$> inputLines









    





(340,(28,29))

Part 2

Find the annihilation order for a given list of asteroids. TODO: cleanup!



In [12]:

    
import Data.Function (on)
import Data.List (sortOn, sortBy, groupBy)

annihilationOrder :: [Vector] -> [Vector]
annihilationOrder asteroids =
    let
        (_, bestPos) = bestPosition asteroids
        
        manhattanDistance :: Vector -> Int
        manhattanDistance = uncurry ((+) `on` abs) . asteroidConnection bestPos
        
        sortedByDistance = sortOn manhattanDistance $ filter (/=bestPos) asteroids
        
        compareClockwise :: Vector -> Vector -> Ordering
        compareClockwise asteroid1 asteroid2 =
            let
                angle (x, y) = if phi < 0 then phi + 2 * pi else phi
                    where
                        phi = (atan2 `on` fromIntegral) x (-y)
                        
                compareAngle = compare `on` (angle . asteroidConnection bestPos)
            in compareAngle asteroid1 asteroid2
        
        sortedClockwise = sortBy compareClockwise sortedByDistance
        
        sortedByAnnihilation = map snd $ sortOn fst $ concatMap (zip [0..]) $ groupBy ((==) `on` (direction . asteroidConnection bestPos)) sortedClockwise
    in sortedByAnnihilation

Verify given example for large map



In [13]:

    
examples = [1, 2, 3, 10, 20, 50, 100, 199, 200, 201, 299]

f [] [] = []
f (e:es) (x:xs)
    | e == fst x = x:f es xs
    | e > fst x = f (e:es) xs

f examples $ zip [1..] (annihilationOrder largeMap)









    





[(1,(11,12)),(2,(12,1)),(3,(12,2)),(10,(12,8)),(20,(16,0)),(50,(16,9)),(100,(10,16)),(199,(9,6)),(200,(8,2)),(201,(10,9)),(299,(11,1))]

Solution, part 2



In [14]:

    
uncurry ((+) . (*100)) . (!! 199) . annihilationOrder . parseMap <$> inputLines