Hintergrund

In Frankreich und wahrscheinlich auch in der übrigen Europäischen Union müssen zum Verkauf stehende Lebensmittel die Zutaten, aus denen sie bestehen, in absteigender Reihenfolge in Gewichtsprozent auf ihrer Verpackung vermerken . Der genaue Prozentsatz muss jedoch nicht angegeben werden, es sei denn, die Zutat wird durch den Text oder ein Bild auf dem Cover hervorgehoben.

Zum Beispiel hat meine Basilikum-Tomatensauce, die nur einige große rote Tomaten und schöne Basilikumblätter auf ihrer Verpackung zeigt, die folgenden Angaben:

Zutaten: Tomaten 80%, Zwiebeln in Stücken, Basilikum 1,4%, Meersalz, Knoblauchpüree, Rohrohrzucker, Olivenöl extra vergine, schwarzer Pfeffer.

Es klingt wohlschmeckend, aber… wie viel Zwiebeln esse ich genau?

Herausforderung

Bei einer Liste der Gewichtsprozente in absteigender Reihenfolge, die eventuell unvollständig ist, wird eine vollständige Liste der minimalen und maximalen Gewichtsprozente ausgegeben , die möglicherweise im Rezept enthalten sind.

• Sie können entweder eine Funktion oder ein vollständiges Programm schreiben.
• Die Eingabe kann in einer beliebigen vernünftigen Form erfolgen (z. B. ein Array von Zahlen oder eine Liste von Zeichenfolgen). Bruchwerte sollten mindestens bis zu einer Dezimalstelle unterstützt werden. Ein fehlender Gewichtsanteil kann in jede konsistenten und eindeutigen Weise (dargestellt werden 0, '?'oder null, zum Beispiel). Sie können davon ausgehen, dass die Eingabe immer einem gültigen Rezept zugeordnet wird ( [70]und [∅, ∅, 50]beispielsweise ungültig ist).
• Die Ausgabe kann in jeder vernünftigen Form erfolgen (z. B. ein Array für den minimalen und den maximalen Gewichtsprozentsatz oder eine einzelne Liste von Dubletten). Der minimale und der maximale Prozentsatz können in beliebiger Reihenfolge angegeben werden ( [min, max]und [max, min]sind beide akzeptabel). Genaue Gewichtsprozente müssen nicht anders als andere Prozente verarbeitet werden und können durch gleiche Minimal- und Maximalwerte dargestellt werden.

Es gelten die Standardregeln für Code-Golf : Während Sie Ihren Code eingeben, kühlt sich mein Nudelgericht ab, sodass die kürzeste Einsendung gewinnt.

Beispiele

Da dieses Problem schwieriger ist, als es auf den ersten Blick erscheinen mag, finden Sie hier eine schrittweise Lösung für einige Fälle.

[40, ∅, ∅]

Nennen wir jeweils xund ydie beiden fehlenden Prozentsätze.

• Da es nach der ersten Zutat zu 40% kommt, xkann es nicht höher als 40% sein.
  [40, [?, 40], [?, ?]]
• Die Summe der beiden fehlenden Prozentsätze beträgt immer 60%. Folglich :
  • Wenn xsein nimmt Maximalwert, dann ynimmt ihren minimalen Wert, der somit beträgt 60% - 40% = 20%.
    [40, [?, 40], [20, ?]]
  • Wenn xseine dauert minimal Wert, dann ynimmt seinen maximalen Wert. Aber xkann nicht niedriger sein als y, so in diesem Fall x= y= 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Nennen wir jeweils x, yund zdie drei fehlenden Prozente.

• Die minimalen und maximalen Prozentsätze für zliegen notwendigerweise zwischen 0% und 5%. Nehmen wir zfür einen Moment = 0% an. Die Summe der beiden fehlenden Prozentsätze beträgt immer 25%. Folglich :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • Wenn ysein nimmt minimalen Wert, 5%, dann xnimmt seinen Maximalwert, der somit 25% - 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • Wenn yseine dauert maximal Wert, dann xnimmt seinen minimalen Wert. Aber xkann nicht niedriger sein als y, so in diesem Fall x= y= 25% / 2 = 12,5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Lassen Sie uns überprüfen, ob alles in Ordnung ist, wenn wir jetzt davon ausgehen, dass z= 5%. Die Summe der beiden fehlenden Prozentsätze beträgt immer 20%. Folglich :
  • Wenn ysein nimmt minimalen Wert, 5%, dann xnimmt seinen Maximalwert, der somit 20% - 5% = 15%. Dieser Fall ist bereits in den zuvor berechneten Bereichen enthalten.
  • Wenn yseine dauert maximal Wert, dann xnimmt seinen minimalen Wert. Aber xkann nicht niedriger sein als y, so in diesem Fall x= y= 20% / 2 = 10%. Dieser Fall ist bereits in dem zuvor berechneten Bereich für enthalten y, jedoch nicht für x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Testfälle

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 Byte

Erwartet 0fehlende Prozentsätze. Gibt ein Paar von Minimal- und Maximalwerten für alle Einträge zurück.

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

Probieren Sie es online!

Wie?

Initialisierung

Wir ersetzen zuerst jeden Wert im Eingabearray a [] durch den größtmöglichen Bereich.

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

Beispiele:

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

Hauptfunktion

Die Hauptfunktion ist h () . Es sucht nach dem ersten Eintrag, der inkonsistent zu sein scheint, wenn wir versuchen, ihn zu minimieren oder zu maximieren. Wenn es einen findet, aktualisiert es ihn auf einen Wert, der angesichts der anderen Bereiche zumindest vorübergehend akzeptabel ist.

Es nimmt als Eingabe entweder M = Math.max / I = 0 oder M = Math.min / I = 1 und definiert J als I XOR 1 .

Da h () geschrieben wurde, um sowohl das Minimieren als auch das Maximieren von Übergängen zu unterstützen, ist der Code etwas schwierig zu kommentieren. Deshalb konzentrieren wir uns nur auf den Maximierungsdurchlauf, für den wir M = Math.max , I = 0 und J = 1 haben . Mit diesen Parametern lautet der Code wie folgt:

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

Rekursion

Die rekursive Funktion g () ruft solange h () auf, bis weder der Minimierungs- noch der Maximierungsdurchlauf zu einer neuen Korrektur führt und schließlich das Endergebnis zurückgibt.

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