## DEV Community is a community of 715,270 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Jon Bristow

Posted on

# Advent of Code 2019 Solution Megathread - Day 14: Space Stoichiometry

Who says we can't play god? Well, a god is probably better at combinatorics than I am.

### Day 14 - The Problem

Bad news, folks. We're running out of fuel. The good news is that we're right next to a big source of ORE.

Part 1 has us trying to assemble fuel with our amazing elemental recombinator.

Part 2: will be described when I get there.

### Ongoing Meta

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

#### Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

##### Languages Seen On Day 12

Under construction

## Discussion (4) Neil Gall • Edited

Ok it's the weekend so I had some fun in Haskell. The input data has a more complex structure today so I whipped out my trusty parser combinator toolkit. But I've got this far with very few external libraries so let's write our own!

``````data ParseResult input value
= Ok value input
| Err String input
deriving (Eq, Show)

instance Functor (ParseResult input) where
fmap f (Ok value rest) = Ok (f value) rest
fmap f (Err expected actual) = Err expected actual

newtype Parser input value = Parser (input -> ParseResult input value)

instance Functor (Parser input) where
fmap f (Parser p) = Parser (\input -> fmap f (p input))

instance Applicative (Parser input) where
pure x = Parser (\input -> Ok x input)
(Parser p) <*> (Parser q) = Parser \$ \input ->
case p input of
Ok r rest -> fmap r (q rest)
Err e a -> Err e a

parse :: Parser input value -> input -> ParseResult input value
parse (Parser p) input = p input

parseWith :: (Char -> Bool) -> (String -> a) -> String -> Parser String a
parseWith match convert expected = Parser \$ \input ->
let
matching = takeWhile match input
rest = dropWhile match input
in
if null matching
then Err expected input
else Ok (convert matching) rest

literal :: String -> Parser String ()
literal s = Parser \$ \input ->
case stripPrefix s input of
Nothing -> Err ("'" ++ s ++ "'") input
(Just rest) -> Ok () rest

integer :: Parser String Int
integer = parseWith isDigit read "an integer"

chemical :: Parser String String
chemical = parseWith isAsciiUpper id "a chemical symbol"

whitespace :: Parser String ()
whitespace = Parser \$ \input -> Ok () (dropWhile isSpace input)

before :: Parser i x -> Parser i a -> Parser i a
x `before` p = fmap snd \$ pure (,) <*> x <*> p

followedBy :: Parser i a -> Parser i x -> Parser i a
p `followedBy` x = fmap fst \$ pure (,) <*> p <*> x

sepBy :: Parser i a -> Parser i s -> Parser i [a]
sepBy (Parser p) (Parser q) = Parser sepBy'
where
sepBy' input = case p input of
Err _ _ -> Ok [] input
Ok v rest -> case q rest of
Err _ _ -> Ok [v] rest
Ok _ rest' -> fmap (\vs -> v:vs) (sepBy' rest')
``````

That was fun, and lets me write really simple code for parsing the input data:

``````type Name = String

data Material = Material Int Name

data Reaction = Reaction [Material] Material

material :: Parser String Material
material = Material <\$> (integer `followedBy` whitespace) <*> chemical

reaction :: Parser String Reaction
reaction = Reaction <\$> inputs <*> output
where
inputs = material `sepBy` literal ", "
output = literal " => " `before` material

reactions :: Parser String [Reaction]
reactions = reaction `sepBy` whitespace
``````

Ok on to the problem. We've had topological sort problems before in AoC so I recognised the general form of the problem pretty quickly. If you sort the chemicals by dependency then you can walk that list in order knowing when you reach a chemical you've already dealt with everything that has a demand on it.

``````data Edge = Edge Name Name

findEdges :: [Reaction] -> [Edge]
findEdges [] = []
findEdges ((Reaction inputs output):rs) = (map toEdge inputs) ++ (findEdges rs)
where
edgeOutput = (\(Material _ o) -> o) output
toEdge (Material _ i) = Edge i edgeOutput

