Em um mundo 2D fictício, um conjunto de instruções de impressão 2D para um objeto pode ser representado por uma lista de números inteiros da seguinte maneira:

1 4 2 1 1 2 5 3 4

Cada número representa a altura do objeto naquele ponto específico. A lista acima se traduz no seguinte objeto quando impressa:

      #
 #    # #
 #    ###
 ##  ####
#########

Em seguida, enchemos com o máximo de água possível, resultando no seguinte:

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Definimos a capacidade do objeto como unidades de água que ele pode reter quando completamente cheio; neste caso, 11.

A rigor, uma unidade de água ( ~) pode existir em um local se e somente se estiver cercada por dois blocos sólidos ( #) na mesma linha.

Desafio

Pegue uma lista de números inteiros positivos como entrada (em qualquer formato) e imprima a capacidade do objeto impresso quando a lista for usada como instruções.

Você pode assumir que a lista contém pelo menos um elemento e todos os elementos estão entre 1 e 255.

Casos de teste

+-----------------+--------+
|      Input      | Output |
+-----------------+--------+
| 1               |      0 |
| 1 3 255 1       |      0 |
| 6 2 1 1 2 6     |     18 |
| 2 1 3 1 5 1 7 1 |      7 |
| 2 1 3 1 7 1 7 1 |      9 |
| 5 2 1 3 1 2 5   |     16 |
| 80 80 67 71     |      4 |
+-----------------+--------+

Haskell, 54 bytes

f l=(sum$zipWith min(scanl1 max l)$scanr1 max l)-sum l

As expressões scanl1 max le scanr1 max lcalculam o máximo de execução da lista lendo para frente e para trás, ou seja, o perfil da água mais a terra, se a água fluir em uma direção.

Orig:

      #
 #    # #
 #    ###
 ##  ####
#########

Esquerda:

      #~~
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Direita:

~~~~~~#
~#~~~~#~#
~#~~~~###
~##~~####
#########

Então, o perfil da imagem geral é o mínimo destes, que corresponde a onde a água não vaza em nenhuma direção.

Mínimo:

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Finalmente, a quantidade de água é a soma desta lista, que contém água e terra, menos a soma da lista original, que contém apenas terra.

Gelatina, 10 bytes

U»\U«»\S_S

Enquanto o APL requer vários parênteses e J símbolos de dois caracteres, o algoritmo é bonito no Jelly.

     »\          Scan maximums left to right
U»\U             Scan maximums right to left
    «            Vectorized minimum
       S_S       Sum, subtract sum of input.

Experimente aqui .

MATL , 14

Minha resposta do Matlab foi traduzida para o MATL. algoritmo do xnor.

Y>GPY>P2$X<G-s

Explicação

Y>: cummax()(a entrada é empurrada implicitamente na pilha)

G: pressionar entrada (novamente)

P: flip()

Y>: cummax()

P: flip()

2$X<: min([],[])(mínimo de dois argumentos)

G: pressionar entrada (novamente)

-: -

s: sum()

Dyalog APL, 17 bytes

+/⊢-⍨⌈\⌊⌽∘(⌈\⌽)

Este é um trem monádico que leva a matriz de entrada à direita.

O algoritmo é praticamente o mesmo que o xnor, embora eu o tenha encontrado de forma independente. Ele verifica o máximo nas duas direções (para trás, invertendo a matriz, digitalizando e invertendo novamente) e encontra o mínimo vetorizado daquelas. Em seguida, subtrai a matriz original e as somas.

A outra maneira de fazer isso seria dividir a matriz em cada local, mas isso é mais longo.

Experimente aqui .

Matlab, 47

Também usando o algoritmo do xnor.

@(x)sum(min(cummax(x),flip(cummax(flip(x))))-x)

MATLAB, 116 113 109 106 Bytes

n=input('');s=0;v=0;l=nnz(n);for i=1:l-1;a=n(i);w=min([s max(n(i+1:l))]);if a<w;v=v+w-a;else s=a;end;end;v

Isso funciona armazenando o ponto alto à esquerda e, enquanto itera em cada próximo ponto, encontra o ponto mais alto à direita. Se o ponto atual for menor que os dois pontos altos, ele adicionará a diferença mínima ao volume acumulado.

Código não destruído:

inputArray = input('');
leftHighPoint = inputArray(1);
volume = 0;
numPoints = nnz(inputArray);

for i = 1:numPoints-1
    currentPoint = inputArray(i); % Current value
    lowestHigh = min([max(inputArray(i+1:numPoints)) leftHighPoint]);

    if currentPoint < lowestHigh
        volume = volume + lowestHigh - currentPoint;
    else 
        leftHighPoint = currentPoint;
    end
end
volume

A primeira vez que tentei jogar golfe, o MATLAB não parece o melhor para fazê-lo ....

ES6, 101 bytes

a=>(b=[],a.reduceRight((m,x,i)=>b[i]=m>x?m:x,0),r=m=0,a.map((x,i)=>r+=((m=x>m?x:m)<b[i]?m:b[i])-x),r)

Outra porta do algoritmo do @ xnor.

Python 2 , 68 bytes

lambda l:sum(min(max(l[:i+1]),max(l[i:]))-v for i,v in enumerate(l))

Experimente online!

Pip -l , 19 bytes

$+J(ST0XgZD1`0.*0`)

Aceita números de entrada como argumentos de linha de comando. Ou adicione a -rbandeira para tomá-las como linhas de stdin: Experimente online!

Explicação

Ao contrário de todas as outras respostas, em Pip era realmente mais curto construir (uma versão modificada) da arte ASCII e contar as unidades de água.

Começamos com ga lista de argumentos.

[1 4 2 1 5 2 3]

0Xgproduz uma lista de cadeias de n zeros para cada n pol g.

[0 0000 00 0 00000 00 000]

ZD1depois fecha essas seqüências de caracteres, usando 1para preencher as lacunas na lista aninhada retangular resultante:

[[0 0 0 0 0 0 0] [1 0 0 1 0 0 0] [1 0 1 1 0 1 0] [1 0 1 1 0 1 1] [1 1 1 1 0 1 1]]

STconverte esta lista em uma string. O -lsinalizador especifica que as listas são formatadas da seguinte forma: todas as listas aninhadas são unidas sem um separador e, no nível superior, o separador é uma nova linha. Portanto, obtemos essa sequência multilinha - essencialmente, o diagrama do objeto, mas de cabeça para baixo:

0000000
1001000
1011010
1011011
1111011

Em seguida, encontramos todas as correspondências da regex `0.*0`. Isso corresponde às duas paredes mais externas e a tudo entre elas em cada linha.

[0000000 001000 011010 0110]

June essas cordas em uma grande e $+soma, fornecendo o número de 1s - que é igual à quantidade de água que o objeto pode conter.

6