What's in my pasta sauce?

Question

Background

In France, and probably in the rest of the European Union, any food available for sale must list the ingredients that compose it on its packaging, in weight percentage descending order. However, the exact percentage doesn't have to be indicated, unless the ingredient is highlighted by the text or an image on the covering.

For example, my basil tomato sauce, showing only some big red tomatoes and beautiful basil leaves on its packaging, has the following indications:

Ingredients: Tomatoes 80%, onions in pieces, basil 1.4%, sea salt, mashed garlic, raw cane sugar, extra virgin olive oil, black pepper.

It sounds savoury, but… how much onions will I eat, exactly?

Challenge

Given a list of weight percentages in descending order, eventually incomplete, output a complete list of the minimal and maximal weight percentages that can possibly be found in the recipe.

• You can write either a function, or a full program.
• The input can be in any reasonable form (array of numbers or list of strings, for instance). Fractional values should be supported at least to one decimal place. A missing weight percentage can be represented in any consistent and unambiguous way (0, '?' or null, for instance). You can assume that the input will always be associated to a valid recipe ([70] and [∅, ∅, 50] are invalid, for instance).
• The output can be in any reasonable form (one array for both of the minimal and maximal weight percentages, or a single list of doublets, for instance). The minimal and maximal percentages can be in any order ([min, max] and [max, min] are both acceptable). Exact weight percentages don't need to be processed differently than other percentages and may be represented by equal minimal and maximal values.

Standard rules for code-golf apply: while you're typing your code, my pasta dish is cooling down, so the shortest submission wins.

Examples

Since this problem is harder than it may look at first glance, here is a step-by-step resolution of a few cases.

[40, ∅, ∅]

Let's call respectively x and y the two missing percentages.

• Because it comes after the first ingredient at 40%, x can't be higher than 40 % itself.
  [40, [?, 40], [?, ?]]
• The sum of the two missing percentages is always 60%. Consequently :
  • If x takes its maximal value, then y takes its minimal value, which is therefore 60% - 40% = 20%.
    [40, [?, 40], [20, ?]]
  • If x takes its minimal value, then y takes its maximal value. But x can't be lower than y, so in this case, x = y = 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Let's call respectively x, y and z the three missing percentages.

• The minimal and maximal percentages for z are necessarily between 0% and 5%. Let's assume z = 0% for a moment. The sum of the two missing percentages is always 25%. Consequently :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • If y takes its minimal value, 5%, then x takes its maximal value, which is therefore 25% - 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • If y takes its maximal value, then x takes its minimal value. But x can't be lower than y, so in this case, x = y = 25% / 2 = 12.5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Let's verify that everything is fine if we assume now that z = 5%. The sum of the two missing percentages is always 20%. Consequently :
  • If y takes its minimal value, 5%, then x takes its maximal value, which is therefore 20% - 5% = 15%. This case is already included in the previously calculated ranges.
  • If y takes its maximal value, then x takes its minimal value. But x can't be lower than y, so in this case, x = y = 20% / 2 = 10%. This case is already included in the previously calculated range for y, but not for x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Test cases

Input:  [∅]
Output: [100]

Input:  [70, 30]
Output: [70, 30]

Input:  [70, ∅, ∅]
Output: [70, [15, 30], [0, 15]]

Input:  [40, ∅, ∅]
Output: [40, [30, 40], [20, 30]]

Input:  [∅, ∅, 10]
Output: [[45, 80], [10, 45], 10]

Input:  [70, ∅, ∅, ∅]
Output: [70, [10, 30], [0, 15], [0, 10]]

Input:  [70, ∅, ∅, 5, ∅]
Output: [70, [10, 20], [5, 12.5], 5, [0, 5]]

Input:  [30, ∅, ∅, ∅, 10, ∅, ∅, 5, ∅, ∅]
Output: [30, [10, 25], [10, 17.5], [10, 15], 10, [5, 10], [5, 10], 5, [0, 5], [0, 5]]

Answer 1

JavaScript (ES6), 252 bytes

Expects 0 for missing percentages. Returns a pair of minimum and maximum values for all entries.

a=>(g=a=>(h=(M,I,J=I^1)=>a.some((x,i)=>a.map((y,j)=>s-=j-i?M(j,i)-i?y[I]:M(w=y[I],z=x[J])-z||w==z?w:++k&&z:y[J],s=100,k=1,X=x)&&(I?-s:s)<0)?X[J]=M(X[I],X[J]+s/k):0)(Math.max,0)+h(Math.min,1)?g(a):a)(a.map((n,i)=>[n?p=n:a.find(n=>i--<0&&n)||0,p],p=100))

Try it online!

How?

Initialization

We first replace each value in the input array a[ ] with the largest possible range.

a.map((n, i) =>       // for each value n at position i in a[]:
  [                   //   generate a [min, max] array:
    n ?               //     if n is not 0:
      p = n           //       use n as the minimum and save it in p
    :                 //     else:
      a.find(n =>     //       find the first value n
        i-- < 0 &&    //         which is beyond the current value
        n             //         and is not equal to 0
      ) || 0,         //       or use 0 as a default value
    p                 //     use p as the maximum
  ],                  //   end of array declaration
  p = 100             //   start with p = 100
)                     // end of map()

Examples:

[ 0 ] --> [ [ 0, 100 ] ]
[ 30, 0, 5, 0 ] --> [ [ 30, 30 ], [ 5, 30 ], [ 5, 5 ], [ 0, 5 ] ]

Main function

The main function is h(). It looks for the first entry that appears to be inconsistent when we try to either minimize or maximize it. If it finds one, it updates it to a value which is at least temporarily acceptable, given the other ranges.

It takes as input either M = Math.max / I = 0 or M = Math.min / I = 1 and defines J as I XOR 1.

Because h() was written to support both the minimizing and maximizing passes, the code is a bit tricky to comment. That's why we will focus on the maximizing pass only, for which we have M = Math.max, I = 0 and J = 1. With these parameters, the code reads as follows:

a.some((x, i) =>              // for each range x at position i in a[] (tested range):
  a.map((y, j) =>             //   for each range y at position j in a[] (reference range):
    s -=                      //     update s:
      j - i ?                 //       if i is not equal to j:
        Math.max(j, i) - i ?  //         if j > i:
          y[0]                //           the reference range is beyond the tested range
                              //           so we just use the minimum value of the y range
        :                     //         else:
          Math.max(           //           take the maximum of:
            w = y[0],         //             w = minimum value of the y range
            z = x[1]          //             z = maximum value of the x range
          ) - z ||            //           if it's not equal to z
          w == z ?            //           or they are equal (i.e. if w <= z):
            w                 //             use w
          :                   //           else:
            ++k && z          //             increment the counter k and use z
      :                       //       else:
        y[1],                 //         use the maximum value of the y range
    s = 100,                  //     start with s = 100
    k = 1,                    //     start with k = 1
    X = x                     //     save the range x in X
  ) &&                        //   end of map()
  (0 ? -s : s) < 0            //   abort if s < 0 (i.e. if we've subtracted more than 100)
) ?                           // end of some(); if truthy:
  X[1] = Math.max(            //   update the maximum value of the faulty range to:
    X[0],                     //     either the minimum value
    X[1] + s / k              //     or the maximum value, less the correction
  )                           //   whichever is greater
:                             // else:
  0                           //   do nothing

Recursion

The recursive function g() keeps calling h() until neither the minimizing or the maximizing pass leads to a new correction, and eventually returns the final result.

g = a => h(Math.max, 0) + h(Math.min, 1) ? g(a) : a