Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 |
+-----------------+--------+
share|improve this question
4  
Conceptually related – Alex A. Jan 13 at 1:19

Haskell, 54 bytes

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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()

share|improve this answer
    
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, 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....

share|improve this answer

Matlab, 47

Also using xnor's algorithm.

@(x)sum(min(cummax(x),flip(cummax(flip(x))))-x)
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.