tło

We Francji i prawdopodobnie w pozostałej części Unii Europejskiej każda żywność dostępna do sprzedaży musi zawierać składniki, które składają się na jej opakowaniu, w procentach wagowych malejącej . Jednak dokładny procent nie musi być wskazany, chyba że składnik jest wyróżniony przez tekst lub obraz na okładce.

Na przykład mój sos pomidorowy z bazylią, zawierający tylko kilka dużych czerwonych pomidorów i piękne liście bazylii na opakowaniu, ma następujące wskazania:

Składniki: Pomidory 80%, cebula w kawałkach, bazylia 1,4%, sól morska, tłuczony czosnek, surowy cukier trzcinowy, oliwa z oliwek z pierwszego tłoczenia, czarny pieprz.

Brzmi pikantnie, ale… ile dokładnie zjem cebuli ?

Wyzwanie

Biorąc pod uwagę listę wartości procentowych masy w porządku malejącym, ostatecznie niekompletną, wypisz pełną listę minimalnych i maksymalnych wartości procentowych masy, jakie można znaleźć w przepisie.

• Możesz napisać funkcję lub pełny program.
• Dane wejściowe mogą mieć dowolną rozsądną formę (na przykład tablicę liczb lub listę ciągów znaków). Wartości ułamkowe powinny być obsługiwane co najmniej z jednym miejscem po przecinku. Brakująca Procent wagowy może być przedstawiona w każdej spójny i jednoznaczny sposób ( 0, '?'lub null, na przykład). Możesz założyć, że dane wejściowe zawsze będą powiązane z prawidłową recepturą ( [70]i [∅, ∅, 50]na przykład są nieprawidłowe).
• Dane wyjściowe mogą być w dowolnej rozsądnej formie (na przykład jedna tablica dla obu minimalnych i maksymalnych wartości procentowych masy lub pojedyncza lista dubletów). Minimalne i maksymalne wartości procentowe mogą być w dowolnej kolejności ( [min, max]i [max, min]obie są dopuszczalne). Dokładne procenty wagowe nie muszą być przetwarzane inaczej niż inne procenty i mogą być reprezentowane przez równe wartości minimalne i maksymalne.

Obowiązują standardowe zasady gry w golfa : podczas pisania kodu moje danie z makaronem ochładza się, więc wygrywa najkrótsze zgłoszenie.

Przykłady

Ponieważ ten problem jest trudniejszy, niż może się wydawać na pierwszy rzut oka, oto rozwiązanie kilku przypadków krok po kroku.

[40, ∅, ∅]

Zadzwońmy odpowiednio xi ydwa brakujące procenty.

• Ponieważ występuje po pierwszym składniku w 40%, xnie może być wyższy niż 40% sam.
  [40, [?, 40], [?, ?]]
• Suma dwóch brakujących wartości procentowych wynosi zawsze 60%. W konsekwencji :
  • Jeśli xprzyjmuje maksymalną wartość, yprzyjmuje minimalną wartość, która wynosi 60% - 40% = 20%.
    [40, [?, 40], [20, ?]]
  • Jeśli xprzyjmuje minimalną wartość, yprzyjmuje maksymalną wartość. Ale xnie może być niższy niż y, więc w tym przypadku x= y= 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Nazwijmy odpowiednio x, ya ztrzy brakujące procenty.

• Minimalne i maksymalne wartości procentowe obowiązkowo zwynoszą od 0% do 5%. Załóżmy przez zchwilę = 0%. Suma dwóch brakujących wartości procentowych wynosi zawsze 25%. W konsekwencji :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • Jeśli yprzyjmuje minimalną wartość, 5%, to xprzyjmuje maksymalną wartość, która wynosi 25% - 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • Jeśli yprzyjmuje maksymalną wartość, xprzyjmuje minimalną wartość. Ale xnie może być niższy niż y, więc w tym przypadku x= y= 25% / 2 = 12,5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Sprawdźmy, czy wszystko jest w porządku, jeśli przyjmiemy, że teraz z= 5%. Suma dwóch brakujących wartości procentowych wynosi zawsze 20%. W konsekwencji :
  • Jeśli yprzyjmuje minimalną wartość, 5%, to xprzyjmuje maksymalną wartość, która wynosi 20% - 5% = 15%. Ten przypadek jest już uwzględniony w uprzednio obliczonych zakresach.
  • Jeśli yprzyjmuje maksymalną wartość, xprzyjmuje minimalną wartość. Ale xnie może być niższy niż y, więc w tym przypadku x= y= 20% / 2 = 10%. Ten przypadek jest już uwzględniony w uprzednio obliczonym zakresie dla y, ale nie dla x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Przypadki testowe

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 bajty

Oczekuje 0brakujących wartości procentowych. Zwraca parę minimalnych i maksymalnych wartości dla wszystkich wpisów.

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

Wypróbuj online!

W jaki sposób?

Inicjalizacja

Najpierw zamieniamy każdą wartość w tablicy wejściowej a [] na możliwie największy zakres.

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

Przykłady:

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

Główna funkcja

Główną funkcją jest h () . Poszukuje pierwszego wpisu, który wydaje się niespójny, gdy próbujemy go zminimalizować lub zmaksymalizować. Jeśli ją znajdzie, aktualizuje ją do wartości, która jest co najmniej tymczasowo dopuszczalna, biorąc pod uwagę inne zakresy.

Przyjmuje jako dane wejściowe M = Math.max / I = 0 lub M = Math.min / I = 1 i definiuje J jako I XOR 1 .

Ponieważ h () zostało napisane w celu obsługi zarówno minimalizacji, jak i maksymalizacji przejść, kod jest nieco trudny do skomentowania. Dlatego skupimy się tylko na przejściu maksymalizacyjnym, dla którego mamy M = Math.max , I = 0 i J = 1 . Przy tych parametrach kod brzmi następująco:

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

Rekurencja

Funkcja rekurencyjna g () ciągle wywołuje h (), dopóki przejście minimalizujące lub maksymalizujące nie prowadzi do nowej korekty i ostatecznie nie zwraca wyniku końcowego.

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