Day03.hs

-- |
-- Module      : AOC.Challenge.Day03
-- Copyright   : (c) Justin Le 2018
-- License     : BSD3
--
-- Maintainer  : justin@jle.im
-- Stability   : experimental
-- Portability : non-portable
--
-- Day 3.  See "AOC.Solver" for the types used in this module!

module AOC.Challenge.Day03 (
    day03a
  , day03b
  ) where

import           AOC.Common    (freqs, firstJust, clearOut)
import           AOC.Solver    ((:~>)(..))
import           Control.Monad (guard)
import           Data.Char     (isDigit)
import           Data.Ix       (range)
import           Data.Map      (Map)
import           Data.Maybe    (mapMaybe)
import           Linear        (V2(..))
import           Text.Read     (readMaybe)
import qualified Data.Map      as M

-- | x and y
type Coord = V2 Int

-- | Claim ID and rectangle
data Claim = C { _cId   :: Int
               , _cRect :: Rect
               }

-- | Start <x,y>, and size <w,h>
data Rect = R { _rStart :: Coord
              , _rSize  :: Coord
              }

-- | Attempt to parse a line into @(Int, Rect)@ (a claim ID #, and the
-- rectangle claimed)
parseLine :: String -> Maybe Claim
parseLine = mkLine
          . mapMaybe readMaybe
          . words
          . clearOut (not . isDigit)
  where
    mkLine [i,x0,y0,w,h] = Just $ C i (R (V2 x0 y0) (V2 w h))
    mkLine _             = Nothing

-- | Get a list of all coordinates within a given rectangle specification
tiles :: Rect -> [Coord]
tiles (R start size) = range (start, start + size - 1)

-- | Generate a frequency map of tiles to number of claims at that tile
layTiles :: [Rect] -> Map Coord Int
layTiles = freqs . concatMap tiles

-- | Lends itself pretty well to a functional approach.
--
-- 1. Lay the tiles.
-- 2. Get all the frequencies at each time
-- 3. Filter for the frequencies greater than 2
-- 4. Count them
day03a :: [Rect] :~> Int
day03a = MkSol
    { sParse = traverse (fmap _cRect . parseLine) . lines
    , sShow  = show
    , sSolve = Just
             . length           -- > how many?
             . filter (>= 2)    -- > only frequencies >= 2
             . M.elems          -- > get all frequencies
             . layTiles         -- > lay the tiles
    }

-- | Once we lay our tiles, we find the first claim that has no overlaps.
day03b :: [Claim] :~> Int
day03b = MkSol
    { sParse = traverse parseLine . lines
    , sShow  = show
    , sSolve = \ts ->
        let tilesClaimed = layTiles (_cRect <$> ts) -- > get all tiles claimed frequency map
        in  firstJust (noOverlap tilesClaimed) ts   -- > find the ID that is not overlapping
    }

-- | Given a map of tiles claimed (and how many are claiming that spot) and
-- a claim ID and rectangle, check if all of the claim's rectangles are
-- alone in the map (are claimed by only one claim).
--
-- If yes, return the ID of the claim.
noOverlap
    :: Map Coord Int
    -> Claim
    -> Maybe Int
noOverlap tilesClaimed C{..} = _cId <$ guard (all isAlone (tiles _cRect))
  where
    isAlone c = M.lookup c tilesClaimed == Just 1