Advent of Code 2018 Day 5: Alchemical Reduction

haskell.md

Problem

Given a combination of polymers, represented by a string of uppercase and lowercase characters, remove the reactions that can take place until no reactions remain. What's the length of the string that has no more reactions?

A reaction can take place if two subsequent letters are the same letter with opposite cases.

• "aA" reacts.
• "Aa" reacts.
• "AA" does not react.
• "aa" does not react.
• "AB" does not react.
• "ab" does not react.

Example

Given an input of dabAcCaCBAcCcaDA, here's how it would react:

dabAcCaCBAcCcaDA

The first 'cC' is removed.

dabAaCBAcCcaDA

This creates 'Aa', which is removed.

dabCBAcCcaDA

Either 'cC' or 'Cc' are removed (the result is the same).

dabCBAcaDA

No further actions can be taken.

A Haskell approach

numberFive :: IO Int
numberFive = length . reactFully . head . lines <$> readFile "/Users/nwest/AoC/5"

reactFully :: String -> String
reactFully input = let reacted = reactOnce input
                   in if reacted == input
                        then reacted
                        else reactOnce reacted

reactOnce :: String -> String
reactOnce input = foldr reactPolymers "" input
  where
    reactPolymers char ""                      = [char]
    reactPolymers char string@(firstChar:rest) = if shouldReact char firstChar
                                                   then rest
                                                   else char:string

shouldReact :: Char -> Char -> Bool
shouldReact c1 c2 | isUpper c1, isLower c2 = c1 == toUpper c2
                  | isLower c1, isUpper c2 = toUpper c1 == c2
                  | otherwise = False