This is a question I came across while going through some questions on alchemy puzzles. It seems pretty hard for me.The question stands:
You are studying alchemy and want to create the philosopher's stone. You have a grimoire full of recipes for the transmutations. Being methodical, you numbered all ingredients starting from 0, and wrote down all the transmutations in terms of ingredients required to perform them and their products. Thus, for each recipe t from the grimoire you know that it requires ingredient[t] ingredients, and that it produces product[t] ingredients after the transmutation.
You can perform a transmutation t only if you have enough ingredients in your inventory. More formally, for each ingredient i it should be true that inventory[i] ≥ ingredient[t][i].
When the transmutation is performed, the ingredients are consumed and the products are created. More formally, for each ingredient i your inventory changes as follows:
inventory[i] = inventory[i] - ingredient[t][i] + products[t][i]
You want to compute the shortest sequence of transmutations that produces the stone. Find the number of transmutations in the order they should be performed.
It is guaranteed that it is possible to create the philosopher's stone. The shortest solution is guaranteed to be unique.
for ingredients= \begin{bmatrix} 0 & 8 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 5 & 9 & 3 \\ 0 & 8 & 2 & 5 & 8 & 1 \\ 0 & 3 & 0 & 0 & 4 & 5 \\ 0 & 0 & 1 & 4 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{bmatrix}
and for products= \begin{bmatrix} 0 & 6 & 3 & 0 & 4 & 0 \\ 4 & 4 & 0 & 5 & 3 & 9 \\ 0 & 1 & 4 & 3 & 4 & 8 \\ 0 & 5 & 0 & 9 & 0 & 0 \\ 0 & 4 & 0 & 7 & 0 & 3 \\ 0 & 0 & 0 & 0 & 2 & 7 \\ \end{bmatrix} and for inventory = [ 0, 6, 8, 4, 2, 0 ], the answer is [4,0,0,1] I just need to understand the mathematics behind this problem and how have they solved it.
I just want to confirm that the process describe by the answer is as follows:
$$\begin{array}{c|c|c} \text{Recipe} & \text{Action} & \text{Inventory}\\ \hline \text{(Initial)} & - & [ 0, 6, 8, 4, 2, 0 ]\\ 4 & [0,0,1,4,0,0] \to [0,4,0,7,0,3] & [0,10,7,7,2,3]\\ 0 & [0,8,0,0,0,0] \to [0,6,3,0,4,0] & [0,8,10,7,6,3] \\ 0 & [0,8,0,0,0,0] \to [0,6,3,0,4,0] & [0,6,13,7,10,3]\\ 1 & [0,0,3,5,9,3] \to [4,4,0,5,3,9] & [\color{red}4,10,10,7,4,9]\\ \end{array}$$
with the final state of inventory$[0]$ being not one but four philosopher's stones.
As for how to solve it; the key ingredients for recipe $[1]$ need to be generated, and a fairly simply review shows the most efficient way to do that.