63 lines
1.8 KiB
Haskell
63 lines
1.8 KiB
Haskell
{-# OPTIONS_GHC -O2 #-}
|
|
{-# LANGUAGE TupleSections #-}
|
|
import Common
|
|
import Data.List.Split (splitOn)
|
|
import Data.List (find)
|
|
import Data.Char (isNumber)
|
|
import Data.Maybe (fromJust, isJust)
|
|
|
|
type SensorData = (Pos, Int)
|
|
|
|
parseLine :: String -> SensorData
|
|
parseLine l = (sensorPos, sensorPos `taxicabDist` beaconPos)
|
|
where
|
|
sensorPos = getPos left
|
|
beaconPos = getPos right
|
|
|
|
getPos :: String -> Pos
|
|
getPos s = (x, y)
|
|
where [x, y] = map (read . filter isNumber) $ filter (isJust . find isNumber) $ words s
|
|
|
|
[left, right] = splitOn ":" l
|
|
|
|
beaconMaxX :: Int
|
|
beaconMaxX = 4000000
|
|
beaconMaxY :: Int
|
|
beaconMaxY = 4000000
|
|
|
|
-- manual recursion for extra speed
|
|
canContainBeacon :: [SensorData] -> Pos -> Bool
|
|
canContainBeacon ((sensorPos, sensorRange):xs) p = p `taxicabDist` sensorPos > sensorRange && (canContainBeacon xs p)
|
|
canContainBeacon [] _ = True
|
|
|
|
dedup a b
|
|
| a == b = [a]
|
|
| otherwise = [a, b]
|
|
|
|
possibleSpots :: SensorData -> [Pos]
|
|
possibleSpots ((x, y), dist) = concatMap drawLine [y - dist - 1 .. y + dist + 1]
|
|
where
|
|
drawLine y' = map (, y') (dedup (x - (dist - yDist) - 1) (x + (dist - yDist) + 1))
|
|
where
|
|
yDist = abs $ y' - y
|
|
|
|
findBeaconInPositions :: [SensorData] -> [Pos] -> Maybe Pos
|
|
findBeaconInPositions sensors = find canContainBeacon'
|
|
where
|
|
-- does this help performance???
|
|
canContainBeacon' = canContainBeacon sensors
|
|
|
|
findBeacon :: [SensorData] -> Pos
|
|
findBeacon sensors = fromJust $ findBeaconInPositions sensors positions
|
|
where
|
|
positions = filter (\(x, y) -> x >= 0 && x <= beaconMaxX && y >= 0 && y <= beaconMaxY) $ concatMap possibleSpots sensors
|
|
|
|
getTuningFrequency :: Pos -> Int
|
|
getTuningFrequency (x, y) = x * 4000000 + y
|
|
|
|
main = interact $
|
|
show
|
|
. getTuningFrequency
|
|
. findBeacon
|
|
. map parseLine
|
|
. lines |