W fikcyjnym świecie 2D zestaw instrukcji drukowania 2D dla obiektu może być reprezentowany przez listę liczb całkowitych w następujący sposób:

1 4 2 1 1 2 5 3 4

Każda liczba reprezentuje wysokość obiektu w tym konkretnym punkcie. Powyższa lista po wydrukowaniu tłumaczy na następujący obiekt:

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

Następnie napełniamy go możliwie dużą ilością wody, co powoduje:

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

Definiujemy pojemność obiektu jako jednostki wody, które obiekt może utrzymać, gdy jest całkowicie pełny; w tym przypadku 11.

Ściśle mówiąc, jednostka wody ( ~) może istnieć w miejscu tylko wtedy, gdy jest otoczona dwoma stałymi blokami ( #) w tym samym rzędzie.

Wyzwanie

Weź listę dodatnich liczb całkowitych jako dane wejściowe (w dowolnym formacie) i wyświetl pojemność obiektu wydrukowanego, gdy lista jest używana jako instrukcja.

Możesz założyć, że lista zawiera co najmniej jeden element, a wszystkie elementy mają wartość od 1 do 255.

Przypadki testowe

+-----------------+--------+
|      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 bajty

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

Wyrażenia scanl1 max li scanr1 max lobliczają maksymalną liczbę odczytów listy do przodu i do tyłu, tj. Profil wody plus ląd, jeśli woda płynie w jednym kierunku.

Orig:

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

Lewo:

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

Dobrze:

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

Profil ogólnego obrazu jest więc ich minimum, co odpowiada miejscu, w którym woda nie przecieka w żadnym kierunku.

Minimum:

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

Wreszcie ilość wody jest sumą tej listy, która zawiera zarówno wodę, jak i ziemię, pomniejszoną o sumę oryginalnej listy, która zawiera tylko ziemię.

Galaretka, 10 bajtów

U»\U«»\S_S

Podczas gdy APL wymaga wielu nawiasów i dwuznakowych symboli J, algorytm jest piękny w galaretce.

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

Wypróbuj tutaj .

MATL , 14

Moja odpowiedź Matlaba przetłumaczona na MATL. algorytm xnora.

Y>GPY>P2$X<G-s

Wyjaśnienie

Y>: cummax()(dane wejściowe są domyślnie wypychane na stos)

G: push input (ponownie)

P: flip()

Y>: cummax()

P: flip()

2$X<: min([],[])(minimum dwa argumenty)

G: push input (ponownie)

-: -

s: sum()

Dyalog APL, 17 bajtów

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

Jest to monadyczny ciąg, który bierze tablicę wejściową po prawej stronie.

Algorytm jest prawie taki sam jak xnor, chociaż znalazłem go niezależnie. Skanuje maksimum w obu kierunkach (wstecz poprzez odwrócenie tablicy, skanowanie i cofanie ponownie) i znajduje wektoryzowane minimum tych. Następnie odejmuje oryginalną tablicę i sumuje.

Innym sposobem na to byłoby podzielenie tablicy w każdej lokalizacji, ale to dłużej.

Wypróbuj tutaj .

Matlab, 47

Również przy użyciu algorytmu xnor.

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

MATLAB, 116 113 109 106 bajtów

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

Działa to poprzez zapisanie najwyższego punktu po lewej stronie i podczas iteracji przez każdy następny punkt znajduje najwyższy punkt po prawej stronie. Jeśli bieżący punkt jest mniejszy niż oba najwyższe punkty, dodaje minimalną różnicę do objętości skumulowanej.

Nieskluczony kod:

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

Za pierwszym razem, gdy próbowałem grać w golfa, MATLAB nie wydaje się najlepszy w ...

ES6, 101 bajtów

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)

Kolejny port algorytmu @ xnor.

Python 2 , 68 bajtów

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

Wypróbuj online!

Pip -l , 19 bajtów

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

Pobiera liczby wejściowe jako argumenty wiersza poleceń. Lub dodaj -rflagę, aby wziąć je jako linie standardowe: Wypróbuj online!

Wyjaśnienie

W przeciwieństwie do wszystkich innych odpowiedzi, w Pipie zbudowanie (zmodyfikowana wersja) sztuki ASCII i policzenie jednostek wodnych było krótsze.

Zaczynamy god listy argumentów.

[1 4 2 1 5 2 3]

0Xgtworzy listę ciągów n zer dla każdego n w g.

[0 0000 00 0 00000 00 000]

ZD1następnie zamyka te ciągi razem, 1wypełniając wszelkie luki w wynikowej prostokątnej liście zagnieżdżonej:

[[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]]

STkonwertuje tę listę na ciąg. W -lOkreśla flag że listy są sformatowane w następujący sposób: każda lista zagnieżdżona jest połączone bez separatora, a na najwyższym poziomie separatorem jest znak nowej linii. Otrzymujemy więc ten ciąg multilinii - zasadniczo schemat obiektu, ale do góry nogami:

0000000
1001000
1011010
1011011
1111011

Następnie znajdujemy wszystkie dopasowania wyrażenia regularnego `0.*0`. To pasuje do dwóch najbardziej zewnętrznych ścian i wszystkiego między nimi w każdej linii.

[0000000 001000 011010 0110]

Jłączy te ciągi razem w jeden duży ciąg i $+sumuje je, podając liczbę 1s - równą ilości wody, którą może pomieścić obiekt.

6