{-# 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