Space Stoichiometry

Advent of Code 2019 Day 14

Task: Solve for X where...

Part 1

X = the minimum amount of ORE required to produce exactly 1 FUEL

Example input

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

It represents:

A list of reactions
Each line denotes one or more input and an output

Part 1

This feels like Handy Haversack
Carefully reading the rules
Attempting to manually evaluate each example input
Trying to write a recursive algorithm

This feels like Handy Haversack

The one-to-many relationship
The pairing of labels and quantities
The pathfinding from a target back to an origin (shiny gold bags)

I'm anxious about whether I can re-use any of the algorithms or data structures I wrote for that puzzle in this one.

Carefully reading the rules

Every reaction turns some quantities of specific input chemicals into some quantity of an output chemical

X INPUT (, Y INPUT?, Z INPUT?) => A OUTPUT

Almost every chemical is produced by exactly one reaction; the only exception, ORE, is the raw material input to the entire process and is not produced by a reaction

Mandatory:
X ORE => A OUTPUT

Won't happen:
X ORE (, Y INPUT?, Z INPUT?) => A OUTPUT

Won't happen:
X INPUT => A ORE

reactions cannot be partially run, so only whole integer multiples of these quantities can be used

XX INPUT => A OUTPUT

...cannot be used as:
X INPUT => 1/2A OUTPUT

It's okay to have leftover chemicals when you're done

XX INPUT => A OUTPUT

But only X was needed? That's ok

You can run the full reaction as many times as necessary

X INPUT, YY INPUT, ZZZ INPUT => A OUTPUT

For AAA OUTPUT:
XXX INPUT, YYYYYY INPUT, ZZZZZZZZZ INPUT

Attempting to manually evaluate each example input

Here is example 1 again:

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

Evaluating the equation

1 FUEL:
7A + 1E
7A + 7A + 1D
7A + 7A + 7A + 1C
7A + 7A + 7A + 7A + 1B
----------------------
              28A + 1B
              ??? ORE?
              10x + 1x
              30  + 1

                    31 CORRECT

Here is example 2:

9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL

Evaluating the equation

1 FUEL:
2 AB + 3 BC + 4 CA
6 A + 8 B + 15 B + 21 C + 16 C + 4 A
10 A + 23 B + 37 C
------------------
????????????? ORE?
2*5A   3*8B   5*8C
  5x     8x     8x
9 ORE  8 ORE  7 ORE
9*5  + 8*8  + 7*8
45   + 64   + 56

              165 CORRECT

Here is example 3, with labels adjusted for space:

157 ORE => 5 A
165 ORE => 6 B
44 C, 5 D, 1 E, 29 A, 9 F, 48 G => 1 FUEL
12 G, 1 F, 8 H => 9 E
179 ORE => 7 H
177 ORE => 5 G
7 B, 7 H => 2 C
165 ORE => 2 F
3 B, 7 A, 5 G, 10 H => 8 D

Evaluating the equation

1 FUEL:
44 C + 5 D + 1 E + 29 A + 9 F + 48 G
154 B + 154 H + 3 B + 7 A + 5 G + 10 H + 12 G + 1 F + 8 H + 29 A + 9 F + 48 G
157 B + 172 H + 36 A + 65 G + 10 F
6*27  + 7*25  + 5*8  + 5*13 + 2*5

  27      25      8      13     5
*165    *179   *157    *177  *165
---------------------------------
4455  + 4475 + 1256  + 2301 + 825

                            13312 CORRECT

Here is example 4, with labels adjusted for space:

2 A, 7 B, 2 C, 11 D => 1 E
17 F, 3 G => 8 A
53 E, 6 D, 46 H, 81 J, 68 C, 25 K => 1 FUEL
22 H, 37 D => 5 B
139 ORE => 4 F
144 ORE => 7 G
5 D, 7 L, 2 B, 2 A, 19 C => 3 J
5 H, 7 D, 9 A, 37 C => 6 K
145 ORE => 6 D
1 F => 8 C
1 H, 6 D => 4 L
176 ORE => 6 H

Evaluating the equation

1 FUEL:
53 E + 6 D + 46 H + 81 J + 68 C + 25 K

106A + 371 B + 106 C + 583 D + 6 D + 46 H + 135 D + 189 L + 54 B + 54 A + 513 C + 72 F + 25 H + 35 D + 45 A + 185 C

