Contexte

En France, et probablement dans le reste de l'Union européenne, tout aliment disponible à la vente doit énumérer les ingrédients qui le composent sur son emballage, en ordre décroissant de pourcentage en poids . Cependant, le pourcentage exact ne doit pas être indiqué, à moins que l'ingrédient ne soit mis en évidence par le texte ou une image sur l'enveloppe.

Par exemple, ma sauce tomate au basilic, ne montrant que quelques grosses tomates rouges et de belles feuilles de basilic sur son emballage, présente les indications suivantes:

Ingrédients: Tomates 80%, oignons en morceaux, basilic 1,4%, sel de mer, purée d'ail, sucre de canne brut, huile d'olive extra vierge, poivre noir.

Cela semble salé, mais… combien d'oignons vais-je manger exactement?

Défi

À partir d’une liste de pourcentages en poids par ordre décroissant, éventuellement incomplet, créez une liste complète des pourcentages en poids minimal et maximal pouvant être trouvés dans la recette.

• Vous pouvez écrire une fonction ou un programme complet.
• L' entrée peut être sous n'importe quelle forme raisonnable (tableau de nombres ou liste de chaînes, par exemple). Les valeurs fractionnelles doivent être prises en charge avec au moins une décimale. Un pourcentage de poids manquant peut être représenté en aucune façon cohérente et sans ambiguïté ( 0, '?'ou null, par exemple). Vous pouvez supposer que l'entrée sera toujours associée à une recette valide ( [70]et [∅, ∅, 50]ne sera pas valide, par exemple).
• La sortie peut être sous n'importe quelle forme raisonnable (un tableau pour les pourcentages de poids minimal et maximal, ou une liste unique de doublets, par exemple). Les pourcentages minimal et maximal peuvent être dans n'importe quel ordre ( [min, max]et [max, min]sont tous deux acceptables). Les pourcentages pondéraux exacts n'ont pas besoin d'être traités différemment des autres pourcentages et peuvent être représentés par des valeurs égales minimale et maximale.

Les règles standard pour le code-golf s'appliquent: pendant que vous tapez votre code, mon plat de pâtes refroidit, la soumission la plus courte gagne.

Exemples

Étant donné que ce problème est plus complexe qu'il n'y parait à première vue, voici une résolution étape par étape de quelques cas.

[40, ∅, ∅]

Appelons respectivement xet yles deux pourcentages manquants.

• Parce qu'il vient après le premier ingrédient à 40%, xil ne peut être supérieur à 40%.
  [40, [?, 40], [?, ?]]
• La somme des deux pourcentages manquants est toujours de 60%. Par conséquent :
  • Si xprend sa valeur maximale , yprend alors sa valeur minimale , qui est donc de 60% à 40% = 20%.
    [40, [?, 40], [20, ?]]
  • Si xprend sa valeur minimale , yprend alors sa valeur maximale . Mais xne peut pas être inférieur à y, donc dans ce cas, x= y= 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Appelons respectivement x, yet zles trois pourcentages manquants.

• Les pourcentages minimal et maximal pour zsont nécessairement compris entre 0% et 5%. Supposons zun instant = 0%. La somme des deux pourcentages manquants est toujours de 25%. Par conséquent :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • Si yprend sa valeur minimale , 5%, xprend alors sa valeur maximale , qui est donc 25% - 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • Si yprend sa valeur maximale , xprend alors sa valeur minimale . Mais xne peut pas être inférieur à y, donc dans ce cas, x= y= 25% / 2 = 12,5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Vérifions que tout va bien si nous supposons maintenant que z= 5%. La somme des deux pourcentages manquants est toujours de 20%. Par conséquent :
  • Si yprend sa valeur minimale , 5%, xprend alors sa valeur maximale , qui est donc 20% - 5% = 15%. Ce cas est déjà inclus dans les plages calculées précédemment.
  • Si yprend sa valeur maximale , xprend alors sa valeur minimale . Mais xne peut pas être inférieur à y, donc dans ce cas, x= y= 20% / 2 = 10%. Ce cas est déjà inclus dans la plage précédemment calculée pour y, mais pas pour x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Cas de test

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]]

JavaScript (ES6), 252 octets

Attend 0des pourcentages manquants. Retourne une paire de valeurs minimum et maximum pour toutes les entrées.

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))

Essayez-le en ligne!

Comment?

Initialisation

Nous remplaçons d'abord chaque valeur du tableau d'entrée par un [] par la plage la plus grande possible.

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()

Exemples:

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

Fonction principale

La fonction principale est h () . Il recherche la première entrée qui semble être incohérente lorsque nous essayons de la minimiser ou de la maximiser. S'il en trouve un, il le met à jour avec une valeur au moins temporairement acceptable, compte tenu des autres plages.

Il prend en entrée soit M = Math.max / I = 0 ou M = Math.min / I = 1 et définit J comme I XOR 1 .

Comme h () a été écrit pour prendre en charge les passes minimizing et maximizing, le code est un peu difficile à commenter. C'est pourquoi nous allons nous concentrer uniquement sur le passage maximisant, pour lequel nous avons M = Math.max , I = 0 et J = 1 . Avec ces paramètres, le code se lit comme suit:

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

Récursion

La fonction récursive g () continue d'appeler h () jusqu'à ce que ni la passe minimisante ni la passe maximalisante ne conduisent à une nouvelle correction et finalement renvoie le résultat final.

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