Retaining Water

Question

Your task is to check the volume of water in a pool. Your have to create a program that takes in a input that is represented by an 10 by 10 grid of integers, with heights ranging from A=1 to Z=26 from the latin alphabet. Find the volume of water each pool can hold.

You have to output the volume of water that the pool can hold. Outside the pool the height is 0, so no water is held on the cells at the edge of the pool. The water does not leak diagonally.

Test cases

ZZZZZZZZZZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZAAAAAAAAZ
ZZZZZZZZZZ
    OR
[[26, 26, 26, 26, 26, 26, 26, 26, 26, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 1, 1, 1, 1, 1, 1, 1, 1, 26], [26, 26, 26, 26, 26, 26, 26, 26, 26, 26]]
->
1600

ZZZZZZZZZZ
ZRRRRRRRRZ
ZRRRRRRRRZ
ZRRRRRRRRZ
ZFFFFFFFFZ
ZDDDDDDDDZ
ZDDDDDDDDZ
ZDDDDDDDDZ
ZDDDDDDDDZ
ZZZZZZZZZZ
    OR
[[26, 26, 26, 26, 26, 26, 26, 26, 26, 26], [26, 18, 18, 18, 18, 18, 18, 18, 18, 26], [26, 18, 18, 18, 18, 18, 18, 18, 18, 26], [26, 18, 18, 18, 18, 18, 18, 18, 18, 26], [26, 6, 6, 6, 6, 6, 6, 6, 6, 26], [26, 4, 4, 4, 4, 4, 4, 4, 4, 26], [26, 4, 4, 4, 4, 4, 4, 4, 4, 26], [26, 4, 4, 4, 4, 4, 4, 4, 4, 26], [26, 4, 4, 4, 4, 4, 4, 4, 4, 26], [26, 26, 26, 26, 26, 26, 26, 26, 26, 26]]
->
1056

XXXXXXXXXX
XSSSSRAAAX
XSSSSRAAAX
XSSSSRAAAX
XXXXXCXXXX
XSSSSCBBBX
XSSSSCBBBX
RSSSSCBBBX
XSSSSCBBBX
XXXXXXXXXX
    OR
[[24, 24, 24, 24, 24, 24, 24, 24, 24, 24], [24, 19, 19, 19, 19, 18, 1, 1, 1, 24], [24, 19, 19, 19, 19, 18, 1, 1, 1, 24], [24, 19, 19, 19, 19, 18, 1, 1, 1, 24], [24, 24, 24, 24, 24, 3, 24, 24, 24, 24], [24, 19, 19, 19, 19, 3, 2, 2, 2, 24], [24, 19, 19, 19, 19, 3, 2, 2, 2, 24], [18, 19, 19, 19, 19, 3, 2, 2, 2, 24], [24, 19, 19, 19, 19, 3, 2, 2, 2, 24], [24, 24, 24, 24, 24, 24, 24, 24, 24, 24]]
->
449

ZZZZZZZZZZ
RAAAAZEEEZ
RAAAAZEEEZ
RAAAAZEEEZ
RAAAAZEEEZ
RAAAAAEEEZ
RAAAAZEEEZ
RAAAAZEEEZ
QAAAAZEEEZ
ZZZZZZZZZZ
    OR
