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

<https://adventofcode.com/2018/day/23>

Part 2 enumerates maxmimal cliques and checks them for optimality.

-}
module Main (main) where

import Advent (countBy, format)
import Advent.Coord3 (manhattan, Coord3(..), origin)
import Advent.MaxClique (maxCliques)
import Data.List (maximumBy)
import Data.Ord (comparing)

-- | Print the answers to day 23
--
-- >>> :main
-- 219
-- 83779034
main :: IO ()
IO ()
main =
 do [(Int, Int, Int, Int)]
inp <- [format|2018 23 (pos=<%d,%d,%d>, r=%d%n)*|]
    let bots :: [Bot]
bots = [Coord3 -> Int -> Bot
Bot (Int -> Int -> Int -> Coord3
C3 Int
x Int
y Int
z) Int
r | (Int
x,Int
y,Int
z,Int
r) <- [(Int, Int, Int, Int)]
inp]
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Bot] -> Int
part1 [Bot]
bots)
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Bot] -> Int
part2 [Bot]
bots)

-- | Compute the number of nanobots (including self) that are in
-- range of the nanobot with the largest radius.
part1 :: [Bot] -> Int
part1 :: [Bot] -> Int
part1 [Bot]
bots = (Bot -> Bool) -> [Bot] -> Int
forall (f :: * -> *) a. Foldable f => (a -> Bool) -> f a -> Int
countBy (Bot -> Coord3 -> Bool
botSees Bot
strongBot (Coord3 -> Bool) -> (Bot -> Coord3) -> Bot -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bot -> Coord3
botPos) [Bot]
bots
  where
    strongBot :: Bot
strongBot = (Bot -> Bot -> Ordering) -> [Bot] -> Bot
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
maximumBy ((Bot -> Int) -> Bot -> Bot -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Bot -> Int
botRadius) [Bot]
bots

-- | Compute the minimum distance to the point that is in range of the
-- maximum number of nanobots.
--
-- To find this region we enumerate the maximal cliques of the graph and compare
-- each to find the ones with the largest clique size then with the minimal distance
-- to the origin.
part2 :: [Bot] -> Int
part2 :: [Bot] -> Int
part2 = (Int, Int) -> Int
forall a b. (a, b) -> b
snd ((Int, Int) -> Int) -> ([Bot] -> (Int, Int)) -> [Bot] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> (Int, Int)
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum ([(Int, Int)] -> (Int, Int))
-> ([Bot] -> [(Int, Int)]) -> [Bot] -> (Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Bot] -> (Int, Int)) -> [[Bot]] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map [Bot] -> (Int, Int)
characterize ([[Bot]] -> [(Int, Int)])
-> ([Bot] -> [[Bot]]) -> [Bot] -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bot -> Bot -> Bool) -> [Bot] -> [[Bot]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
maxCliques Bot -> Bot -> Bool
botOverlap
  where
    characterize :: [Bot] -> (Int, Int)
characterize [Bot]
bs = (- [Bot] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Bot]
bs, [Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ((Bot -> Int) -> [Bot] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Bot -> Int
distToOrigin [Bot]
bs))

-- * Bots

data Bot = Bot { Bot -> Coord3
botPos :: !Coord3, Bot -> Int
botRadius :: !Int }
  deriving (Bot -> Bot -> Bool
(Bot -> Bot -> Bool) -> (Bot -> Bot -> Bool) -> Eq Bot
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Bot -> Bot -> Bool
== :: Bot -> Bot -> Bool
$c/= :: Bot -> Bot -> Bool
/= :: Bot -> Bot -> Bool
Eq, Eq Bot
Eq Bot =>
(Bot -> Bot -> Ordering)
-> (Bot -> Bot -> Bool)
-> (Bot -> Bot -> Bool)
-> (Bot -> Bot -> Bool)
-> (Bot -> Bot -> Bool)
-> (Bot -> Bot -> Bot)
-> (Bot -> Bot -> Bot)
-> Ord Bot
Bot -> Bot -> Bool
Bot -> Bot -> Ordering
Bot -> Bot -> Bot
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Bot -> Bot -> Ordering
compare :: Bot -> Bot -> Ordering
$c< :: Bot -> Bot -> Bool
< :: Bot -> Bot -> Bool
$c<= :: Bot -> Bot -> Bool
<= :: Bot -> Bot -> Bool
$c> :: Bot -> Bot -> Bool
> :: Bot -> Bot -> Bool
$c>= :: Bot -> Bot -> Bool
>= :: Bot -> Bot -> Bool
$cmax :: Bot -> Bot -> Bot
max :: Bot -> Bot -> Bot
$cmin :: Bot -> Bot -> Bot
min :: Bot -> Bot -> Bot
Ord, Int -> Bot -> String -> String
[Bot] -> String -> String
Bot -> String
(Int -> Bot -> String -> String)
-> (Bot -> String) -> ([Bot] -> String -> String) -> Show Bot
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> Bot -> String -> String
showsPrec :: Int -> Bot -> String -> String
$cshow :: Bot -> String
show :: Bot -> String
$cshowList :: [Bot] -> String -> String
showList :: [Bot] -> String -> String
Show)

-- | Predicate for points that a bot's signal is strong enough to reach.
-- These points form a regular octohedron centered at the bot's location.
botSees :: Bot -> Coord3 -> Bool
botSees :: Bot -> Coord3 -> Bool
botSees (Bot Coord3
c Int
r) Coord3
p = Coord3 -> Coord3 -> Int
manhattan Coord3
c Coord3
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
r

-- | Check if two bots have sensor range overlap.
botOverlap :: Bot -> Bot -> Bool
botOverlap :: Bot -> Bot -> Bool
botOverlap (Bot Coord3
c1 Int
r1) (Bot Coord3
c2 Int
r2) = Coord3 -> Coord3 -> Int
manhattan Coord3
c1 Coord3
c2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r2

-- | Minimum distance from edge of bot's range to the origin (or zero if overlapping).
distToOrigin :: Bot -> Int
distToOrigin :: Bot -> Int
distToOrigin (Bot Coord3
c Int
r) = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Coord3 -> Coord3 -> Int
manhattan Coord3
origin Coord3
c Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
r)