fundo

Na França, e provavelmente no resto da União Europeia, qualquer alimento disponível para venda deve listar os ingredientes que o compõem em sua embalagem, em ordem decrescente de porcentagem em peso . No entanto, a porcentagem exata não precisa ser indicada, a menos que o ingrediente seja destacado pelo texto ou uma imagem na capa.

Por exemplo, meu molho de tomate com manjericão, mostrando apenas grandes tomates vermelhos e lindas folhas de manjericão em sua embalagem, tem as seguintes indicações:

Ingredientes: Tomate 80%, cebola em pedaços, manjericão 1,4%, sal marinho, purê de alho, açúcar bruto de cana, azeite extra-virgem, pimenta do reino.

Parece saboroso, mas ... quantas cebolas vou comer exatamente?

Desafio

Dada uma lista de porcentagens de peso em ordem decrescente, eventualmente incompleta, produz uma lista completa das porcentagens de peso mínima e máxima que podem ser encontradas na receita.

• Você pode escrever uma função ou um programa completo.
• A entrada pode estar em qualquer forma razoável (matriz de números ou lista de cadeias, por exemplo). Os valores fracionários devem ser suportados pelo menos com uma casa decimal. Uma percentagem em peso em falta pode ser representado de qualquer maneira consistente e inequívoco ( 0, '?'ou null, por exemplo). Você pode assumir que a entrada sempre será associada a uma receita válida ( [70]e [∅, ∅, 50]é inválida, por exemplo).
• A saída pode estar em qualquer forma razoável (uma matriz para as porcentagens de peso mínima e máxima, ou uma única lista de dupletos, por exemplo). As porcentagens mínima e máxima podem estar em qualquer ordem ( [min, max]e [max, min]são aceitáveis). As porcentagens exatas de peso não precisam ser processadas diferentemente de outras porcentagens e podem ser representadas por valores mínimos e máximos iguais.

Aplicam -se regras padrão para o código-golfe : enquanto você digita seu código, meu prato de macarrão está esfriando, para que o menor envio seja vencido.

Exemplos

Como esse problema é mais difícil do que parece à primeira vista, aqui está uma resolução passo a passo de alguns casos.

[40, ∅, ∅]

Vamos chamar respectivamente xe yas duas porcentagens ausentes.

• Porque vem após o primeiro ingrediente em 40%, xnão pode ser superior a 40% em si.
  [40, [?, 40], [?, ?]]
• A soma das duas porcentagens ausentes é sempre 60%. Consequentemente :
  • Se xobtém seu valor máximo , yobtém seu valor mínimo , que é, portanto, de 60% a 40% = 20%.
    [40, [?, 40], [20, ?]]
  • Se xassume seu valor mínimo , yassume seu valor máximo . Mas xnão pode ser menor que y, portanto, neste caso, x= y= 60% / 2 = 30%.
    [40, [30, 40], [20, 30]]

[70, ∅, ∅, 5, ∅]

Vamos ligar respectivamente x, ye zas três porcentagens ausentes.

• As porcentagens mínima e máxima para zestão necessariamente entre 0% e 5%. Vamos assumir z= 0% por um momento. A soma das duas porcentagens ausentes é sempre de 25%. Consequentemente :
  [70, [?, ?], [?, ?], 5, [0, 5]]
  • Se yobtém seu valor mínimo , 5%, xobtém seu valor máximo , que é, portanto, de 25% a 5% = 20%.
    [70, [?, 20], [5, ?], 5, [0, 5]]
  • Se yassume seu valor máximo , xassume seu valor mínimo . Mas xnão pode ser menor que y, portanto, neste caso, x= y= 25% / 2 = 12,5%.
    [70, [12.5, 20], [5, 12.5], 5, [0, 5]]
• Vamos verificar se está tudo bem se assumirmos agora que z= 5%. A soma das duas porcentagens ausentes é sempre 20%. Consequentemente :
  • Se yobtém seu valor mínimo , 5%, xobtém seu valor máximo , que é, portanto, 20% - 5% = 15%. Este caso já está incluído nos intervalos calculados anteriormente.
  • Se yassume seu valor máximo , xassume seu valor mínimo . Mas xnão pode ser menor que y, portanto, neste caso, x= y= 20% / 2 = 10%. Este caso já está incluído no intervalo calculado anteriormente para y, mas não para x.
    [70, [10, 20], [5, 12.5], 5, [0, 5]]

Casos de teste

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 bytes

Espera 0por porcentagens ausentes. Retorna um par de valores mínimo e máximo para todas as entradas.

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

Experimente online!

Quão?

Inicialização

Primeiro, substituímos cada valor na matriz de entrada a [] pelo maior intervalo possível.

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

Exemplos:

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

Função principal

A função principal é h () . Ele procura a primeira entrada que parece inconsistente quando tentamos minimizá-la ou maximizá-la. Se encontrar um, ele será atualizado para um valor que seja pelo menos temporariamente aceitável, considerando os outros intervalos.

Ele assume como entrada M = Math.max / I = 0 ou M = Math.min / I = 1 e define J como I XOR 1 .

Como h () foi escrito para oferecer suporte a passes minimizadores e maximizadores, o código é um pouco complicado de comentar. É por isso que focaremos apenas no passe maximizador, para o qual temos M = Math.max , I = 0 e J = 1 . Com esses parâmetros, o código lê da seguinte maneira:

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

Recursão

A função recursiva g () continua chamando h () até que a passagem minimizadora ou a maximização não leve a uma nova correção e, eventualmente, retorne o resultado final.

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