[[26, 26, 26, 26, 26, 26, 26, 26, 26, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [18, 1, 1, 1, 1, 1, 5, 5, 5, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [18, 1, 1, 1, 1, 26, 5, 5, 5, 26], [17, 1, 1, 1, 1, 26, 5, 5, 5, 26], [26, 26, 26, 26, 26, 26, 26, 26, 26, 26]]
->
816

The input is in the form of a 2D list of integers. The one with letters is just a reference (You can input it as letters if you want to)

Worked Example:

For the 1st test case: There is only 1 box and that is 10 lines of 26 or A's, and since this a pool, the A, represents the bottom of the pool, and the Z is the top, so 26-1=25 is the depth of the entire pool. Take 25*8*8=1600, as the Z is the wall so only a 8*8 area is occupied.

Test Case 3 has a R in the outer row of X, so do take note the water level cannot go past this

Test Case 4:

The lowest wall is Q, so we take 17-1=16 as the highest water level for maximum height of A=1. We take 16*4*8=512, next there is a Z wall, BUT there is an A breaking through the wall, which is connecting all the E to the wall of height 16, so the max height of the water level of E is 17-5=12, and take 12*3*8=288. Finally, we take 512+12+288=816(12 comes from the extra A inside the Z wall)

Tips:

Think of this challenge as water held in many different boxes inside a large box

Others:

• You may assume that all inputs are from the alphabet and that they are all uppercase
• You may assume that the outer row of alphabets do not always have the highest height, and can all have different heights
• The outer row MUST have a higher level than the 2nd outermost row due to the rule of no overflowing
• Water level cannot be higher than the highest "wall"

Scoring

This is code-golf, so shortest code wins!

Credits to the codingame community for this puzzle! Puzzle link

Answer 1

Python 3, 230 bytes

-1 from 12944qwerty

R=range;S=(1,0,-1,0)
def m(A,r=0):
 for l in R(2,27):
  K={(i,j)for i in R(10)for j in R(10)if A[i][j]<l};B={s for s in K if set(s)&{0,9}}
  for _ in R(64):B|=K&{(i+S[k],j+S[k-1])for(i,j)in B for k in R(4)}
  r+=len(K-B)
 return r

Try it online! Input is a list of lists of numbers from 1 to 26 inclusive.

For each possible water level from B (2) to Z (26) this function first fills the pool to that height, then drains off any water touching the edge. K is the set of tentatively filled cells and B that of "burned" cells (since it implements a flood fill).

Answer 2

Python3, 259 bytes

import numpy as np
r=range
l=np.array([[ord(j)-65for j in input()]for i in r(10)])
p=l.copy()
p[1:-1,1:-1]=25
for _ in r(11):
 for i in r(1,9):
  for j in r(1,9):p[i][j]=max(min([p[i+a][j+b]for a,b in[(-1,0),(0,1),(0,-1),(1,0)]]),l[i][j])
print(sum(sum(p-l)))

Try it online!

Answer 3

JavaScript (Node.js), 144 143 bytes

need extra stack

f=(x,t=[...f+f].map((_,i)=>~i%16&&26),z=0)=>t.some((v,i)=>[1,-1,16,-16].some(d=>v>~~t[i+d],p=(x[i>>4]||0)[i%16]|0,z+=v-p)&v>p&&t[i]--)?f(x,t):z

Try it online!

JavaScript (Node.js), 150 bytes

f=(x,t=[...f+f].map((_,i)=>~i%16&&26),u,z=0,r=t.map((v,i)=>[1,-1,16,-16].some(d=>v>~~t[i+d],p=(x[i>>4]||0)[i%16]|0,z+=v-p)&v>p?u=[v-1]:v))=>u?f(x,r):z

Try it online!

t[16*y+x] stores water level

Answer 4

Charcoal, 108 bytes

⊞υＥ⁺Aθ⁰ＷＳ⊞υＥ⁺Aι⌕ακ≔ＥυＥιφθ≔⟦Ｅ³¦⁰⟧ηＦη«≔⊟ιδ≔⊟ιε≔⌈⟦⊟駧υδε⟧ζ¿‹ζ§§θδ嫧≔§θδεζＦ²Ｆ²⊞ηＥ⟦ζεδ⟧⁺μ∧⁼κ⊖ν⊖⊗λ»»Ｉ⁻ΣＥθΣιΣＥυΣι

Try it online! Link is to verbose version of code. Explanation:

⊞υＥ⁺Aθ⁰ＷＳ⊞υＥ⁺Aι⌕ακ

Read in the pool, but add a border of zero depth.

≔ＥυＥιφθ

Try to fill the pool to a height of 1000.

≔⟦Ｅ³¦⁰⟧ηＦη«

Begin a breadth-first search of the pool starting at the top left corner.

≔⊟ιδ≔⊟ιε

Get the next co-ordinates to check.

≔⌈⟦⊟駧υδε⟧ζ

Get the height of the neighbouring water level that triggered this search, but limit it to the height of the cell.

¿‹ζ§§θδε«

If this is less than the current height of the water, then:

§≔§θδεζ

Update the water height.

Ｆ²Ｆ²

Loop over the neighbouring cells.

⊞ηＥ⟦ζεδ⟧⁺μ∧⁼κ⊖ν⊖⊗λ

Add them to the search list of cells to check.

»»Ｉ⁻ΣＥθΣιΣＥυΣι

Subtract the heights of cells from the heights of the water and output the total.

Answer 5

MATLAB, 267 bytes

function d=p(A)
d=0;I=true(10);I(2:9,2:9)=0;for i=2:26
B=int8(A>=i);while any(~B(~I))
[j,k]=find(B==0,1);f(j,k);end
if any(B(I)==2)break
end
d=d+sum(sum(B==2));end
function f(x,y)
if (x<11&y<11&x>0&y>0)&~B(x,y)
B(x,y)=2;f(x-1,y);f(x+1,y);f(x,y+1);f(x,y-1);end
end
end

tried using the flood-fill algorithm to determine what squares on each layer should be filled. If the flood-fill ever reaches the outer edge, that's where the summation stops. I had a much shorter version, but it failed on test case 3 because the lowest outer wall is technically blocked off entirely, raising the effective maximum water level.

Try it online!

Answer 6

C (gcc), 224 214 bytes

-10 bytes by using ternaries (thanks @ceilingcat) and simplifying parameter declaration

#define F for(m=0,j=10;j--;)for(i=10;i--;)
#define L l[j+1][i+1]
#define C(y,x)m=L>h[j][i]&L>l[y+j][x+i]?--L:m;
f(int**h){int m,j,i,l[12][12]={};F L=26;do F{C(,1)C(1,)C(1,2)C(2,1)}while(m);F m+=L-h[j][i];return m;}

Try it online!

Reduce the water level of each box that has water and its level is above one of its neighbours. Repeat until there are no changes to the water level.