topoSort :: [Reaction] -> [Name]
topoSort rs = reverse \$ topoSort' (findEdges rs) ["FUEL"] []
where
input (Edge i _) = i
output (Edge _ o) = o
from x e = input e == x
to x e = output e == x
noneFrom es e = not (any (from (input e)) es)

topoSort' :: [Edge] -> [Name] -> [Name] -> [Name]
topoSort' _ [] result = result
topoSort' edges (here:stack) result =
let
(incoming, edges') = partition (to here) edges
next = map input \$ filter (noneFrom edges') incoming
stack' = stack ++ next
in
topoSort' edges' stack' (here:result)
``````

The next bit was tricky. First I reorganised the reaction data into a map from chemical name to its requirements and quantity produced:

``````requirements :: [Reaction] -> M.Map Name (Int, [Material])
requirements [] = M.empty
requirements ((Reaction inputs (Material quantity name)):rs) =
M.insert name (quantity, inputs) (requirements rs)
``````

Then the quantity needed is found by walking the topologically sorted list of chemicals and building a map of the amount of each needed. For each chemical look up the inputs and add the appropriately scaled amount to each input's requirements.

``````quantitiesNeeded :: [Reaction] -> Int -> M.Map String Int
quantitiesNeeded rs fuel = foldl quantityNeeded (M.fromList [("FUEL", fuel)]) (topoSort rs)
where
add q Nothing = Just q
add q (Just q') = Just (q' + q)
reqs = requirements rs

quantityNeeded :: M.Map String Int -> String -> M.Map String Int
quantityNeeded neededByName name =
case M.lookup name reqs of
Nothing -> neededByName
Just (makesQuantity, inputs) -> foldl addNeeded neededByName' inputs
where
Just needQuantity = M.lookup name neededByName
scale = (needQuantity `div` makesQuantity) + (if needQuantity `mod` makesQuantity > 0 then 1 else 0)
neededByName' = M.alter (add needQuantity) name neededByName
addNeeded n (Material q m) = M.alter (add (scale * q)) m n
``````

The final answer is waiting the in the map at the end

``````oreNeededForFuel :: [Reaction] -> Int -> Int
oreNeededForFuel rs fuel = fromMaybe 0 \$ M.lookup "ORE" \$ quantitiesNeeded rs fuel
``````

At first I thought part 2 was going to reverse the search order so we started from ORE but I quickly realised the search space explodes once you can use an input for multiple outputs. It turned out much simpler - starting with an estimate of the quantity of ORE divided by the ORE needed for 1 FUEL, it's just a binary search to find the maximum amount of FUEL we can make.

``````maxFuelProduced :: [Reaction] -> Int -> Int
maxFuelProduced reactions quantityOfOre = binarySearch estimateLow estimateHigh
where
estimateLow = quantityOfOre `div` (oreNeededForFuel reactions 1)
estimateHigh = estimateLow * 2
binarySearch min max = if min == max || min + 1 == max then min
else let
mid = (min + max) `div` 2
in
if oreNeededForFuel reactions mid > quantityOfOre
then binarySearch min mid
else binarySearch mid max
``````

Full source with unit tests. Rizwan

Finally something not involving grid points. Took wrong path and wasted lot of time

Swift solution here.

``````struct Item: Hashable, CustomStringConvertible {
var count: Int
let name: String

init(_ count: Int, _ name: String) {
self.count = count
self.name = name
}

init(_ string: String) {
let value = string.components(separatedBy: " ")
self.count = Int(value.first!) ?? 0
self.name = value.last!
}

var description: String {
get {
return "\(count) \(name)"
}
}

func scaled(by scale: Int) -> Item {
return Item(count * scale,name)
}
}
struct Reaction {
var inputs: [Item]
var output: Item
}
var reactions = input.map { line in
Reaction.init(inputs: line.first.map { \$0.map{ Item(\$0) }}!, output: Item(line.last!.first!))
}

func cost(_ count: Int) -> Int {
var req: [Item] = [Item.init(count, "FUEL")]
var excess: [String: Int] = [:]
var done = false

while !done {
//print(req)
if !req.contains(where: { \$0.name != "ORE"}) {
done = true
}
var next: [Item] = []
for item in req {
if item.name == "ORE" {
excess["ORE", default: 0] += item.count
}
else {
//print(excess)
var quantity = item.count
if let extra = excess[item.name] {
if extra > quantity {
excess[item.name, default: 0] = extra - quantity
continue
} else {
quantity -= extra
excess.removeValue(forKey: item.name)
}
}
let current = reactions.filter{ \$0.output.name == item.name }.first!
let scale = Int(ceil(Double(quantity) / Double(current.output.count)))
current.inputs.map { i in
var x = i
x.count *= scale
next.append(x)
}

let a = current.output.count * scale - quantity
if a > 0 {
excess[item.name, default: 0] += a
}
}
}
req = next
}
//print(excess)
return req.filter { (item) -> Bool in
item.name == "ORE"
}.first?.count ?? 0 + (excess["ORE"] ?? 0)
}

func partOne() {
let result = cost(1)
}

func partTwo() {
var low = 0
var high = Int(1e12)
while low < high {
let mid = (low + high + 1) / 2

if cost(mid) <= Int(1e12) {
low = mid
}
else {
high = mid - 1
}
}

}

partOne()
partTwo()

`````` Massimo Artizzu

Oooh another nice problem :)

First of all, parsing. Fairly simple, you just have to create a map. Note that there's only one reaction to produce a specific chemical.
But the produced amount may vary, so we have to track that information. For some silly reason, I used a JavaScript `Symbol` to store that in the map 😅. I basically never used `Symbol`s in my job, but here I am practicing with them:

``````const quantityKey = Symbol();
const reactions = input.trim().split('\n').reduce((map, line) => {
const [ ingredientList, result ] = line.split(' => ');
const [ quantity, chemical ] = result.split(' ');
map[chemical] = ingredientList.split(', ').reduce((ingredientMap, combo) => {
const [ qty, chem ] = combo.split(' ');
ingredientMap[chem] = +qty;
return ingredientMap;
}, { [quantityKey]: +quantity });
return map;
}, {});
``````

The basic idea here is, of course, that you have to start with the reaction needed for FUEL (there's only one) and create a shopping list of the chemicals you need (and how many of them). But while doing so, you also have to keep track of the chemicals you end up not using for the current reaction, because they may come in handy for the next reactions.

I'm wrapping everything in a function so it can be used in the second part:

``````function getNeededOre(fuel) {
let neededChemicals = { FUEL: fuel };
const reserves = {};
while (Object.keys(neededChemicals).length !== 1 || !('ORE' in neededChemicals)) {
const newNeededList = {};
for (const [ chemical, quantity ] of Object.entries(neededChemicals)) {
if (chemical === 'ORE') {
newNeededList.ORE = (newNeededList.ORE || 0) + quantity;
continue;
}
const reaction = reactions[chemical];
const reactionQuantity = reaction[quantityKey];
const reactionCount = Math.ceil((quantity - (reserves[chemical] || 0)) / reactionQuantity);
for (const [ ingredient, amount ] of Object.entries(reaction)) {
newNeededList[ingredient] = (newNeededList[ingredient] || 0) + reactionCount * amount;
}
reserves[chemical] = (reserves[chemical] || 0) + reactionCount * reactionQuantity - quantity;
}
neededChemicals = newNeededList;
}
return neededChemicals.ORE;
}

const orePer1Fuel = getNeededOre(1);

console.log('Part 1:', orePer1Fuel);
``````

For the second part, we have to remind that after producing 1 FUEL, we still have some useful chemicals left. So, should we produce one FUEL at a time, always keeping track of the reserves? I had a better idea, and it involves estimations. Turns out it reaches the correct answer pretty fast (right at the second iteration for me!):

``````const TOTAL_ORE = 1e12;
let estimate;
let newEstimate = Math.floor(TOTAL_ORE / orePer1Fuel);
do {
const neededEstimate = getNeededOre(estimate);
newEstimate = Math.floor(estimate * TOTAL_ORE / neededEstimate);
console.log('Part 2:', estimate);
``````

Text, input and solution at my repo 👋 Ryan Palo

After much stewing and drawing diagrams, I realized it was an acyclic directed graph. It's always a graph! Part 2 took a little bit of pragmatic, targeted brute forcing because I was sleepy.

``````"""Make fuel out of ore based on stoichiometric recipes"""
from dataclasses import dataclass
from typing import List, Dict
from math import ceil

@dataclass
class Component:
"""An input component to a reaction"""
name: str
quantity: int

@dataclass
class Equation:
"""A stoichiometric reaction equation using multiple ingredients to make some output"""
name: str
quantity: int
ingredients: Dict[str, Component]

@dataclass
class Node:
"""A node in a dependency graph of stoichiometric equations.

Nodes are ingredients.  They have dependents (things that use them
as inputs) and dependencies (things they need to make themselves).

Dynamically, they resolve themselves by listening to their dependents
telling them how much of themself they need and, based on the equations,
calculating the minimum amount that can be made to achieve that.
"""
name: str
dependents: List["Node"]
dependencies: List["Node"]
amount_needed: int = 0
resolved: bool = False

def parse(text):
"""Parses input text to build the recipes database.

Expects text in the form of equations (one per line):
3 IMFS, 4 ABCD, 1 EFGH => 6 OUTP

Returns a dict of output names to recipe Equations.
"""
result = dict()
for line in text.splitlines():
inputs, outputs = line.split(" => ")
ingredients = dict()
for inp in inputs.split(", "):
qty, name = inp.split()
ingredients[name] = Component(name, int(qty))
out_qty, out_name = outputs.split()
result[out_name] = Equation(out_name, int(out_qty), ingredients)

# Additionally, ORE is free.  You can make 1 ORE with no inputs.
result["ORE"] = Equation(1, dict())
return result

def generate_digraph(recipes: Dict[str, Equation]) -> Dict[str, Node]:
"""Generates a graph of component dependencies."""
digraph = {name: Node(name, [], []) for name in recipes}

for name, eqn in recipes.items():
for ingredient_name in eqn.ingredients:
digraph[name].dependencies.append(digraph[ingredient_name])
digraph[ingredient_name].dependents.append(digraph[name])

return digraph

def resolve_digraph(fuel: int, recipes: Dict[str, Equation], digraph: Dict[str, Node]):
"""Based on the desired amount of fuel, calculates how much of each
component is needed, and, based on output amounts in the recipes,
how much of each component is actually created to minimize waste.

Initializes information at FUEL--the top of the graph--and starts
solving recursively from the bottom of the graph: ORE.
"""
digraph["FUEL"].amount_needed = fuel
resolve(digraph["ORE"], recipes)

def resolve(node: Node, recipes: Dict[str, Equation]):
"""Resolve a node.

A node can be resolved if all of the components that depend on it
have been resolved and have decided how much of it they need.
Then, it calculates how much should be made based on the recipes.
And it informs its dependencies how much of each of them it will
need.
"""
for dependent in node.dependents:
if not dependent.resolved:
resolve(dependent, recipes)

needed = node.amount_needed
possible = recipes[node.name].quantity
batches = ceil(needed / possible)

for dependency in node.dependencies:
dependency.amount_needed += batches * \
recipes[node.name].ingredients[dependency.name].quantity

node.resolved = True

if __name__ == "__main__":
with open("data/day14.txt") as f:
digraph = generate_digraph(recipes)

# Part 1: How much ORE to make 1 FUEL?
resolve_digraph(1, recipes, digraph)

# Part 2: How much FUEL can you make with 1 ORE.
# Actually, I started 'fuel' at 1 and ran for a while to collect
# data points.  I graphed it, found the approximate trend line,
# hedged low, and used that new number as my start point.
# It was only a few iterations before I found the real answer :)
fuel = 1934973
while True:
digraph = generate_digraph(recipes)
resolve_digraph(fuel, recipes, digraph)