Wypełnij jeziora, 2D

22

Jednowymiarowy wersja tego problemu było dość łatwe, więc oto wersja trudniej 2D.

Otrzymujesz tablicę 2D wysokości ziemi na standardowym wejściu i musisz dowiedzieć się, gdzie utworzą się jeziora, gdy pada deszcz. Mapa wysokości jest po prostu prostokątnym układem cyfr od 0 do 9 włącznie.

8888888888
5664303498
6485322898
5675373666
7875555787

Musisz wypisać tę samą tablicę, zastępując wszystkie lokalizacje, które byłyby pod wodą *.

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

Woda może uciekać po przekątnej, więc w tej konfiguracji nie byłoby jeziora:

888
838
388

najkrótszy kod wygrywa. Twój kod musi obsługiwać rozmiary do 80 szerokości i 24 wysokości.

Trzy kolejne przykłady:

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
Keith Randall
źródło
4
Przydałoby się jeszcze kilka przypadków testowych (szczególnie dane wejściowe, które można by rozważyć w przypadku krawędzi).
Ventero
Czy dozwolone są końcowe białe znaki w liniach wyjściowych?
hallvabo
@hallvabo: nie. Dlaczego miałbyś chcieć
Keith Randall
Keith: Miałem inne rozwiązanie, w którym wypełniałem linie wejściowe do stałej szerokości i zapisywałem niektóre bajty w algorytmie. Jeśli muszę usunąć wypełnienie dla danych wyjściowych, takie podejście zajmuje więcej bajtów niż moje obecnie najlepsze rozwiązanie.
hallvabo

Odpowiedzi:

7

Haskell, 258 znaków

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

Przykładowy przebieg:

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

Przechodzi wszystkie testy jednostkowe. Brak dowolnych ograniczeń wielkości.


  • Edycja (281 → 258): nie testuj stabilności, po prostu iteruj do górnej granicy; przestań przekazywać stały argumentm
MtnViewMark
źródło
5

Python, 483 491 znaków

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

Jestem prawie pewien, że istnieje lepszy (i krótszy) sposób na zrobienie tego

System wyłączony
źródło
Przeważnie działa, ale musiałem wymienić input()z sys.stdin.read()i usunąć krawędzie tylną \nz moich przykładowych wejść.
Keith Randall
@ Keith Randall - sys.stdin.read()czyta z pliku, prawda? Wciąż jestem nowy w Pythonie.
System wyłączony
sys.stdin.read()odczytuje STanDard INput aż do EOF. input()odczytuje i ocenia jeden wiersz standardowego wejścia.
Keith Randall
4

Python, 478 471 znaków

(Bez komentarzy. 452 450 znaków bez importu).

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

Chodzi o to, że tworzę ukierunkowany wykres, w którym każda komórka siatki ma swój własny wierzchołek (plus jeden dodatkowy wierzchołek „drenażowy”). Na wykresie jest krawędź od każdej komórki o wyższej wartości do sąsiednich komórek o niższej wartości, a także krawędź od wszystkich komórek zewnętrznych do wierzchołka „drenażu”. Następnie używam Floyd-Warshall do obliczenia, które wierzchołki są połączone z wierzchołkiem „drenażu”; wszystkie wierzchołki, które nie są połączone, zostaną zalane i będą oznaczone gwiazdką.

Nie mam dużego doświadczenia ze skondensowaniem kodu Pythona, więc prawdopodobnie jest bardziej zwięzły sposób na zaimplementowanie tej metody.

ESultanik
źródło
3

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

Nie podjęto żadnej próby gry w golfa, po prostu uważam ten problem za interesujący. Dane wejściowe to tablica 2D mapy. Rozwiązanie sprawdza każdy kwadrat, aby sprawdzić, czy „odpływa” - kwadrat odpływa, jeśli znajduje się na zewnętrznej krawędzi lub jeśli sąsiaduje z kwadratem o równej lub niższej wysokości, który odpływa. Aby uniknąć powtarzania się w nieskończoność, kod zachowuje „mapę drenażu” (dm), w której przechowuje status drenażu już określonych kwadratów.

Dr. Pain
źródło
Opisana przez ciebie logika nie jest do końca właściwa, ponieważ nie obsługuje poprawnie sprawy z wyspą.
Keith Randall
1

Python, 246 znaków

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

Rozwiązanie działa, wykonując DFS z każdej pozycji, aby ustalić, czy wypełnić.

Jeśli końcowe białe znaki w każdej linii są dozwolone, można je skrócić, stosując w = 80 i wypełniając linie wejściowe białymi znakami do 80 znaków.

hallvabo
źródło