{-|
Module      : Main
Description : Day 10 solution
Copyright   : (c) Eric Mertens, 2023
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2023/day/10>

This solution finds the contained area using
<https://en.wikipedia.org/wiki/Shoelace_formula>.

>>> :{
:main +
".....
.S-7.
.|.|.
.L-J.
.....
"
:}
4
1

>>> :{
:main +
"-L|F7
7S-7|
L|7||
-L-J|
L|-JF
"
:}
4
1

>>> :{
:main +
"7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ
"
:}
8
1

>>> :{
:main +
"...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........
"
:}
23
4

>>> :{
:main +
".F----7F7F7F7F-7....
.|F--7||||||||FJ....
.||.FJ||||||||L7....
FJL7L7LJLJ||LJ.L-7..
L--J.L7...LJS7F-7L7.
....F-J..F7FJ|L7L7L7
....L7.F7||L7|.L7L7|
.....|FJLJ|FJ|F7|.LJ
....FJL-7.||.||||...
....L---J.LJ.LJLJ...
"
:}
70
8

>>> :{
:main +
"FF7FSF7F7F7F7F7F---7
L|LJ||||||||||||F--J
FL-7LJLJ||||||LJL-77
F--JF--7||LJLJ7F7FJ-
L---JF-JLJ.||-FJLJJ7
|F|F-JF---7F7-L7L|7|
|FFJF7L7F-JF7|JL---7
7-L-JL7||F7|L7F-7F7|
L.L7LFJ|||||FJL7||LJ
L7JLJL-JLJLJL--JLJ.L
"
:}
80
10

-}
module Main (main) where

import Advent (getInputArray, arrIx)
import Advent.Coord (invert, invert', south, north, west, manhattan, Coord(C))
import Data.Array.Unboxed (UArray, (!), assocs)
import Data.List (tails)

-- | Parse the input and print out answers to both parts.
--
-- >>> :main
-- 6907
-- 541
main :: IO ()
IO ()
main =
 do input <- Int -> Int -> IO (UArray Coord Char)
getInputArray Int
2023 Int
10
    let route = (Coord -> Coord -> [Coord]) -> (Coord, Coord) -> [Coord]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (UArray Coord Char -> Coord -> Coord -> [Coord]
follow UArray Coord Char
input) (UArray Coord Char -> (Coord, Coord)
pickStart UArray Coord Char
input)
        perimeter = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Coord -> Coord -> Int) -> [Coord] -> [Coord] -> [Int]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Coord -> Coord -> Int
manhattan [Coord]
route ([Coord] -> [Coord]
forall a. HasCallStack => [a] -> [a]
tail [Coord]
route))
    print (perimeter `quot` 2)
    print (abs (polyareaRect route) - perimeter `quot` 2 + 1)

-- | Determine the location of the start cell and a valid direction
-- leaving it.
pickStart :: UArray Coord Char -> (Coord, Coord)
pickStart :: UArray Coord Char -> (Coord, Coord)
pickStart UArray Coord Char
input = [(Coord, Coord)] -> (Coord, Coord)
forall a. HasCallStack => [a] -> a
head
  [ (Coord
c, Coord
dir)
  | (Coord
c, Char
'S')  <- UArray Coord Char -> [(Coord, Char)]
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(i, e)]
assocs UArray Coord Char
input
  , (Coord
dir, String
ok) <- [(Coord
south, String
"L|J"), (Coord
north, String
"F|7"), (Coord
west,String
"7-J")]
  , Char
next      <- UArray Coord Char -> Coord -> String
forall (a :: * -> * -> *) e i (f :: * -> *).
(IArray a e, Ix i, Alternative f) =>
a i e -> i -> f e
arrIx UArray Coord Char
input (Coord
c Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
+ Coord
dir)
  , Char
next Char -> String -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` String
ok
  ]

-- | Trace out the closed loop from start to start
follow :: UArray Coord Char -> Coord -> Coord -> [Coord]
follow :: UArray Coord Char -> Coord -> Coord -> [Coord]
follow UArray Coord Char
input Coord
start Coord
dir0 = Coord
start Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> Coord -> [Coord]
go Coord
dir0 Coord
start 
  where
    go :: Coord -> Coord -> [Coord]
go Coord
dir Coord
prev =
      let here :: Coord
here = Coord
dir Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
+ Coord
prev in
      case UArray Coord Char
input UArray Coord Char -> Coord -> Char
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Coord
here of
        Char
'S' -> [Coord
here]
        Char
'7' -> Coord
here Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> Coord -> [Coord]
go (Coord -> Coord
invert  Coord
dir) Coord
here
        Char
'L' -> Coord
here Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> Coord -> [Coord]
go (Coord -> Coord
invert  Coord
dir) Coord
here
        Char
'J' -> Coord
here Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> Coord -> [Coord]
go (Coord -> Coord
invert' Coord
dir) Coord
here
        Char
'F' -> Coord
here Coord -> [Coord] -> [Coord]
forall a. a -> [a] -> [a]
: Coord -> Coord -> [Coord]
go (Coord -> Coord
invert' Coord
dir) Coord
here
        Char
_   ->        Coord -> Coord -> [Coord]
go Coord
dir           Coord
here

-- | Area of a polygon using Shoelace formula on a closed loop
-- in a clockwise direction.
polyareaRect :: [Coord] -> Int
polyareaRect :: [Coord] -> Int
polyareaRect [Coord]
xs = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int
x1 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
y2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
y1 | C Int
y1 Int
x1 : C Int
y2 Int
x2 : [Coord]
_ <- [Coord] -> [[Coord]]
forall a. [a] -> [[a]]
tails [Coord]
xs] Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2