Rellene los lagos, 2D

La versión unidimensional de este problema fue bastante fácil, así que aquí hay una versión 2D más difícil.

Se le proporciona una matriz 2D de alturas de tierra en la entrada estándar, y tiene que averiguar dónde se formarán los lagos cuando llueva. El mapa de altura es solo una matriz rectangular de los números 0-9, inclusive.

8888888888
5664303498
6485322898
5675373666
7875555787

Debe generar la misma matriz, reemplazando todas las ubicaciones que estarían bajo el agua *.

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

El agua puede escapar en diagonal, por lo que no habría lago en esta configuración:

888
838
388

el código más corto gana. Su código debe manejar tamaños de hasta 80 de ancho y 24 de alto.

Tres ejemplos más:

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

Haskell, 258 caracteres

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

Ejemplo de ejecución:

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

Pasa todas las pruebas unitarias. No hay límites arbitrarios en el tamaño.

• Editar (281 → 258): no pruebe la estabilidad, solo repita el límite superior; deja de pasar argumentos constantesm

Python, 483 491 caracteres

a=dict()
def s(n,x,y,R):
 R.add((x,y))
 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]))

Estoy bastante seguro de que hay una manera mejor (y más corta) de hacer esto

Python, 478 471 caracteres

(Sin incluir comentarios. 452 450 caracteres sin incluir las importaciones).

import sys,itertools
i=[list(x)for x in sys.stdin.read().strip().split('\n')]
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]))

La idea aquí es que construya un gráfico dirigido donde cada celda de la cuadrícula tenga su propio vértice (más un vértice de "drenaje" adicional). Hay un borde en el gráfico desde cada celda de mayor valor a sus celdas vecinas de menor valor, además hay un borde desde todas las celdas exteriores hasta el vértice de "drenaje". Luego uso Floyd-Warshall para calcular qué vértices están conectados al vértice de "drenaje"; cualquier vértice que no esté conectado se inundará y se dibujará con un asterisco.

No tengo mucha experiencia con la condensación de código Python, por lo que probablemente haya una forma más sucinta de haber implementado este método.

Lisp común, 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 se ha hecho ningún intento de jugar al golf, el problema me pareció interesante. La entrada es la matriz 2D del mapa. La solución verifica cada cuadrado para ver si "drena": un cuadrado drena si está en el borde exterior o si está adyacente a un cuadrado de altura igual o menor que drena. Para evitar que se repita sin cesar, el código mantiene un "mapa de drenaje" (dm) donde almacena el estado de drenaje de los cuadrados que ya se han determinado.

Python, 246 caracteres

import os
a=list(os.read(0,2e3))
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])

La solución funciona haciendo un DFS desde cada posición para determinar si se debe llenar o no.

Si se permite el espacio en blanco al final de cada línea, se puede acortar usando w = 80 y rellenando las líneas de entrada con espacios en blanco a 80 caracteres.