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

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')

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

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)

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

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

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

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

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()

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;
}, {});

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);

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);

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