# Fill in the lakes, 2D

The one-dimensional version of this problem was pretty easy, so here's a harder 2D version.

You are given a 2D array of land heights on standard input, and you have to figure out where the lakes will form when it rains. The height map is just a rectangular array of the numbers 0-9, inclusive.

8888888888
5664303498
6485322898
5675373666
7875555787


You must output the same array, replacing all locations that would be underwater with *.

8888888888
566*****98
6*85***898
5675*7*666
7875555787


Water can escape diagonally, so there would be no lake in this configuration:

888
838
388


shortest code wins. Your code must handle sizes up to 80 wide and 24 high.

Three more examples:

77777    77777
75657    7*6*7
75757 => 7*7*7
77677    77677
77477    77477

599999    599999
933339    9****9
936639 => 9*66*9
935539    9*55*9
932109    9****9
999999    999999

88888888    88888888
84482288    8**8**88
84452233 => 8**5**33
84482288    8**8**88
88888888    88888888

• Some more testcases would be nice, if possible (especially input you would consider an edge case). – Ventero May 21 '11 at 0:15
• Is trailing whitespace in the output lines allowed? – hallvabo Apr 4 '12 at 10:29
• @hallvabo: no. Why would you want to? – Keith Randall Apr 4 '12 at 19:36
• Keith: I had another solution where I padded the input lines to a fixed width, and saved some bytes in the algorithm. If I have to remove the padding for the output, this approach takes more bytes than my currently best solution. – hallvabo Apr 4 '12 at 19:53

a§b|a<b='*'|1<3=a
z=[-1..1]
l m=zipWith(§)m$(iterate(b.q)$b(\_ _->'9'))!!(w*h)where
w=length mdivh
h=length$lines m q d i=max$minimum[d!!(i+x+w*y)|x<-z,y<-z]
b f=zipWith(\n->ndivModw¶f n)[0..]m
(j,i)¶g|0<i&&i<w-2&&0<j&&j<h-1=g|1<3=id
main=interact l


Example run:

\$> runhaskell 2638-Lakes2D.hs <<TEST
> 8888888888
> 5664303498
> 6485322898
> 5675373666
> 7875555787
> TEST
8888888888
566*****98
6*85***898
5675*7*666
7875555787


Passes all unit tests. No arbitrary limits on size.

• Edit (281 → 258): don't test for stability, just iterate to the upper bound; stop passing constant argument m

## Python, 483 491 characters

a=dict()
def s(n,x,y,R):
r=range(-1,2)
m=set([(x+i,y+j)for i in r for j in r if(i,j)!=(0,0)and(x+i,y+j)not in R])
z=m-set(a.keys())
if len(z)>0:return 1
else:return sum(s(n,k[0],k[1],R)for k in[d for d in m-z if a[(d[0],d[1])]<=n])
i=[list(x)for x in input().strip().split('\n')]
h=len(i)
w=len(i[0])
e=range(0,w)
j=range(0,h)
for c in[(x,y)for x in e for y in j]:a[c]=int(i[c[1]][c[0]])
for y in j:print(''.join([('*',str(a[(x,y)]))[s(a[(x,y)],x,y,set())>0] for x in e]))


I'm pretty sure there's a better (and shorter) way of doing this

• Mostly works, but I did have to replace input() with sys.stdin.read() and remove the trailing \n from my sample inputs. – Keith Randall May 25 '11 at 19:51
• @Keith Randall - sys.stdin.read() reads from a file right? I'm still rather new at Python. – System Down May 25 '11 at 20:02
• sys.stdin.read() reads STanDard INput until EOF. input() reads and evaluates one line of standard input. – Keith Randall May 25 '11 at 23:05

## Python, 478 471 characters

(Not including comments. 452 450 characters not including the imports.)

import sys,itertools
h=len(i)
w=len(i[0])
n=h*w
b=n+1
e=range(h)
d=range(w)
# j is, at first, the adjancency matrix of the graph.
# The last vertex in j is the "drain" vertex.
j=[[[b,1][(t-r)**2+(v-c)**2<=1 and i[r][c]>=i[t][v]] for t in e for v in d]+[[b,1][max([r==0,r>h-2,c==0,c>w-2])]]for r in e for c in d]+[[0]*b]
r=range(b)
for k,l,m in itertools.product(r,repeat=3):
# This is the Floyd-Warshall algorithm
if j[l][k]+j[k][m]<j[l][m]:
j[l][m]=j[l][k]+j[k][m]
# j is now the distance matrix for the graph.
for k in r:
if j[k][-1]>n:
# This means that vertex k is not connected to the "drain" vertex, and is therefore flooded.
i[k/w][k-w*(k/w)]='*'
for r in e:print(''.join(i[r]))


The idea here is that I construct a directed graph where each grid cell has its own vertex (plus one additional "drain" vertex). There is an edge in the graph from each higher valued cell to its neighboring lower valued cells, plus there is an edge from all exterior cells to the "drain" vertex. I then use Floyd-Warshall to calculate which vertices are connected to the "drain" vertex; any vertices that are not connected will be flooded and are drawn with an asterisk.

I don't have much experience with condensing Python code, so there's probably a more succinct way I could have implemented this method.

## Common Lisp, 833

(defun drains (terr dm a b)
(cond
((= (aref dm a b) 1) t)
((= (aref dm a b) -1) nil)
((or (= a 0) (= b 0)
(= a (1- (array-dimension terr 0)))
(= b (1- (array-dimension terr 1)))) t)
(t (loop for x from -1 to 1
do (loop for y from 0 to 1
do (if (and (or (> x 0) (> y 0))
(drains terr dm (+ a x) (+ b y))
(<= (aref terr (+ a x) (+ b y))
(aref terr a b)))
(progn
(setf (aref dm a b) 1)
(return-from drains t)))))
(setf (aref dm a b) -1)
nil)))

(defun doit (terr)
(let ((dm (make-array (array-dimensions terr))))
(loop for x from 0 to (- (array-dimension terr 0) 1)
do (loop for y from 0 to (- (array-dimension terr 1) 1)
do (format t "~a"
(if (drains terr dm x y)
(aref terr x y)
"*"))
finally (format t "~%")))))


No attempt has been made to golf this, I just found the problem interesting. Input is the 2D array of the map. The solution checks each square to see if it "drains" -- a square drains if it is on the outer edge or if it is adjacent to an equal or lower height square that drains. To keep from recursing endlessly, the code keeps a "drain map" (dm) where it stores the drainage status of squares that have already been determined.

• Your described logic isn't quite right, as it doesn't handle the case with the island correctly. – Keith Randall May 25 '11 at 19:39

## Python, 246 chars

import os
w=a.index('\n')+1
a+=' '*w
def f(p,t):
if e<a[p]or p in t:return
t[p]=1
return'*'>a[p]or any(f(p+d,t)for d in(~w,-w,-w+1,-1,1,w-1,w,w+1))
z=0
for e in a:
if(' '<e)*~-f(z,{}):a[z]='*'
z+=1
print''.join(a[:~w])


The solution works by doing a DFS from each position to determine whether or not to fill.

If trailing whitespace on each line is allowed, it may be shortened by using w=80 and padding the input lines with whitespace to 80 chars.