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

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

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

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

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

Comments

[Neil Gall]

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)
    print("Part 1 answer is :\(result)")
}

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
        }
    }

    print("Part 2 answer is :\(low)")
}

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 Symbols 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 {
  estimate = newEstimate;
  const neededEstimate = getNeededOre(estimate);
  newEstimate = Math.floor(estimate * TOTAL_ORE / neededEstimate);
} while (newEstimate > estimate)
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
    amount_made: 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)
    node.amount_made = batches * 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:
        recipes = parse(f.read())
        digraph = generate_digraph(recipes)

    # Part 1: How much ORE to make 1 FUEL?
    resolve_digraph(1, recipes, digraph)
    print(f"Amount of ore needed: {digraph['ORE'].amount_made}")

    # 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)
        if digraph["ORE"].amount_made > 1_000_000_000_000:
            print(f"{fuel - 1} fuel possible on a trillion ore.")
            break

        print(f"{fuel} fuel needs {digraph['ORE'].amount_made} ore.")
        fuel += 1