Day 14: Space Stoichiometry

It's quite clearly graph related, and we pick out that each chemical (except the start) is produced by exactly one reaction (this will be important later on) and that we're trying to get to an end chemical (FUEL).

The graph you use is up to you, since this one doesn't explicitly define a particular graph, but our graph construction will work as follows:

In the graph each vertex represents a chemical and has weighted edges from a chemical to all the ones used to make it, where A -> B with weight W means that A needs W of B to make it (We're exploiting the fact that every A can only be made 1 way here)

We're using this graph representation so that we can "propagate out" the material needs from the 1 FUEL to each of its dependencies, eventually converging on ORE, which has no dependencies.

In essence, if we know that we need at least N of A and that the formula that makes A makes M amount of it but takes P and Q amounts of B and C, we then know that we will need to make ceil(N/M) batches of A, which adds ceil(N/M)*P and ceil(N/M)*Q additional amounts of B and C when accounting for A.

Doing this for all the materials in the right order will get us back to ORE, and that big number will be our final answer.

Of course, "right order" isn't trivial here, since it isn't obvious to know when you have all of a material accounted for and when you can say to "propagate out" its dependencies.

However, assuming our input doesn't have a dependency hell hidden in it (which it shouldn't), this graph has no cycles, and for acyclic graphs other smart people have thought about it before.

