-- | -- Module : AOC.Challenge.Day02 -- Copyright : (c) Justin Le 2018 -- License : BSD3 -- -- Maintainer : justin@jle.im -- Stability : experimental -- Portability : non-portable -- -- Day 2. See "AOC.Solver" for the types used in this module! module AOC.Challenge.Day02 ( day02a , day02b ) where import AOC.Common (freqs, perturbations) import AOC.Prelude import AOC.Solver ((:~>)(..)) import Control.Monad (guard) import Data.Containers.ListUtils (nubOrd) import Data.Functor.Foldable import Data.Functor.Foldable.TH import Data.List (find) import Data.Witherable (catMaybes) import qualified Data.Map as M import qualified Data.Set as S -- | We compute a frequency map of all of the characters in a string, and -- then get all of the frequencies that happened for each line. -- -- Then we build a frequency map of the frequencies! day02a :: [String] :~> Int day02a = MkSol { sParse = Just . lines , sShow = show , sSolve = mulTwoThree -- > lookup how many times -- 2 and 3 occurred, and -- multiply . freqs -- > build a frequency map of -- all seen frequencies . concatMap -- > get the frequency map of (nubOrd . M.elems . freqs) -- each string, and then -- combine all of the -- frequencies into a big -- list of frequencies } where mulTwoThree m = (*) <$> M.lookup 2 m <*> M.lookup 3 m -- newtype TrieF = -- newtype TrieF a = TF (Map Char a) -- invariant: all a's are unique -- deriving (Functor, Foldable, Traversable, Show, Eq) -- data TrieF k v a = TNowF v (Map k a) -- | TLaterF (NEMap k a) -- deriving (Functor, Foldable, Traversable, Show, Eq) -- | The main work is in 'firstNeighbor', which looks thorugh a list of -- items and finds the first item whose neighbor was already seen. -- -- Then we take the two "almost matching" strings and filter out all of the -- characters that aren't the same, using 'zipWith' and 'catMaybes'. day02b :: [String] :~> String day02b = MkSol { sParse = Just . lines , sShow = id , sSolve = fmap (uncurry onlySame) . firstNeighbor } where onlySame xs = catMaybes . zipWith (\x y -> x <$ guard (x == y)) xs -- | Find the first string in a list that is a neighbor of a previous -- string. firstNeighbor :: [String] -> Maybe (String, String) firstNeighbor = go S.empty where go seen (x:xs) = case find (`S.member` seen) (neighbors x) of Just n -> Just (x, n) Nothing -> go (x `S.insert` seen) xs go _ [] = Nothing -- | Get all one-character neighbors of a given string neighbors :: String -> [String] neighbors = perturbations (const ['a'..'z'])