Задний план

Во Франции и, вероятно, в остальной части Европейского Союза, любая пища, имеющаяся в наличии для продажи, должна перечислять ингредиенты, которые ее составляют, на упаковке в порядке убывания веса . Тем не менее, точный процент не должен быть указан, если ингредиент не выделен текстом или изображением на обложке.

Например, мой томатный соус с базиликом, на упаковке которого есть только несколько больших красных помидоров и красивые листья базилика, имеет следующие признаки:

Ингредиенты: помидоры 80%, лук кусочками, базилик 1,4%, морская соль, пюре из чеснока, тростниковый сахар-сырец, оливковое масло первого отжима, черный перец.

Это звучит несладко, но ... сколько я буду есть , точно?

Вызов

Учитывая список весовых процентов в порядке убывания, в конечном итоге неполный, выведите полный список минимального и максимального весовых процентов, которые могут быть найдены в рецепте.

• Вы можете написать либо функцию, либо полную программу.
• Вход может быть в любой разумной форме (массив чисел или список строк, например). Дробные значения должны поддерживаться как минимум с одним десятичным знаком. Отсутствующий весовой процент может быть представлен в любом последовательном и недвусмысленном способе ( 0, '?'или null, к примеру). Вы можете предположить, что входные данные всегда будут связаны с действительным рецептом ( [70]и [∅, ∅, 50], например, неверны).
• Выход может быть в любой разумной форме (один массив для обоих из минимального и максимального процентного веса, или один список дублетов, например). Минимальный и максимальный проценты могут быть в любом порядке ( [min, max]и [max, min]оба приемлемы). Точные весовые проценты не должны обрабатываться иначе, чем другие проценты, и могут быть представлены равными минимальными и максимальными значениями.

Применяются стандартные правила для code-golf : пока вы набираете код, мое блюдо с пастой охлаждается, поэтому выигрывает самое короткое представление.

Примеры

Поскольку эта проблема сложнее, чем может показаться на первый взгляд, здесь приведено пошаговое решение нескольких случаев.

[40, ∅, ∅]

Давайте назовем соответственно xи yдва пропущенных процента.

• Потому что он идет после первого ингредиента на 40%, xне может быть выше, чем 40%.
  [40, [?, 40], [?, ?]]
• Сумма двух пропущенных процентов всегда составляет 60%. Следовательно :
  • Если xпринимает его максимальное значение, то yпринимает его минимальное значение, которое поэтому составляет 60% - 40% = 20%.
    [40, [?, 40], [20, ?]]
  • Если xпринимает минимальное значение, то yпринимает максимальное значение. Но xне может быть ниже y, поэтому в этом случае x= y= 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Давайте назовем соответственно x, yи zтри недостающие проценты.

• Минимальный и максимальный проценты для zобязательно находятся между 0% и 5%. Давайте предположим z= 0% на мгновение. Сумма двух пропущенных процентов всегда составляет 25%. Следовательно :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • Если yпринимает минимальное значение 5%, то xпринимает максимальное значение, которое, следовательно, составляет 25% - 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • Если yпринимает его максимальное значение, то xпринимает его минимальное значение. Но xне может быть ниже y, поэтому в этом случае x= y= 25% / 2 = 12,5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Давайте проверим, что все в порядке, если предположить, что z= 5%. Сумма двух пропущенных процентов всегда составляет 20%. Следовательно :
  • Если yпринимает минимальное значение 5%, то xпринимает максимальное значение, которое, следовательно, составляет 20% - 5% = 15%. Этот случай уже включен в ранее рассчитанные диапазоны.
  • Если yпринимает максимальное значение, то xпринимает минимальное значение. Но xне может быть ниже y, поэтому в этом случае x= y= 20% / 2 = 10%. Этот случай уже включен в ранее рассчитанный диапазон дляy , но не для x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Контрольные примеры

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 байта

Ожидания 0для недостающих процентов. Возвращает пару минимальных и максимальных значений для всех записей.

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

Попробуйте онлайн!

Как?

инициализация

Сначала мы заменим каждое значение во входном массиве a [] на максимально возможный диапазон.

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

Примеры:

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

Основная функция

Основная функция это h () . Он ищет первую запись, которая кажется непоследовательной, когда мы пытаемся минимизировать или максимизировать ее. Если он находит его, он обновляет его до значения, которое по крайней мере временно приемлемо, учитывая другие диапазоны.

Он принимает в качестве входных данных либо M = Math.max / I = 0, либо M = Math.min / I = 1 и определяет J как I XOR 1 .

Поскольку h () был написан для поддержки как минимизации, так и максимизации проходов, код немного сложно комментировать. Вот почему мы сосредоточимся только на максимальном проходе, для которого имеем M = Math.max , I = 0 и J = 1 . С этими параметрами код выглядит следующим образом:

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

Рекурсия

Рекурсивная функция g () продолжает вызывать h () до тех пор, пока ни минимизирующий, ни максимизирующий проход не приведут к новой коррекции и в конечном итоге не вернут окончательный результат.

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