Fülle die Seen aus, 2D

Die eindimensionale Version dieses Problems war ziemlich einfach. Hier ist eine schwierigere 2D-Version.

Sie erhalten eine 2D-Anordnung von Landhöhen bei Standardeingabe und müssen herausfinden, wo sich die Seen bilden, wenn es regnet. Die Höhenkarte ist nur eine rechteckige Anordnung der Zahlen 0-9 einschließlich.

8888888888
5664303498
6485322898
5675373666
7875555787

Sie müssen dasselbe Array ausgeben und alle Positionen ersetzen, bei denen sich Unterwasser befindet *.

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

Wasser kann diagonal entweichen, so dass in dieser Konfiguration kein See vorhanden ist:

888
838
388

kürzester Code gewinnt. Ihr Code muss Größen bis zu 80 breit und 24 hoch verarbeiten können.

Drei weitere Beispiele:

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 Zeichen

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

Beispiellauf:

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

Besteht alle Komponententests. Keine willkürlichen Größenbeschränkungen.

• Bearbeiten (281 → 258): Testen Sie nicht die Stabilität, sondern iterieren Sie bis zur oberen Grenze. Übergeben Sie keine konstanten Argumente mehrm

Python, 483 491 Zeichen

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

Ich bin mir ziemlich sicher, dass es einen besseren (und kürzeren) Weg gibt, dies zu tun

Python, 478 471 Zeichen

(Ohne Kommentare. 452 450 Zeichen ohne Importe.)

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

Die Idee hier ist, dass ich einen gerichteten Graphen konstruiere, bei dem jede Gitterzelle einen eigenen Scheitelpunkt hat (plus einen zusätzlichen "Drain" -Scheitelpunkt). Das Diagramm enthält eine Kante von jeder höherwertigen Zelle zu den benachbarten niedrigerwertigen Zellen sowie eine Kante von allen äußeren Zellen zum "Drain" -Vertex. Ich benutze dann Floyd-Warshall, um zu berechnen, welche Vertices mit dem "Drain" -Vertex verbunden sind. Alle nicht verbundenen Scheitelpunkte werden überflutet und mit einem Sternchen gekennzeichnet.

Ich habe nicht viel Erfahrung mit der Verdichtung von Python-Code, daher gibt es wahrscheinlich eine prägnantere Möglichkeit, wie ich diese Methode hätte implementieren können.

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

Es wurde noch kein Versuch unternommen, Golf zu spielen. Ich fand das Problem nur interessant. Eingabe ist das 2D-Array der Karte. Die Lösung überprüft jedes Quadrat, um festzustellen, ob es "entwässert" - ein Quadrat entwässert, wenn es sich an der Außenkante befindet oder an ein Quadrat gleicher oder niedrigerer Höhe angrenzt, das entwässert. Um eine endlose Wiederholung zu vermeiden, speichert der Code eine "Drain-Map" (dm), in der der Drain-Status bereits ermittelter Quadrate gespeichert wird.

Python, 246 Zeichen

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

Die Lösung besteht darin, von jeder Position aus eine DFS durchzuführen, um zu bestimmen, ob gefüllt werden soll oder nicht.

Wenn nachfolgende Leerzeichen in jeder Zeile zulässig sind, können Sie diese mit w = 80 kürzen und die Eingabezeilen mit Leerzeichen auf 80 Zeichen auffüllen.