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

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

-}
module Main (main) where

import Advent (getInputLines, fromDigits)
import Data.Either (partitionEithers)
import Data.List (sort)

-- | >>> :main
-- 392043
-- 1605968119
main :: IO ()
IO ()
main =
 do [String]
inp <- Int -> Int -> IO [String]
getInputLines Int
2021 Int
10
    let (String
p1, [String]
p2) = [Either Char String] -> (String, [String])
forall a b. [Either a b] -> ([a], [b])
partitionEithers (String -> String -> Either Char String
validate [] (String -> Either Char String) -> [String] -> [Either Char String]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [String]
inp)
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Char -> Int) -> String -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Char -> Int
cost1 String
p1))
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. Ord a => [a] -> a
median ((String -> Int) -> [String] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map String -> Int
cost2 [String]
p2))

-- | Return the median of an odd-length list
--
-- >>> median [1,2,0]
-- 1
median :: Ord a => [a] -> a
median :: forall a. Ord a => [a] -> a
median [a]
xs = [a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)

-- | Either find the first unexpected bracket, or return the expected
-- sequence of closing characters.
--
-- >>> validate [] "{([(<{}[<>[]}>{[]{[(<()>"
-- Left '}'
--
-- >>> validate [] "[({(<(())[]>[[{[]{<()<>>"
-- Right "}}]])})]"
validate :: String -> String -> Either Char String
validate :: String -> String -> Either Char String
validate (Char
x:String
xs) (Char
y:String
ys) | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
y            = String -> String -> Either Char String
validate String
xs String
ys
validate String
xs     (Char
y:String
ys) | Just Char
x <- Char -> Maybe Char
close Char
y = String -> String -> Either Char String
validate (Char
xChar -> String -> String
forall a. a -> [a] -> [a]
:String
xs) String
ys
validate String
_      (Char
y:String
_ )                     = Char -> Either Char String
forall a b. a -> Either a b
Left Char
y
validate String
xs     []                         = String -> Either Char String
forall a b. b -> Either a b
Right String
xs

-- | Return the character that closes this bracket, if there is one.
close :: Char -> Maybe Char
close :: Char -> Maybe Char
close Char
'(' = Char -> Maybe Char
forall a. a -> Maybe a
Just Char
')'
close Char
'[' = Char -> Maybe Char
forall a. a -> Maybe a
Just Char
']'
close Char
'{' = Char -> Maybe Char
forall a. a -> Maybe a
Just Char
'}'
close Char
'<' = Char -> Maybe Char
forall a. a -> Maybe a
Just Char
'>'
close Char
_   = Maybe Char
forall a. Maybe a
Nothing

cost1 :: Char -> Int
cost1 :: Char -> Int
cost1 Char
')' = Int
3
cost1 Char
']' = Int
57
cost1 Char
'}' = Int
1197
cost1 Char
'>' = Int
25137
cost1 Char
x   = String -> Int
forall a. HasCallStack => String -> a
error (String
"cost1: bad input " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Char -> String
forall a. Show a => a -> String
show Char
x)

-- | Compute the part 2 cost of the expected tail.
--
-- >>> cost2 "}}]])})]"
-- 288957
cost2 :: String -> Int
cost2 :: String -> Int
cost2 = Int -> [Int] -> Int
forall a. (HasCallStack, Integral a) => a -> [a] -> a
fromDigits Int
5 ([Int] -> Int) -> (String -> [Int]) -> String -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Int) -> String -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map Char -> Int
cost2'

cost2' :: Char -> Int
cost2' :: Char -> Int
cost2' Char
')' =  Int
1
cost2' Char
']' =  Int
2
cost2' Char
'}' =  Int
3
cost2' Char
'>' =  Int
4
cost2' Char
x   = String -> Int
forall a. HasCallStack => String -> a
error (String
"cost2': bad input " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Char -> String
forall a. Show a => a -> String
show Char
x)