December 16, 2019

# Advent of Code 2019 day 14

Blackboards and binary search

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


## Parsing

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 = L.space (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
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


## Code

The code is available (and on Github).