Day 14: Space Stoichiometry

---

Links:

• Puzzle on adventofcode.com
• Source Code

I didn’t properly read the puzzle’s description (again…) and so I ended up discarding excess chemicals instead of using them for future reactions which uses much more ore than it would otherwise. The thing is, I decided to use proper structs which made fixing the issue a lot harder than it otherwise would have been.

I love how I keep being punished for using structs. I had this really nice dynamic programming approach where the “ore per chemical” is only calculated once. Oh well…

To solve the first part for real, I added support for keeping track of leftovers. For each input chemical it is first checked whether there is some of it left from previous reactions and the existing quantity is deducted from the one needed. Nothing fancy, really, but I really appreciated using structs because it made “scaling” the reactions to produce sufficient output really easy.

I was very optimistic for the second part. I thought thanks to the power of Rust I could just repeat the reaction until there is no more ore left. Disappointingly, the reaction doesn’t use enough ore to complete in a reasonable amount of time.

A better way to find the amount of fuel we can produce for a given amount of ore is to just guess a number and check how much ore it requires to generate that amount of fuel. If we’re left with ore to spare we just guess a bigger number. Likewise, if we end up using too much ore, we guess a smaller number. Now we repeat this until we find the biggest amount of fuel that requires at most the amount of ore we have access to.

Instead of just guessing random numbers we can try to be smart about it. We could just use an exponential search which first narrows down the range of possible values and then uses binary search to find the exact value. The narrowing down is done by finding the first exponent, $j$, where producing $2^j$ fuel takes more ore than we have. Once found we know that the exact amount of fuel $x$ has to lie in the range $2^{j-1} < x < 2^j$. The second phase, binary search, is done by checking the value in the middle of the range. If it uses too much ore discard the upper half and run binary search on the lower half. Similarly, if it uses too little ore discard the lower half and run it on the upper half. If we happen to hit the exact amount of ore required we’re done and can return that amount of fuel. Repeat this until there is only one value left. That value is the most fuel we can produce without going over the ore limit.

This might sound a bit wonky, but it works probably.

But we can do better!

Assume $f(n) = m$, where $f$ is the function to calculate the amount of fuel $m$ we get from $n$ ore. If we multiply $n$ and $m$ by a scalar $i \in \mathbb{N}_1$ we get the inequality $f(n * i) \ge m * i$. In other words, if we have $i$ times the amount of ore, we know that we can produce at least $i$ times more fuel. This is because it takes some amount of ore to generate one fuel, but the more fuel we make, the more leftovers we have from previous reactions which makes it so the following reactions use less ore. The more fuel we create, the less ore we need on average.

Knowing this we can define the function $g$ to derive the next guess based on the result of the current one:

$$g(0) = 1$$ $$g(n) = \lfloor (g(n - 1) + 1) * \frac {o_{max}} {o_n} \rfloor$$

Where $o_n$ is the amount of ore it takes to produce $g(n - 1) + 1$ fuel ($o_n = f(g(n - 1) + 1)$) and $o_{max}$ is the amount of ore we’re allowed to use.

To put it simply, if the current guess used half of the available ore, the next guess will be around twice the current guess. When close to the correct amount of fuel $\frac {o_{max}} {o_n} \approx 1$ so $g$ becomes $g(n) \approx g(n - 1) + 1$.

Once $o_n \gt {o_{max}}$ is reached, we know that the previous guess ($o_{n-1}$) is the solution. This method manages to reach the correct amount in only 4 steps (for my input).

Well, that went on for far too long. See you tomorrow!

---

Overview
Previous day Next day