Advent of Code 2019 day 14

    Day 14 took a bit of thought about the best way to tackle it, but I eventually took inspiration from blackboard systems. The key data structure was a Map of required production of each chemical. A positive number of required indicates how many molecules still need to be created; a negative number show how much excess of a molecule is around, produced but unused.

    Initially, the required map contains just the one element of fuel required. The reaction rules were also stored in a map, keyed by the chemical that was produced by that reaction. Finally, reagents in a reaction were stored as a chemical name and number of molecules.

    data Reagent = Reagent { _quantity :: Int, _chemical :: String } deriving (Ord, Eq, Show)
    data Reaction = Reaction {_lhs :: S.Set Reagent, _rhs :: Reagent} deriving (Eq, Show)
    type Reactions = M.Map String Rule
    type Requirement = M.Map String Int


    The input structure was more complex than just a comma-separated list of numbers, so it showed off the abilities of the parser rather well, I thought.

    The parser started by giving some names for parts of the reaction rules.

    type Parser = Parsec Void Text
    sc :: Parser ()
    sc = (skipSome spaceChar) CA.empty CA.empty
    lexeme  = L.lexeme sc
    integer = lexeme L.decimal
    symb = L.symbol sc
    arrowP = symb "=>"
    commaP = symb ","
    identifierP = some alphaNumChar <* sc

    Given those, the parser proper is just these four statements:

    reactionsP = mkReactions <$> many reactionP
    reactionP = Reaction <$> reagentsP <* arrowP <*> reagentP
    reagentP = Reagent <$> integer <*> identifierP
    reagentsP = S.fromList <$> reagentP `sepBy` commaP

    together with the auxiliary function mkReactions, which folds a list of reactions into a map.

    mkReactions :: [Reaction] -> Reactions
    mkReactions = foldl' addReaction M.empty
        where addReaction base reaction = M.insert (_chemical $ _rhs reaction) reaction base

    Part 1

    The production plan started by stating the requirement for one fuel. It then proceeds by picking a required chemical (arbitrarily), finding the reaction that produces it, and running that reaction.

    "Running" a reaction decreases the required of the reaction's product, and increases the required of the reaction's reagents.

    produce :: Reactions -> Requirement -> Requirement
    produce reactions required 
        | M.null outstanding = required 
        | otherwise = produce reactions required''
        where outstanding =  M.filter (> 0) $ nonOre required
              (chem, qty) = M.findMin outstanding
              reaction = reactions!chem
              productQty = _quantity $ _rhs reaction
              applications = max 1 (qty `div` productQty)
              qty' = qty - (applications * productQty)
              required' = M.insert chem qty' required
              required'' = S.foldl (addRequrirement applications) required' (_lhs reaction) 

    When there's a lot of a chemical that needs producing, the applications value shows how many times the reaction can be run; a reaction must be run at least once if the product is required. (I didn't need to count applications for part 1; just doing a single run of a reaction at a time was sufficient. But I needed it for part 2!)

    The nonOre implements the exception that ORE never needs to be produced.

    nonOre :: Requirement -> Requirement
    nonOre = M.filterWithKey (\c _ -> c /= "ORE")

    addRequirement adds all the reagents to the required map, taking account of any existing requirements for that chemical.

    addRequrirement :: Int -> Requirement -> Reagent -> Requirement
    addRequrirement n requirements reagent = M.insert chem qty' requirements
        where chem = _chemical reagent
              qty = M.findWithDefault 0 chem requirements
              qty' = qty + (n * _quantity reagent) 

    The whole thing is triggered by oreForFuel, which calculates the amount of ore required for a particular amount of fuel.

    part1 reactions = oreForFuel reactions 1
    oreForFuel :: Reactions -> Int -> Int
    oreForFuel reactions n = required!"ORE"
        where required0 = M.singleton "FUEL" n
              required = produce reactions required0 

    Part 2

    This was a binary search of the fuel amount. I guessed a lower limit on the amount of fuel based on the ore requirement for a single unit of fuel. I guessed an upper limit as powers of two times that, picking the first that required more ore than was available.

    part2 reactions = searchFuel reactions (upper `div` 2) upper 
        where upper = findUpper reactions (oreLimit `div` base)
              base = oreForFuel reactions 1
    findUpper :: Reactions -> Int -> Int
    findUpper reactions n = if ore > oreLimit
                        then n
                        else findUpper reactions (n * 2)
        where ore = oreForFuel reactions n 

    Given a sensible upper and lower bound, the binary search of the maximal fuel amount could begin. It's a relatively standard search, but with some fiddling around to ensure that it always returns a valid amount of fuel.

    searchFuel :: Reactions -> Int -> Int -> Int
    searchFuel reactions lower upper 
        | upper == lower = upper
        | otherwise = if ore > oreLimit
                      then searchFuel reactions lower (mid - 1)
                      else searchFuel reactions mid upper
        where mid = (upper + lower + 1) `div` 2
              ore = oreForFuel reactions mid


    The code is available (and on Github).

    Neil Smith

    Read more posts by this author.