0
$\begingroup$

I am trying to make a function to calculate whether a given supply of reagents is sufficient to create a list of products at a given solution.

So for a list of products $$ (a_1, b_1), (a_2, b_2) ... (a_n, b_n) $$ where $a_n$ = concentration of solution (mol/L)

and $b_n$ = volume of solution (L)

and a list of supplies of the same format (concentration, volume)

How can I mathematically determine whether or not the supplies are sufficient to meet the demand, assuming I have infinite water to perform dilutions? Essentially, I'm trying to determine if I can create the "products" through any combination of dilutions of the finite and available supplies.

Dilution: If I have 500 L of a 2 mol/L solution, I can add 500 L of water to create 1000 L of a 1 mol/L solution. Thus, even a small amount of a very concentrated supply may satisfy many products.

Assumptions: Assume that for this situation, there is only one chemical at issue, and any "supply" can be used to satisfy any "product" . Heuristic solutions are usable if the % error is small (~ 5%). A product may also use many supplies, so long as the total volume of supply used is less than b. These lists are finite, but may contain thousands of items.

Attempts: I can think of a recursive way to perform this calculation, but it is computatioanlly expensive for a number of reasons related to the way this data is stored.

$\endgroup$
  • $\begingroup$ You should be able to convert to the number of moles and compare against the amount you have. That is, $\sum_{i} a_{i}b_{i} \leq n_{tot}$ $\endgroup$ – Zhe Jun 7 '17 at 15:36
  • $\begingroup$ @Zhe: If I have 300 quadrillion liters of a 0.00000000001 molar solution, I can never make 1 L of 1M solution, but I will have far more than 1 mol available. I can only dilute, not concentrate. $\endgroup$ – mstorkson Jun 7 '17 at 15:39
  • $\begingroup$ But you know that immediately... Am I missing an edge case? $\endgroup$ – Zhe Jun 7 '17 at 16:29
1
$\begingroup$

Order the lists of products and supplies so that the most concentrated solutions appear first.

Start on the first product solution (the most concentrated). If the first supply solution is less concentrated, give up, you can't win. Otherwise, calculate how much of the first supply solution you need to create this product. If you have enough to fill it, then subtract the needed amount and continue on to the next product solution. If not, then subtract the amount you could fill from the product amount, and move on the the next supply solution as needed.

If at some point your supply solution is less concentrated than the product solution, or if you run out of supply solutions when you still have product, there is no way to do it. Otherwise you have constructed a way to meet the demand.

[Proof of above claim: Suppose at some point in this algorithm, the supply solution is less concentrated than the product solution. Call the product solution concentration C. Then split the products into those at lower concentration than C, and those at equal or higher concentration than C. Call the second set X. In order to meet the demand for X, we need an amount of supply with concentration $\geq C$ at least equal to the total amount of chemical ($\sum_{i\in X} a_i b_i) $ in the product. But by the construction of the algorithm, we used all the supply solution that met this constraint, and it still wasn't enough. The rest of the claims seem clear enough]

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's the recursive solution I was talking about, the problem is that sorting an array is a big performance bottleneck, and this calculation could occur thousands of times in a short space. Thanks for that concentration check idea though, that is a quick exit out. I'm trying to find a way to see if I can do the experiment before I do it. This is basically doing the experiment and seeing if it fails. $\endgroup$ – mstorkson Jun 7 '17 at 15:41
  • $\begingroup$ Sorting an array can be done in $O(n\log{n})$ time. (See quicksort or mergesort). Since there is clearly no way to avoid at least a linear time problem (reading in the data is linear time), this isn't a big performance issue. $\endgroup$ – idontseethepoint Jun 7 '17 at 15:45
  • $\begingroup$ I guess I was thinking about the worst case scenario for the sort. I'll implement it and see if that works. $\endgroup$ – mstorkson Jun 7 '17 at 15:50
  • $\begingroup$ If you are really concerned about worst case, use merge sort, but if you know ahead of time worst case is likely, you should be able to sort those cases very quickly since there is an obvious pattern to the worst case (which is a different pattern depending on how you choose the pivot). Also, the first thing you should try is to use an existing sort method in your language (e.g. sorted in python or std::sort in C++) to save a lot of time $\endgroup$ – idontseethepoint Jun 7 '17 at 15:54
  • $\begingroup$ Well I'm in Javascript, so I'm quite concerned with how fast the user sees results of things. I think Array.sort() uses Merge-sort. $\endgroup$ – mstorkson Jun 7 '17 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.