Find the capacity of 2D printed objects

Question

In a fictional 2D world, a set of 2D printing instructions for an object can be represented by a list of integers as follows:

1 4 2 1 1 2 5 3 4

Each number represents the height of the object at that particular point. The above list translates to the following object when printed:

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

We then fill it with as much water as we can, resulting in this:

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

We define the capacity of the object to be the units of water the object can hold when completely full; in this case, 11.

Strictly speaking, a unit of water (~) can exist at a location if and only if it is surrounded by two solid blocks (#) in the same row.

Challenge

Take a list of positive integers as input (in any format), and output the capacity of the object printed when the list is used as instructions.

You can assume the list contains at least one element and all elements are between 1 and 255.

Test Cases

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

Answer 1

Haskell, 53 bytes

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

Thanks to Wheat Wizard for saving 1 byte. See also their shorter 48-byte solution.

The expressions scanl1 max l and scanr1 max l compute the running maximum of the list reading forwards and backwards, i.e. the profile of the water plus land if water would go flow one direction.

Orig:

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

Left:

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

Right:

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

Then, the profile of the overall picture is the minimum of these, which corresponds to where the water does not leak either direction.

Minimum:

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

Finally, the amount of water is the sum of this list, which contains both water and land, minus the sum of the original list, which contains only land.

Answer 2

Jelly, 10 bytes

U»\U«»\S_S

While APL requires multiple parentheses, and J two-character symbols, the algorithm is beautiful in Jelly.

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

Try it here.

Answer 3

MATL, 14

My Matlab answer translated to MATL. xnor's algorithm.

Y>GPY>P2$X<G-s

Explanation

Y>: cummax() (input is implicitly pushed on the stack)

G: push input (again)

P: flip()

Y>: cummax()

P: flip()

2$X<: min([],[]) (two-argument minimum)

G: push input (again)

-: -

s: sum()

Answer 4

Haskell, 48 bytes

q!u@(x:t)=q-x+maximum u`min`max q x!t
q!_=q

(0!)

Attempt This Online!

Answer 5

Dyalog APL, 17 bytes

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

This is a monadic train that takes the input array on the right.

The algorithm is pretty much the same as xnor's, although I found it independently. It scans for the maximum in both directions (backwards by reversing the array, scanning, and reversing again), and finds the vectorized minimum of those. Then it subtracts the original array and sums.

The other way to do this would be to split the array at each location, but that's longer.

Try it here.

Answer 6

Matlab, 47

Also using xnor's algorithm.

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

Answer 7

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

This works by storing the high point on the left, and while iterating through each next point, finds the highest point to the right. If the current point is less than both the high points, then it adds the minimum difference to the cumulative volume.

Ungolfed code:

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

First time I've tried to golf anything, MATLAB doesn't seem the best to do it in....

Answer 8

Python 2, 68 bytes

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

Try it online!

Answer 9

Pip -l, 19 bytes

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

Takes input numbers as command-line arguments. Or, add the -r flag to take them as lines of stdin: Try it online!

Explanation

Unlike all the other answers, in Pip it was actually shorter to construct (a modified version of) the ASCII-art and count the water units.

We start with g, the list of arguments.

[1 4 2 1 5 2 3]

0Xg produces a list of strings of n zeros for each n in g.

[0 0000 00 0 00000 00 000]

ZD1 then zips these strings together, using 1 to fill in any gaps in the resulting rectangular nested list:

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

ST converts this list to a string. The -l flag specifies that lists are formatted as follows: every nested list is joined together without a separator, and at the top level the separator is newline. So we get this multiline string--essentially, the diagram of the object, but upside down:

0000000
1001000
1011010
1011011
1111011

We then find all matches of the regex `0.*0`. This matches the two outermost walls and everything between them on each line.

[0000000 001000 011010 0110]

J joins these strings together into one big string, and $+ sums it, giving the number of 1s--which is equal to the amount of water the object can hold.

6

Answer 10

Rust, 112 bytes

|l:&[u8]|{(0..).zip(l).scan(0,|a,(b,c)|{*a=(*a).max(*c);Some((*a).min(*l[b..].iter().max()?)-c)}).sum::<u8>()};

Playground Link

Basically min(max(..index),max(index..)-value

Answer 11

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)

Another port of @xnor's alghorithm.

Answer 12

Vyxal, 11 bytes

Ṙɖ∴Ṙ?ɖ∴Þ∵ε∑

Try it Online!