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

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

>>> :{
:main +
  "#.######\n\
  \#>>.<^<#\n\
  \#.<..<<#\n\
  \#>v.><>#\n\
  \#<^v^^>#\n\
  \######.#\n"
:}
18
54

-}
module Main where

import Data.Array.Unboxed (UArray, (!), bounds, inRange)
import Data.Set (Set)
import Data.Set qualified as Set

import Advent (getInputArray)
import Advent.Coord (Coord(..), cardinal, west)

data SearchState = S {
  SearchState -> Int
time :: !Int,
  SearchState -> Set Coord
world :: !(Set Coord)
}

-- |
-- >>> :main
-- 295
-- 851
main :: IO ()
IO ()
main =
 do UArray Coord Char
input <- Int -> Int -> IO (UArray Coord Char)
getInputArray Int
2022 Int
24
    let start :: Coord
start = Int -> Int -> Coord
C Int
0 Int
1
        end :: Coord
end   = (Coord, Coord) -> Coord
forall a b. (a, b) -> b
snd (UArray Coord Char -> (Coord, Coord)
forall i. Ix i => UArray i Char -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds UArray Coord Char
input) Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
+ Coord
west
        t1 :: Int
t1    = UArray Coord Char -> Int -> Coord -> Coord -> Int
shortest UArray Coord Char
input Int
0  Coord
start Coord
end
        t2 :: Int
t2    = UArray Coord Char -> Int -> Coord -> Coord -> Int
shortest UArray Coord Char
input Int
t1 Coord
end   Coord
start
        t3 :: Int
t3    = UArray Coord Char -> Int -> Coord -> Coord -> Int
shortest UArray Coord Char
input Int
t2 Coord
start Coord
end
    Int -> IO ()
forall a. Show a => a -> IO ()
print Int
t1
    Int -> IO ()
forall a. Show a => a -> IO ()
print Int
t3

-- | Find the shortest time from source to destination starting at a
-- particular time step.
shortest ::
  UArray Coord Char {- ^ input map           -} ->
  Int               {- ^ initial time step   -} ->
  Coord             {- ^ starting location   -} ->
  Coord             {- ^ ending location     -} ->
  Int               {- ^ minimum travel time -}
shortest :: UArray Coord Char -> Int -> Coord -> Coord -> Int
shortest UArray Coord Char
input Int
t Coord
src Coord
dst =
    SearchState -> Int
time ((SearchState -> Bool)
-> (SearchState -> SearchState) -> SearchState -> SearchState
forall a. (a -> Bool) -> (a -> a) -> a -> a
until (Coord -> Set Coord -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Coord
dst (Set Coord -> Bool)
-> (SearchState -> Set Coord) -> SearchState -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SearchState -> Set Coord
world) (UArray Coord Char -> SearchState -> SearchState
step UArray Coord Char
input) (Int -> Set Coord -> SearchState
S Int
t (Coord -> Set Coord
forall a. a -> Set a
Set.singleton Coord
src)))

-- | Given a set of locations the elf could be find the set the elf can be at next.
step ::
  UArray Coord Char {- ^ input map -} ->
  SearchState -> SearchState
step :: UArray Coord Char -> SearchState -> SearchState
step UArray Coord Char
w (S Int
t Set Coord
prev) =
  Int -> Set Coord -> SearchState
S (Int
tInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Set Coord -> SearchState) -> Set Coord -> SearchState
forall a b. (a -> b) -> a -> b
$
  [Coord] -> Set Coord
forall a. Ord a => [a] -> Set a
Set.fromList
    [ Coord
next
      | Coord
here <- Set Coord -> [Coord]
forall a. Set a -> [a]
Set.toList Set Coord
prev
      , Coord
next <- Coord
here Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> [Coord]
cardinal Coord
here
      , UArray Coord Char -> Int -> Coord -> Bool
isOpen UArray Coord Char
w (Int
tInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Coord
next
    ]

-- | Check if a location in the world is available
isOpen ::
  UArray Coord Char {- ^ input map          -} ->
  Int               {- ^ time step          -} ->
  Coord             {- ^ location           -} ->
  Bool              {- ^ location available -}
isOpen :: UArray Coord Char -> Int -> Coord -> Bool
isOpen UArray Coord Char
w Int
t here :: Coord
here@(C Int
y Int
x) =
  (Coord, Coord) -> Coord -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (UArray Coord Char -> (Coord, Coord)
forall i. Ix i => UArray i Char -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds UArray Coord Char
w) Coord
here          Bool -> Bool -> Bool
&&
  Char
'#' Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= UArray Coord Char
w UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Coord
here                  Bool -> Bool -> Bool
&& -- walls
  Char
'>' Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= UArray Coord Char
w UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int -> Int -> Coord
C Int
y ((Int
x'Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
t)Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod`Int
xmInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Bool -> Bool -> Bool
&& -- east-bound storms
  Char
'<' Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= UArray Coord Char
w UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int -> Int -> Coord
C Int
y ((Int
x'Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
t)Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod`Int
xmInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Bool -> Bool -> Bool
&& -- west-bound storms
  Char
'v' Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= UArray Coord Char
w UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int -> Int -> Coord
C ((Int
y'Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
t)Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod`Int
ymInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
x Bool -> Bool -> Bool
&& -- south-bound storms
  Char
'^' Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= UArray Coord Char
w UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int -> Int -> Coord
C ((Int
y'Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
t)Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod`Int
ymInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
x    -- north-bound storms
  where
    y' :: Int
y' = Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
    x' :: Int
x' = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
    C Int
ym Int
xm = (Coord, Coord) -> Coord
forall a b. (a, b) -> b
snd (UArray Coord Char -> (Coord, Coord)
forall i. Ix i => UArray i Char -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds UArray Coord Char
w) Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
- Coord
1