Retaining Water

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

• Can the pool contain multiple separated bodies of water?
Feb 7, 2022 at 7:26
• yes it can but no overflowing of water is allowed past the outer layer Feb 7, 2022 at 7:27
• The 4th case array form is still missing
– l4m2
Feb 8, 2022 at 13:39
• added thx l4m2 didnt see that Feb 9, 2022 at 0:11
• @DialFrost The fourth test case array form doesn't look exactly right... are you sure you meant to put a list of one element lists? Feb 9, 2022 at 0:20

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

• -1 if you move r=0 to argument part of function Feb 8, 2022 at 14:03

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!

• This produces the wrong answer when the path for the water to flow out is long.
– m90
Feb 7, 2022 at 8:57
• this test case is not possible, the outer wall has to have the highest wall Feb 8, 2022 at 6:01
• @DialFrost But it is... The outer wall is B = 2, which is higher than A = 1. Also, your rules even state: "You may assume that the outer row of alphabets do not always have the highest height, and can all have different heights" Feb 8, 2022 at 6:42
• Sry i need to change that Feb 8, 2022 at 12:53

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

Charcoal, 108 bytes

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


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

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


≔ＥυＥιφθ


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.

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!

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.