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

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

-}
module Main (main) where

import Advent.Format (format)
import Advent.Coord (Coord, north, south, east, west, origin, drawCoords)
import Advent.Search (bfsOn)
import Intcode (Effect(..), run, new)

-- |
-- >>> :main
-- █████████████·███████████·███████·█████
-- █·····█·····█·█·········█·█···█···█···█
-- █████·█·███·█·█·███·███·█·███·█████·███
-- ····█·█·█·█···█·█·█···█·█···█·······█··
-- █·███·███·███·███·█████·███·███████·███
-- █·█·········█···█·······█·█···········█
-- █·█·███████·███·█·█████·█·█████████·███
-- █·█·····█·█·█···█·█···█·····█·····█·█·█
-- █·███████·█·█████·███·█████·█████·█·█·█
-- █·········█·········█·····█·····█·█·█··
-- █████████·█████·█████·█·███·███·█·█·███
-- █·······█···█···█·····█·█···█·█···█·█·█
-- █·█████████·█·███·█████·█·███·█████·█·█
-- █·█···█·····█·█···█···█·█·█···········█
-- █·███·█·█████·█·█████·█·█·███·███·█████
-- ····█·█·█·····█·█···█···█···█·█·█·█·█··
-- █████·█·█·█·███·███·███·█████·█·█·█·███
-- █·····█·█·█·█···█·····█·······█·█·····█
-- █·█·███·███·█·███·███·█████·███·███████
-- █·█·█·····█·█···█·█·█·█·····█·█·█·····█
-- █·███████·█·███·█·█·█·█████·█·█·█·███·█
-- █·········█···█·█·█·······█·█·█···█·█·█
-- ███·█████████·█·█·█████·███·█·█████·█·█
-- █·█·█·········█·█·····█·█···█·······█·█
-- █·█████·███·███·█·███·█·███████·█████·█
-- █·······█·█·█···█···█·█·█·······█·····█
-- ███·█████·███·███████·█·███·███·███·█·█
-- ··█·█·········█·····█·█·█···█·█·█·█·█·█
-- █·█·█·█████·█·█·███·█·█·█·███·█·█·█·███
-- █·█·█·█···█·█·█·█·█···█···█···█·█·█·█··
-- ███·███·█·█·███·█·█████·███·█·█·█·█·███
-- █·······█·█···█·█·······█···█·█···█····
-- ███·█████·███·█·█·███████·███·███·█·███
-- ··█·█···█···█···█·█···█···█·█···█·█·█·█
-- █·█·█·███·█·█████·█·███·███·█·███·███·█
-- █·█·█·█···█·········█·····█···█·······█
-- █·█·█·█·█████████·███·█████·███·███·███
-- █·█·█·█·····█···█·█···█·····█···█·█·█·█
-- █████·███████·█████·█████████████·███·█
-- 242
-- 276
main :: IO ()
IO ()
main =
 do [Int]
intcode <- [format|2019 15 %d&,%n|]
    let SearchState
part1:[SearchState]
_ = (SearchState -> Bool) -> [SearchState] -> [SearchState]
forall a. (a -> Bool) -> [a] -> [a]
filter SearchState -> Bool
onOxygen
                    (SearchState -> [SearchState]
explore (Effect -> SearchState
initialState (Machine -> Effect
run ([Int] -> Machine
new [Int]
intcode))))
        part2 :: [SearchState]
part2 = SearchState -> [SearchState]
explore SearchState
part1{distance = 0}
    String -> IO ()
putStr ([Coord] -> String
forall (t :: * -> *). Foldable t => t Coord -> String
drawCoords ((SearchState -> Coord) -> [SearchState] -> [Coord]
forall a b. (a -> b) -> [a] -> [b]
map SearchState -> Coord
location [SearchState]
part2))
    Int -> IO ()
forall a. Show a => a -> IO ()
print (SearchState -> Int
distance SearchState
part1)
    Int -> IO ()
forall a. Show a => a -> IO ()
print (SearchState -> Int
distance ([SearchState] -> SearchState
forall a. HasCallStack => [a] -> a
last [SearchState]
part2))

data SearchState = SearchState
  { SearchState -> Bool
onOxygen :: !Bool  -- ^ Is the robot currently on the oxygen?
  , SearchState -> Int
distance :: !Int   -- ^ Commands issued so far
  , SearchState -> Coord
location :: !Coord -- ^ robot's current location
  , SearchState -> Effect
effect   :: Effect -- ^ current program state
  }

-- | Build a new search state for a program effect. Assume we're at the
-- origin and that we are not on oxygen.
initialState :: Effect -> SearchState
initialState :: Effect -> SearchState
initialState = Bool -> Int -> Coord -> Effect -> SearchState
SearchState Bool
False Int
0 Coord
origin

-- | Breadth-first search of the program execution visiting each
-- location in the maze once.
explore :: SearchState -> [SearchState]
explore :: SearchState -> [SearchState]
explore = (SearchState -> Coord)
-> (SearchState -> [SearchState]) -> SearchState -> [SearchState]
forall r a. Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
bfsOn SearchState -> Coord
location SearchState -> [SearchState]
step

-- | Advance the program forward one input/output step.
step :: SearchState -> [SearchState]
step :: SearchState -> [SearchState]
step (SearchState Bool
oxy Int
dist Coord
loc (Input Int -> Effect
f)) =
  [ Bool -> Int -> Coord -> Effect -> SearchState
SearchState (Int
o Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2) (Int
dist Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Coord
loc Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
+ Coord
dir) Effect
e'
    | (Int
i, Coord
dir) <- [(Int
1,Coord
north),(Int
2,Coord
south),(Int
3,Coord
west),(Int
4,Coord
east)]
    , let Output Int
o Effect
e' = Int -> Effect
f Int
i
    , Int
o Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0]