238 F + 42 G + 1650 H + 2775 D + 14 F + 583 D + 6 D + 46 H + 135 D + 48 H + 288 D + 242 H + 407 D + 119 F + 21 G + 65 F + 72 F + 25 H + 35 D + 102 F + 18 G + 24 F

F G D H
238 + 14 + 119 + 65 + 72 + 102 + 24 F
42 + 21 + 18 G
2775 + 583 + 6 + 135 + 288 + 407 + 35 D
1650 + 46 + 48 + 242 + 25 H

634 F + 81 G + 4229 D + 2011 H
4*159 + 7*12 + 6*705  + 6*336

  159     12     705      336
 *139   *144    *145     *176
-----------------------------
22101 + 1728+ 102225  + 59136

                       185190 WRONG, BUT CLOSE!
Should have been:      180797

Trying to write a recursive algorithm

The regular expression to parse each chemical and amount

For a line like this:

5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV

I want to extract:

(5, VJHF), (7, MNCFX), (9, VPVL), (37, CXFTF), (6, GNMV)

The simplest regular expression I got to work was:

/(\d+)\s(\w+)/g

Matching:

\d+ several digits
\s a space
\w+ several letters

I recognize I'll have to:

Run this on each line of input, not the whole input
Identify the last match as the key to which all other matches must be the linked list

The data structure for storing chemical relations

I'll use a dictionary/hash/object
Keys will be each chemical after the =>
Values will be a dictionary: a key for the amount, and a key for the list of required chemicals and amounts

An example of this data structure using example 1:

Input:
10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

Planned data structure:
A:
  Multiples: 10
  Chemicals: ORE: 10
B:
  Multiples: 1
  Chemicals: ORE: 1
C:
  Multiples: 1
  Chemicals: A: 7, B: 1
D:
  Multiples: 1
  Chemicals: A: 7, C: 1
E:
  Multiples: 1
  Chemicals: A: 7, D: 1
FUEL:
  Multiples: 1
  Chemicals: A: 7, E: 1

My malfunctioning recursive algorithm

Accept one input - a 2-element array:
  1. An integer representing the quantity of the chemical produced
  2. A string representing the chemical produced

  If the array associated with the key specified in item 2 has 'ORE' as its second item:
    Return the input array inside an array
  Else
    Return a mutated list of chemicals associated with the key specified in item 2, such that:
      Each integer at location 1 in each chemical's array is updated to reflect the multiple and minimum quantity needed
      Then, call this function on each resulting 2-element array

The function is supposed to return a list of 2-element arrays that represent each quantity of elements that are directly made from ORE
I call this function as part of a larger 2-step reduction process that generates an object with keys corresponding to each element and integer sums of all quantities...then multiplies each sum by the proper minimum quantity needed based on the multiplier

Running my algorithm on some example inputs

Example 1: CORRECT
Example 2: CORRECT
Example 3: CORRECT
Example 4: WRONG - Over by 1000+
Example 5: WRONG - Over by 10000+
Input: WRONG - Too high, as expected

I'm not sure what I'm missing.

And I suspect I may never know.

UPDATED:

I returned to Example 4
I wanted to retry manually calculating the minimum required ORE for one of the base chemicals: NVRVD
I followed the path from 1 FUEL down each reaction that included a chemical that included NVRVD

Here was my path and math:

          68 CXFTF:
            9 NVRVD : ORE
53 STKFG
    53 * 2 = 106 CXFTF :
            14 NVRVD : ORE
    53 * 2 = 106 VPVL :
            136 NVRVD : ORE
81 HVMC
    27 * 19 = 513 CXFTF : 
            65 NVRVD : ORE
    27 * 2 = 54 VPVL : 
            119 NVRVD : ORE
25 GNMV : 
    37 * 5 = 185 CXFTF :
            24 NVRVD : ORE
    5 * 9 = VPVL : 
            119 NVRVD : ORE

            486 NVRVD
            122 * 139  = 16958 ORE

In my initial attempt, I multiply 139 by 159 - nearly 40 greater than in this new round.

I suspect that my algorithm was rounding up too early in each recursive iteration.

I feel a bit better now knowing one instance of where my initial logic was flawed.

I still likely couldn't have written an algorithm to solve this puzzle.

Successes

I stepped through four examples, confirming the correct answers for 3/4
I wrote a recursive algorithm that generated the same amount of correct answers...and helped me spot an error in my math for the fourth example
I returned a few days later to attack one small part of the first example that my algorithm didn't solve correctly, and found a flaw in my logic