{-# Language ImportQualifiedPost, QuasiQuotes #-}
{-|
Module      : Main
Description : Day 6 solution
Copyright   : (c) Eric Mertens, 2019
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2019/day/6>

-}
module Main (main) where

import Advent
import Control.Applicative
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map

-- | >>> :main
-- 110190
-- 343
main :: IO ()
IO ()
main =
  do [([Char], [Char])]
inp <- [format|2019 6 (%s%)%s%n)*|]

     let orbits :: Map [Char] [Char]
orbits = [([Char], [Char])] -> Map [Char] [Char]
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [ ([Char]
y,[Char]
x) | ([Char]
x,[Char]
y) <- [([Char], [Char])]
inp]

     Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> IO ()) -> Int -> IO ()
forall a b. (a -> b) -> a -> b
$ [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [ [[Char]] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Map [Char] [Char] -> [Char] -> [[Char]]
forall a. Ord a => Map a a -> a -> [a]
path Map [Char] [Char]
orbits [Char]
i) | ([Char]
_,[Char]
i) <- [([Char], [Char])]
inp ]

     let you :: [Char]
you    = Map [Char] [Char]
orbits Map [Char] [Char] -> [Char] -> [Char]
forall k a. Ord k => Map k a -> k -> a
Map.! [Char]
"YOU"
         san :: [Char]
san    = Map [Char] [Char]
orbits Map [Char] [Char] -> [Char] -> [Char]
forall k a. Ord k => Map k a -> k -> a
Map.! [Char]
"SAN"
         t1 :: [[Char]]
t1     = Map [Char] [Char] -> [Char] -> [[Char]]
forall a. Ord a => Map a a -> a -> [a]
path Map [Char] [Char]
orbits [Char]
you
         t2 :: [[Char]]
t2     = Map [Char] [Char] -> [Char] -> [[Char]]
forall a. Ord a => Map a a -> a -> [a]
path Map [Char] [Char]
orbits [Char]
san
         common :: [[Char]]
common = [[Char]] -> [[Char]] -> [[Char]]
forall a. Eq a => [a] -> [a] -> [a]
intersect [[Char]]
t1 [[Char]]
t2

     Int -> IO ()
forall a. Show a => a -> IO ()
print ([[Char]] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [[Char]]
t1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ [[Char]] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [[Char]]
t2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* [[Char]] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [[Char]]
common)

path :: Ord a => Map a a -> a -> [a]
path :: forall a. Ord a => Map a a -> a -> [a]
path Map a a
m a
i =
  case a -> Map a a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup a
i Map a a
m of
    Maybe a
Nothing -> []
    Just a
j  -> a
i a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Map a a -> a -> [a]
forall a. Ord a => Map a a -> a -> [a]
path Map a a
m a
j