Remplissez les lacs, 2D

La version unidimensionnelle de ce problème était assez facile, alors voici une version 2D plus difficile.

Vous disposez d'un tableau 2D de hauteurs de terrain sur une entrée standard, et vous devez déterminer où les lacs se formeront quand il pleuvra. La carte des hauteurs n'est qu'un tableau rectangulaire des nombres 0-9 inclus.

8888888888
5664303498
6485322898
5675373666
7875555787

Vous devez sortir la même baie, en remplaçant tous les emplacements qui seraient sous l'eau avec *.

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

L'eau peut s'échapper en diagonale, il n'y aurait donc pas de lac dans cette configuration:

888
838
388

le code le plus court gagne. Votre code doit gérer des tailles allant jusqu'à 80 de large et 24 de haut.

Trois autres exemples:

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 caractères

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

Exemple d'exécution:

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

Réussit tous les tests unitaires. Pas de limites arbitraires sur la taille.

• Edit (281 → 258): ne testez pas la stabilité, parcourez simplement la limite supérieure; arrêter de passer l'argument constantm

Python, 483 491 caractères

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

Je suis presque sûr qu'il y a une meilleure (et plus courte) manière de procéder

Python, 478 471 caractères

(Non compris les commentaires. 452 450 caractères non compris les importations.)

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

L'idée ici est que je construise un graphe orienté où chaque cellule de la grille a son propre sommet (plus un sommet "drain" supplémentaire). Il y a un bord dans le graphique de chaque cellule de valeur supérieure à ses cellules voisines de valeur inférieure, plus il y a un bord de toutes les cellules extérieures au sommet "drain". J'utilise ensuite Floyd-Warshall pour calculer quels sommets sont connectés au sommet "drain"; tous les sommets qui ne sont pas connectés seront inondés et seront dessinés avec un astérisque.

Je n'ai pas beaucoup d'expérience avec la condensation de code Python, donc il y a probablement une manière plus succincte que j'aurais pu implémenter cette méthode.

Lisp commun, 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 "~%")))))

Aucune tentative n'a été faite pour jouer au golf, je viens de trouver le problème intéressant. L'entrée est le tableau 2D de la carte. La solution vérifie chaque carré pour voir s'il "draine" - un carré draine s'il est sur le bord extérieur ou s'il est adjacent à un carré de hauteur égale ou inférieure qui draine. Pour éviter de se reproduire indéfiniment, le code conserve une "carte de drainage" (dm) où il stocke l'état de drainage des carrés qui ont déjà été déterminés.

Python, 246 caractères

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 solution fonctionne en faisant un DFS à partir de chaque position pour déterminer s'il faut ou non remplir.

Si un espace de fin sur chaque ligne est autorisé, il peut être raccourci en utilisant w = 80 et en remplissant les lignes d'entrée avec un espace à 80 caractères.