8 votes

Day 14: Space Stoichiometry

Today's problem description: https://adventofcode.com/2019/day/14


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

3 comments

  1. Hvv
    Link
    Funky questions like these are always amazingly fun or absolutely terrifying. This one is more than a little of both. Part 1 Strategy Before we get to anything else, we need to make sure we know...

    Funky questions like these are always amazingly fun or absolutely terrifying. This one is more than a little of both.

    Part 1 Strategy Before we get to anything else, we need to make sure we know what exactly we're solving.

    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.

    Part 1 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';
    }
    
    Part 2 Strategy This one isn't actually 1 trillion / (Our Part 1 Answer), as much as we want it to be.

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

    Part 2 Code
    #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';
    }
    
    2 votes
  2. Crespyl
    (edited )
    Link
    This one took me the longest so far (other than Day 1, which I didn't start until very late), but I still finished at around the same rank that I have been which makes me feel a tad better...

    This one took me the longest so far (other than Day 1, which I didn't start until very late), but I still finished at around the same rank that I have been which makes me feel a tad better (1594/1431).

    I decided to start with the Ruby implementation first, since I knew I'd want to poke at it from the repl a bunch during testing. Unfortunately, I'd got used to Crystals pass-by-value stack-allocated struct behaviors, and Ruby likes to pass things by references. So when I parsed out the input into Rule and Value objects, the algorithm would do what I expected once, but alter the rules it was using during the process and fail every time after that. Tracking this down took me much longer than it should've, but I did get there in the end (freeze helped track down where the inappropriate writes were happening).

    Part 1 Spoilers

    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
    Part 1 Ruby
    #!/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))
    
    Part 2

    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
    

    Weirdly, the first pass of my Crystal port gets the correct answer for part 2, but outputs a slightly wrong value for part 1, despite the logic being more or less identical. Not sure where it's going wrong yet, but I can fix it later.

    2 votes
  3. Gyrfalcon
    Link
    Well I got distracted with the end of my semester and the start of the holiday season but I am trying to catch up if possible. Code below is for both parts in Python, split by file. Reaction.py...

    Well I got distracted with the end of my semester and the start of the holiday season but I am trying to catch up if possible. Code below is for both parts in Python, split by file.

    Reaction.py
    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]))
    
    Stoich.py
    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)
    
    2 votes