Using a Topological Sort, we can ensure that every node is completely accounted for when we propagate out its dependencies (the below code uses Kahn's algorithm but any one of these will do), and, running this through until we reach ORE, we can just output how much of ORE is needed according to the graph.

From the top:

1. Construct a graph with weighted edges from product to reactants, weighted by how much is needed
2. For each chemical, keep track of how much of it is needed at any given time
3. Start with the requirement of 1 FUEL. Using the order prescribed by some topological sort, take each chemical and add the minimum required number of each of the ingredients used to make it (ceil(N/M)*W for N product needed, M made by recipe, and W needed ingredient per recipe)
4. Return the recorded ORE requirement.

Aside for input parsing: I know that at least in C++, string parsing is pretty bad, so you'll have to fiddle with that too. My (mildly gross) approach is prefaced in the code.

/*
 * String parsing in C++ sucks, so the input parsing in the below code is doing
   the following: 
 * For each ingredient, get its number and the word after it. 
 * If that word has a comma in it, keep doing so until it doesn't 
	(if you look at the ingredient list, only the last ingredient
	 before the "=>" has a comma)
 * Then, suck up the "=>" and get the number and name of the final product
 * To process all of these, use a map to assign an ID number to each string, 
	and construct the graph based on the ID numbers
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> al;
const ll MAXN = 100100;
vii g[MAXN];
ll pr[MAXN];
vi ond;
vi ind;
ll num[MAXN];
map<string,int> ms;
int get(string& s) {
	int res = ms.size();
	if(ms.find(s) == ms.end()) {
		ms[s] = res;
		ond.push_back(0);
		return res;
	}
	return ms[s];
}
int main() {
	memset(num,0,sizeof(num));
	while(1) {
		ll n;
		string s;
		if(!(cin >> n)) {break;}
		cin >> s;
		int id = get(s);
		vii w;
		while(s.back() == ',') {
			string t = s.substr(0,s.size()-1);
			w.push_back({ll(n),ll(get(t))});
			cin >> n >> s;
		}
		w.push_back({ll(n),ll(get(s))});
		cin >> s;
		cin >> n >> s;
		int fin = get(s);
		pr[fin] = n;
		for(int i=0;i<w.size();i++) {
			ii a = w[i];
			g[fin].push_back({a.second,a.first});
			ond[a.second]++;
		}
	}
	ind = ond;
	string sts = "FUEL";
	string stt = "ORE";
	int start = get(sts);
	int dest = get(stt);
	queue<int> q;
	q.push(start);
	memset(num,0,sizeof(num));
	num[start] = 1;
	while(!q.empty()) {
		int u = q.front();q.pop();
		if(u == dest) break;
		ll val = (num[u]+pr[u]-1)/pr[u];
		for(int i=0;i<g[u].size();i++) {
			int v = g[u][i].first;
			ll co = g[u][i].second;
			ind[v]--;
			num[v] += val*co;
			if(ind[v] == 0) {
				q.push(v);
			}
		}
	}
	cout << num[dest] << '\n';
}

This is because we can reuse leftover materials from making the first FUEL unit to make the next with less materials, but this issue isn't hard to solve.

Note that from our part 1 construction we simply set 1 to our initial FUEL count, then ran a graph thing to get the minimum number of ORE to make 1 FUEL.

So instead of setting 1 to the initial count, we can set it to N for any N, run the graph thing, and get the minimum number of ORE to make N FUEL.

We definitely need to do this multiple times, so we have to set up stuff to store the initial graph conditions, but other than that, we can just test values for N to find out the biggest one that takes <= 10^12 ORE.

Of course, to do this in a structured way we can use binary search (yay algorithms!) where a FUEL amount that needs at most 10^12 ORE is a "success" (increase the lower bound) and one that needs more than 10^12 is a "failure" (decrease the upper bound), where you can return the last "success".

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> al;
const ll MAXN = 100100;
vii g[MAXN];
ll pr[MAXN];
vi ond;
vi ind;
ll num[MAXN];
map<string,int> ms;
int get(string& s) {
	int res = ms.size();
	if(ms.find(s) == ms.end()) {
		ms[s] = res;
		ond.push_back(0);
		return res;
	}
	return ms[s];
}
int main() {
	memset(num,0,sizeof(num));
	while(1) {
		ll n;
		string s;
		if(!(cin >> n)) {break;}
		cin >> s;
		int id = get(s);
		vii w;
		while(s.back() == ',') {
			string t = s.substr(0,s.size()-1);
			w.push_back({ll(n),ll(get(t))});
			cin >> n >> s;
		}
		w.push_back({ll(n),ll(get(s))});
		cin >> s;
		cin >> n >> s;
		int fin = get(s);
		pr[fin] = n;
		for(int i=0;i<w.size();i++) {
			ii a = w[i];
			g[fin].push_back({a.second,a.first});
			ond[a.second]++;
		}
	}
	ind = ond;
	ll st = 1,ed = 1e12;
	ll tril = 1000000000000;
	string sts = "FUEL";
	string stt = "ORE";
	ll res = 1;
	int start = get(sts);
	int dest = get(stt);
	while(st <= ed) {
		ll mid = (st+ed)/2;
		queue<int> q;
		q.push(start);
		memset(num,0,sizeof(num));
		num[start] = mid;
		ind = ond;
		while(!q.empty()) {
			int u = q.front();q.pop();
			if(u == dest) break;
			ll val = (num[u]+pr[u]-1)/pr[u];
			for(int i=0;i<g[u].size();i++) {
				int v = g[u][i].first;
				ll co = g[u][i].second;
				ind[v]--;
				num[v] += val*co;
				if(ind[v] == 0) {
					q.push(v);
				}
			}
		}
		if(num[dest] <= tril) {
			res = mid;
			st = mid+1;
		} else {
			ed = mid-1;
		}
	}
	cout << res << '\n';
}

Parsing the input was straight forward, I chose to use Value (tuple of name and amount) and Rule objects, which was easy but as I mentioned above I think it caused more trouble than it was worth. Keeping everything as simpler numbers where possible would helped avoid the mutating objects issue I ran into.

Once I had the rules parsed out into a map, we know how much of each resource it takes to produce any given resource, and to get the total ore we can walk the algorithm backwards.

There are three important functions:

reqs_for_value takes in a Value (resource "R" and amount "N") and returns a list of values required to produce at least N units of R, and if the rules used result in any excess R floating around, we also return the amount of extra R produced in the reaction. So for the first sample problem, if I need to get the requirements for 14 A, then the function returns [20 ORE], 6.

collapse_values is more of a utility function to take a list of values and merge any values with the same resource into one. So if we have 10 A, 3 ORE, 3 A it will return 13 A, 3 ORE. I think switching to a hashmap might've allowed me to skip this step. This is used to help keep our working set tidy while we're running.

breakdown is the actual solution to Part 1, this walks the ore production process backwards, deducing how much of each resource were produced and consumed along the way. We have our working set values, and we loop until either we run out of values in the set or the only resource left is ORE.

It works like this:

• Take a value needed out of the working set (1 FUEL to begin)
• Find its requirements reqs and the amount of extra that will be produced
• For each requirement:
• • check if we have already PRODUCED more of that resource than we have CONSUMED; if so update this instance of the requirement (not the one in the rule itself) and increase our CONSUMED counter for the required resource
• • after adjusting the requirement to account for consumed excess, increase our CONSUMED counter by the amount still needed by the requirement (which might be 0 if the entire amount was available)
• Once we've done this for each requirement, we increase our PRODUCED value by the amount of needed + the amount of extra produced during the reaction.
• Add each of the updated reqs to the working set

#!/usr/bin/env ruby
require_relative "../lib/utils.rb"

Value = Struct.new(:resource, :amount)

class Rule
  attr_accessor :output
  attr_accessor :requirements

  def initialize(reqs, output)
    @requirements = reqs
    @output = output
  end

  def to_s
    "%s => %s" % [@requirements.map(&:to_s).join(', '), @output]
  end
end

def parse_value(str)
  m = str.match(/(\d+)\s+(\w+)/)
  Value.new(m[2],m[1].to_i).freeze if m
end

def parse_rule(str)
  reqs, out = str.split(" => ")
  reqs = reqs.split(", ").map{ |s| parse_value(s) }

  out = parse_value(out)

  Rule.new(reqs, out).freeze
end

def parse_file(filename)
  File.read(filename)
    .lines
    .map(&:chomp)
    .map { |line| parse_rule(line) }
    .each_with_object({}) { |rule, hash| hash[rule.output.resource] = rule }
    .freeze
end

# take a list that might contain several values with the same resource and fold
# them into one value for each resource
def collapse_values(values)
  values.each_with_object(Hash.new { |h,k| h[k] = 0 }) { |v,h|
    h[v.resource] += v.amount
  }.map { |k,v| Value.new(k,v) }
end

# get the requirements necessary to produce the requested value
def reqs_for_value(rules, value)
  rule = rules[value.resource]
  return [[],0]  unless rule && value.amount > 0
 
  reqs = rule.requirements.map { |v| Value.new(v.resource, v.amount) }
  excess = 0

  if rule.output.amount >= value.amount
    # one application of this rule is enough
    excess = rule.output.amount - value.amount
  else
    # we need a multiple of the values
    extras = (value.amount / rule.output.amount) + (value.amount % rule.output.amount == 0 ? 0 : 1)
    reqs = reqs.map { |req| Value.new(req.resource, req.amount * extras) }
    excess = (rule.output.amount * extras) - value.amount
  end
  [reqs, excess]
end

# Breakdown a value into the amount of ore necessary to produce it
#
# The basic idea is to walk the provided ORE => FUEL formula backwards. For any
# given value with rule (m X => n Y) we do the following:
#
#  given (n Y) in our working set,
#  note that we have PRODUCED (n Y),
#  remove (n Y) from the working set,
#  state that we must have CONSUMED (m X),
#  add (m X) to the working set
#
# the difference between the amount PRODUCED and CONSUMED for any given resource
# is considered available, and can be used to reduce the requirements for the
# next rule that needs them.
def breakdown(rules, value)
  values = [value]

  produced = Hash.new(0)
  consumed = Hash.new(0)

  # Keep iterating over our list of available values, until all that's left is ORE
  while ! values.empty? && ! values.all? { |v| v.resource == "ORE" }
    values = collapse_values(values) # make sure we fold the list down and don't
                                     # have two or more clumps of the same
                                     # resource at once

    # select one value to examine and get is requirements, along with any excess
    # that will be produced
    needed = values.shift
    reqs, extra = reqs_for_value(rules, needed)

    reqs.each do |req|
      # for each requirement
      available = produced[req.resource] - consumed[req.resource]
      if produced[req.resource] > 0 && produced[req.resource] >= consumed[req.resource]
        # if we have some spares available, modify the required amount and note
        # the consumption
        if available >= req.amount
          consumed[req.resource] += req.amount
          req.amount = 0
        elsif available > 0 && available < req.amount
          consumed[req.resource] += available
          req.amount -= available
        end
      end

      # having updated the required amount to account for any already available,
      # we note the consumption
      consumed[req.resource] += req.amount
    end

    # now that we processed all the requirements, we can state that we produced
    # some amount
    produced[needed.resource] += needed.amount + extra

    # and we add the requirements to our working set so that we can keep
    # following the chain
    values += reqs
  end

  # lastly we just pull out the amount of ore we consumed during the process
  consumed["ORE"]
end

INPUT = Utils.cli_param_or_default(0,"day14/input.txt")
rules = parse_file(INPUT)

# part 1
puts "Part 1: %i" % breakdown(rules, Value.new("FUEL", 1))

Once Part 1 is working correctly, it's relatively easy (still took me a while to fix an off-by-one and port to Crystal) to write a binary search to find the biggest amount of fuel that can be produced without going over an ORE requirement of one trillion.

def find_max_fuel_for_ore(rules, ore)
  low, high = 0, ore
  pivot = low + ((high-low) / 2)

  while (pivot != high && pivot != low)
    case breakdown(rules, Value.new("FUEL", pivot)) <=> ore
    when  0 then break
    when  1 then high = pivot
    when -1 then low = pivot
    end

    pivot = low + ((high-low) / 2)
  end

  pivot
end

class Reaction(object):

    def __init__(self, output, inputs):
        self.output_id = output[1]
        self.output_num = int(output[0])

        self.input_ids = []
        self.input_nums = []

        for input in inputs:
            self.input_ids.append(input[1])
            self.input_nums.append(int(input[0]))

import Reaction
import math

def parse_reactions(file_name):

    with open(file_name, 'r') as fid:
        data = fid.readlines()

    reactions = {}

    for line in data:
        inputs = line.split("=>")[0].strip()
        outputs = line.split("=>")[1].strip()
        inputs = inputs.split(",")
        inputs = [x.strip() for x in inputs]
        inputs = [x.split(" ") for x in inputs]
        outputs = outputs.split(" ")
        new_reaction = Reaction.Reaction(outputs, inputs)
        reactions[new_reaction.output_id] = new_reaction

    return reactions

def produce_compound(reactions, output_id, num_needed):
    current_reaction = reactions[output_id]
    ore_total = 0

    try:
        current_extra = produce_compound.extra[current_reaction.output_id]
    except KeyError:
        produce_compound.extra[current_reaction.output_id] = 0
        current_extra = 0

    if num_needed <= current_extra:
        produce_compound.extra[current_reaction.output_id] -= num_needed
        return 0
    elif num_needed > current_extra:
        num_needed -= current_extra
        produce_compound.extra[current_reaction.output_id] = 0

    num_reactions = math.ceil(num_needed / current_reaction.output_num)
    produce_compound.extra[current_reaction.output_id] = num_reactions * current_reaction.output_num - num_needed


    for idx in range(len(current_reaction.input_ids)):
        if current_reaction.input_ids[idx] == 'ORE':
            ore_total += num_reactions*current_reaction.input_nums[idx]
        else:
            ore_total += produce_compound(reactions, current_reaction.input_ids[idx], num_reactions*current_reaction.input_nums[idx])

    return ore_total



input_file = "PuzzleInput.txt"
test_files = ["Test1_1.txt", "Test1_2.txt", "Test1_3.txt", "Test1_4.txt", "Test1_5.txt"]
test_outputs = [31, 165, 13312, 180697, 2210736]

for idx in range(len(test_files)):

    reactions = parse_reactions(test_files[idx])
    produce_compound.extra = {}
    ore = produce_compound(reactions, 'FUEL', 1)
    assert ore == test_outputs[idx]

reactions = parse_reactions(input_file)
produce_compound.extra = {}
ore = produce_compound(reactions, 'FUEL', 1)
print(ore)

needed_ore = 0
num_fuel = int(1e12) // ore

for i in range(5):
    produce_compound.extra = {}
    needed_ore = produce_compound(reactions, 'FUEL', num_fuel)
    num_fuel = math.floor((int(1e12) / needed_ore)*num_fuel)
    print(num_fuel)

while True:

    needed_ore_old = needed_ore
    produce_compound.extra = {}
    needed_ore = produce_compound(reactions, 'FUEL', num_fuel)
    print(needed_ore)

    if needed_ore > int(1e12) and needed_ore_old > int(1e12):
        num_fuel -= 1
        continue
    elif needed_ore > int(1e12) and needed_ore_old < int(1e12):
        num_fuel -= 1
        break
    elif needed_ore < int(1e12) and needed_ore_old > int(1e12):
        break
    elif needed_ore < int(1e12) and needed_ore_old < int(1e12):
        num_fuel += 1
        continue


print(num_fuel)