{-# LANGUAGE TupleSections #-}
import Common
import Data.List.Split (splitOn)
import Data.List (find)
import Data.Char (isNumber)
import Data.Maybe (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

scanY :: Int
scanY = 2000000

getMinX :: SensorData -> Int
getMinX ((x, y), dist) = x - dist
getMaxX :: SensorData -> Int
getMaxX ((x, y), dist) = x + dist

getXScanRange :: [SensorData] -> (Int, Int)
getXScanRange sensors = (minX, maxX)
  where
    minX = minimum $ map getMinX sensors
    maxX = maximum $ map getMaxX sensors

-- manual recursion for extra speed
canContainBeacon :: [SensorData] -> Pos -> Bool
canContainBeacon ((sensorPos, sensorRange):xs) p = p `taxicabDist` sensorPos > sensorRange && (canContainBeacon xs p)
canContainBeacon [] _ = True

countContainsBeacon :: [SensorData] -> Int
countContainsBeacon sensors = count (not . canContainBeacon sensors) $ map (, scanY) [minX .. maxX]
  where
    (minX, maxX) = getXScanRange sensors

main = interact $
  show
  . flip (-) 1
  . countContainsBeacon
  . map parseLine
  . lines