Space Stoichiometry
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-12 23:28:48

## [Advent of Code 2019 Day 14](https://adventofcode.com/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
1. This feels like [Handy Haversack](https://dev.to/rmion/handy-haversack-2o15)
2. Carefully reading the rules
3. Attempting to manually evaluate each example input
4. Trying to write a recursive algorithm

### This feels like [Handy Haversack](https://dev.to/rmion/handy-haversack-2o15)
- 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:
```js
/(\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

### Bummer:
- I failed to solve either part

I was really hoping I would at least solve Part 1.

Oh well. Time to move on.