# Find the capacity of 2D printed objects

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 |
+-----------------+--------+
``````
-
Conceptually related – Alex A. Jan 13 at 1:19

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

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.

-

## 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.

-

## 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.

-
Exactly the same I came here to write. :-) When we get the dual (a.k.a under) operator, you can save 3 bytes with `+/⊢-⍨⌈\⌊⌈\⍢⌽`. – Adám Jan 13 at 9:34

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

-
Is MATL a substitution language of Matlab? Can you provide a link in the header? – VTCAKAVSMoACE Jan 13 at 14:03
@FlagAsSpam I think it's a bit more than that: esolangs.org/wiki/MATL – Martin Ender Jan 13 at 14:06
@MartinBüttner Would the pseudocode for this be identical to the Matlab pseudocode? I'm wondering if it's a direct translation thing, rather than a based on thing. – VTCAKAVSMoACE Jan 13 at 14:08
@FlagAsSpam MATL is stack-based, so it's definitely not a plain substitution. – Martin Ender Jan 13 at 14:08
Yes, it's a direct translation. MATL is stack based (reverse polish notation) with one to three character shorthands for MATLAB operators and functions. See [github.com/lmendo/MATL/blob/master/doc/MATL_spec.pdf]. – Rainer P. Jan 13 at 14:10

## MATLAB, 116113109 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....

-

# Matlab, 47

Also using xnor's algorithm.

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

## 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.

-