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

<https://adventofcode.com/2018/day/5>

-}
module Main (main) where

import Advent.Format (format)
import Data.Char (toLower, toUpper)
import Data.List (nub)

-- | Print the answers to day 5
--
-- >>> :main
-- 9370
-- 6390
main :: IO ()
IO ()
main =
  do [Char]
inp <- [format|2018 5 %s%n|]
     Int -> IO ()
forall a. Show a => a -> IO ()
print ([Char] -> Int
part1 [Char]
inp)
     Int -> IO ()
forall a. Show a => a -> IO ()
print ([Char] -> Int
part2 [Char]
inp)

-- | Collapse the polymer using the lowercase/uppercase matching rule.
--
-- >>> simplify "dabAcCaCBAcCcaDA"
-- "dabCBAcaDA"
simplify :: String -> String
simplify :: [Char] -> [Char]
simplify = (Char -> [Char] -> [Char]) -> [Char] -> [Char] -> [Char]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Char -> [Char] -> [Char]
step [Char]
""
  where
    -- Invariant: list argument to step is always completely reduced
    step :: Char -> [Char] -> [Char]
step Char
x (Char
y:[Char]
ys) | Char -> Char -> Bool
match Char
x Char
y = [Char]
ys
    step Char
x [Char]
ys                 = Char
x Char -> [Char] -> [Char]
forall a. a -> [a] -> [a]
: [Char]
ys

-- | Match characters where one is the lowercase version of the other.
--
-- >>> match 'a' 'A'
-- True
-- >>> match 'A' 'a'
-- True
-- >>> match 'a' 'a'
-- False
match :: Char -> Char -> Bool
match :: Char -> Char -> Bool
match Char
x Char
y = Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= Char
y Bool -> Bool -> Bool
&& Char -> Char
toUpper Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char -> Char
toUpper Char
y

-- | Compute the length of the collapsed polymer.
--
-- >>> part1 "dabAcCaCBAcCcaDA"
-- 10
part1 :: String -> Int
part1 :: [Char] -> Int
part1 = [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Char] -> Int) -> ([Char] -> [Char]) -> [Char] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> [Char]
simplify


-- | Find the minimum length a string can reduce to when we're allowed
-- to remove any one pair of characters.
--
-- >>> part2 "dabAcCaCBAcCcaDA"
-- 4
part2 :: String -> Int
part2 :: [Char] -> Int
part2 [Char]
str = [Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Int]
lengths
  where
    str' :: [Char]
str'       = [Char] -> [Char]
simplify [Char]
str
    candidates :: [Char]
candidates = [Char] -> [Char]
forall a. Eq a => [a] -> [a]
nub ((Char -> Char) -> [Char] -> [Char]
forall a b. (a -> b) -> [a] -> [b]
map Char -> Char
toLower [Char]
str')
    isOk :: Char -> Char -> Bool
isOk Char
bad Char
x = Char
bad Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= Char -> Char
toLower Char
x
    lengths :: [Int]
lengths    = [[Char] -> Int
part1 ((Char -> Bool) -> [Char] -> [Char]
forall a. (a -> Bool) -> [a] -> [a]
filter (Char -> Char -> Bool
isOk Char
bad) [Char]
str') | Char
bad <- [Char]
candidates]