DEV Community

Robert Mion
Robert Mion

Posted on • Updated on

Space Stoichiometry

#adventofcode #algorithms #computerscience #programming

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

It represents:

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

Part 1

  1. This feels like Handy Haversack
  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

  • 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

XX INPUT => A OUTPUT

But only X was needed? That's ok
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

I want to extract:

(5, VJHF), (7, MNCFX), (9, VPVL), (37, CXFTF), (6, GNMV)
Enter fullscreen mode Exit fullscreen mode

The simplest regular expression I got to work was:

/(\d+)\s(\w+)/g
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)

Read next

khai-jt profile image

Move hardcoded secrets to a Secrets Manager

Khai J. Thani -

ridoy_hasan profile image

How to Set Up Your JavaScript Development Environment

Ridoy Hasan -

trixsec profile image

Build a Python Bot to Automate Social Media Engagement

Trix Cyrus -

dmitry-koleev profile image

"What Every Programmer Should Know About Memory" by Ulrich Drepper.

Dmitry Koleev -