2
\$\begingroup\$

The one dimensional twitter waterflow problem is this:

You are given an array that represents a hill in the sense that the ith entry is the height of the ith location of the hill. When it rains, water logs in the hills, and you need to figure out how much water would log.

For example, after raining, the array 2 5 3 4 3 2 5 5 3 4 2 2 2 looks like this,

and 9 units of water have accumulated.


The challenge is to solve the 2D version of this. To clarify, you will be given a 2D matrix of land heights, and you will have to output the total amount of rainwater it can collect. Water cannot flow out through diagonals, but only the four cardinal directions.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ duplicate? \$\endgroup\$
    – ngn
    Commented Jul 1, 2018 at 6:15
  • 3
    \$\begingroup\$ @AgnishomChattopadhyay Fair enough. I think you should mention big-O of what we should optimise for - the size of the matrix, or the volume of the water held, or the max height? \$\endgroup\$
    – ngn
    Commented Jul 1, 2018 at 7:12
  • 2
    \$\begingroup\$ @AgnishomChattopadhyay also, it would be nice to have some tests \$\endgroup\$
    – ngn
    Commented Jul 1, 2018 at 7:21
  • 4
    \$\begingroup\$ I think you should make it more obvious that the actual challenge is the second part of the post and give at least one 2D example. \$\endgroup\$
    – Arnauld
    Commented Jul 1, 2018 at 7:47
  • 1
    \$\begingroup\$ Also: (1) if there is a winning criteria tag, don't need [code-challenge]. (2) best case, worst case or average case? \$\endgroup\$
    – DELETE_ME
    Commented Jul 1, 2018 at 9:33

1 Answer 1

0
\$\begingroup\$

Python 3, O(h × w × d) 296 bytes, O(h × w × d')

def f(a):
 w=0;b=[len(a[0])*[0]];a=b+a+b;a=[[0]+x+[0]for x in a];b=sorted(set(sum(a,[])))
 for[i,j]in zip(b,b[1:]+[1+max(b)]):
  c=[[0,0]]
  while c:
   [x,y]=c.pop()
   if x<len(a)and x>=0and y<len(a[0])and y>=0and a[x][y]<=i:w+=i-a[x][y];a[x][y]=j;c+=[[x+1,y],[x,y+1],[x-1,y],[x,y-1]]
 return w

Try it online! Where d' represents the number of distinct values in the input. Edit: Saved 3 bytes thanks to @Mr.Xcoder.

\$\endgroup\$
12
  • \$\begingroup\$ (what is h, w and d?) \$\endgroup\$
    – DELETE_ME
    Commented Jul 1, 2018 at 10:01
  • \$\begingroup\$ @user202729 d is the highest land height in the w × h grid, but I like to think of it as the depth. \$\endgroup\$
    – Neil
    Commented Jul 1, 2018 at 10:16
  • \$\begingroup\$ b=[len(a[0])*[0]] should work for 276. \$\endgroup\$
    – Mr. Xcoder
    Commented Jul 1, 2018 at 12:31
  • \$\begingroup\$ Thanks for the answer. I'd like to think that there is some algorithm that is independent of d. Otherwise, scaling all the numbers by some arbitrary amount would randomly require more time. \$\endgroup\$ Commented Jul 1, 2018 at 15:28
  • \$\begingroup\$ @AgnishomChattopadhyay Better now? \$\endgroup\$
    – Neil
    Commented Jul 1, 2018 at 16:03

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