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

<https://adventofcode.com/2022/day/18>

>>> :{
:main +
    "2,2,2\n\
    \1,2,2\n\
    \3,2,2\n\
    \2,1,2\n\
    \2,3,2\n\
    \2,2,1\n\
    \2,2,3\n\
    \2,2,4\n\
    \2,2,6\n\
    \1,2,5\n\
    \3,2,5\n\
    \2,1,5\n\
    \2,3,5\n"
:}
64
58

-}
module Main where

import Data.Ix (inRange)
import Data.Maybe (fromJust)
import Data.Set (Set)
import Data.Set qualified as Set

import Advent (format)
import Advent.Search (bfs)
import Advent.Coord3 (Coord3(..), boundingBox)

-- |
-- >>> :main
-- 4332
-- 2524
main :: IO ()
IO ()
main =
 do [(Int, Int, Int)]
input <- [format|2022 18 (%u,%u,%u%n)*|]
    let cubes :: Set Coord3
cubes    = [Coord3] -> Set Coord3
forall a. Ord a => [a] -> Set a
Set.fromList (((Int, Int, Int) -> Coord3) -> [(Int, Int, Int)] -> [Coord3]
forall a b. (a -> b) -> [a] -> [b]
map (Int, Int, Int) -> Coord3
toC3 [(Int, Int, Int)]
input)
    let air :: Set Coord3
air      = Set Coord3 -> Set Coord3
findAir Set Coord3
cubes
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([()] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [() | Coord3
c <- Set Coord3 -> [Coord3]
forall a. Set a -> [a]
Set.toList Set Coord3
cubes, Coord3
n <- Coord3 -> [Coord3]
neigh Coord3
c, Coord3 -> Set Coord3 -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.notMember Coord3
n Set Coord3
cubes])
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([()] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [() | Coord3
c <- Set Coord3 -> [Coord3]
forall a. Set a -> [a]
Set.toList Set Coord3
cubes, Coord3
n <- Coord3 -> [Coord3]
neigh Coord3
c, Coord3 -> Set Coord3 -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member    Coord3
n Set Coord3
air  ])

-- | Given the the location of the lava cubes, find a bounding box of air surrounding them.
findAir :: Set Coord3 -> Set Coord3
findAir :: Set Coord3 -> Set Coord3
findAir Set Coord3
cubes = [Coord3] -> Set Coord3
forall a. Ord a => [a] -> Set a
Set.fromList ((Coord3 -> [Coord3]) -> Coord3 -> [Coord3]
forall a. Ord a => (a -> [a]) -> a -> [a]
bfs Coord3 -> [Coord3]
step (Coord3
hi Coord3 -> Coord3 -> Coord3
forall a. Num a => a -> a -> a
+ Coord3
1))
  where
    (Coord3
lo, Coord3
hi) = Maybe (Coord3, Coord3) -> (Coord3, Coord3)
forall a. HasCallStack => Maybe a -> a
fromJust (Set Coord3 -> Maybe (Coord3, Coord3)
forall (f :: * -> *).
Foldable f =>
f Coord3 -> Maybe (Coord3, Coord3)
boundingBox Set Coord3
cubes)
    box :: (Coord3, Coord3)
box      = (Coord3
lo Coord3 -> Coord3 -> Coord3
forall a. Num a => a -> a -> a
- Coord3
1, Coord3
hi Coord3 -> Coord3 -> Coord3
forall a. Num a => a -> a -> a
+ Coord3
1)
    step :: Coord3 -> [Coord3]
step Coord3
c   = [Coord3
n | Coord3
n <- Coord3 -> [Coord3]
neigh Coord3
c, (Coord3, Coord3) -> Coord3 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Coord3, Coord3)
box Coord3
n, Coord3 -> Set Coord3 -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.notMember Coord3
n Set Coord3
cubes]

-- | Neighbors of the cubes (excluding diagonals)
neigh :: Coord3 -> [Coord3]
neigh :: Coord3 -> [Coord3]
neigh (C3 Int
x Int
y Int
z) = [Int -> Int -> Int -> Coord3
C3 (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
y Int
z, Int -> Int -> Int -> Coord3
C3 (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Int
y Int
z, Int -> Int -> Int -> Coord3
C3 Int
x (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
z, Int -> Int -> Int -> Coord3
C3 Int
x (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Int
z, Int -> Int -> Int -> Coord3
C3 Int
x Int
y (Int
zInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1), Int -> Int -> Int -> Coord3
C3 Int
x Int
y (Int
zInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)]

-- | Convert tuple to Coord3
toC3 :: (Int, Int, Int) -> Coord3
toC3 :: (Int, Int, Int) -> Coord3
toC3 (Int
x,Int
y,Int
z) = Int -> Int -> Int -> Coord3
C3 Int
x Int
y Int
z