Wprowadzenie

Przez wiele stuleci istniała pewna rzeka, która nigdy nie została zmapowana. Gildia Kartografów chce stworzyć mapę rzeki, jednak nigdy im się nie udało - z jakiegoś powodu wszyscy kartografowie, którzy wysłali ją na mapę rzeki, zostali zjedzeni przez dzikie zwierzęta w okolicy. Wymagane jest inne podejście.

Opis wejścia

Obszar jest prostokątną siatką komórek o długości mi szerokości n. Komórka w lewym dolnym rogu byłaby 0,0, a komórka w prawym górnym rogu byłaby m-1,n-1. mi nsą podawane na wejściu jako krotka m,n.

Dzięki zastosowaniu technik sondowania geograficznego na duże odległości zidentyfikowano położenie wysp wokół rzeki. Rozmiar wysp (tj. Ile komórek zajmuje wyspa) również został zidentyfikowany, ale kształt nie. Dostarczamy te informacje w krotce, s,x,ygdzie sjest wielkość wyspy, xi ysą pozycjami x i y jednej konkretnej komórki tej wyspy. Każda krotka na wejściu jest oddzielona spacją, więc oto przykładowe wejście:

7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6

Aby lepiej zilustrować, oto dane wejściowe na wykresie:

 y 6|8 1 3
   5|
   4|  2
   3|    2
   2|
   1|   2  2
   0|2  
     =======
     0123456
     x

Opis wyjścia

Wydrukuj mapę, używając znaków ASCII do reprezentacji części obszaru. Każda komórka będzie albo #(lądem), albo .(wodą). Mapa powinna przestrzegać następujących zasad:

1. Definicja. Wyspa to ortogonalnie przylegająca grupa komórek lądowych, która jest całkowicie ograniczona przez komórki rzeczne i / lub granicę obszaru.
2. Definicja. Rzeka to ortogonalnie przylegająca grupa komórek wodnych, która jest całkowicie ograniczona przez komórki lądowe i / lub granicę obszaru i nie zawiera „jezior” (2 x 2 obszary komórek wodnych).
3. Rządzić . Mapa powinna zawierać dokładnie jedną rzekę.
4. Rządzić . Każda ponumerowana komórka na wejściu powinna być częścią wyspy zawierającej dokładnie skomórki.
5. Rządzić . Każda wyspa na mapie musi zawierać dokładnie jedną z ponumerowanych komórek na wejściu.
6. Rządzić . Istnieje jedna unikalna mapa dla każdego wejścia.

Oto wynik przykładowego wejścia:

#.#.##.
#....#.
#.##...
##..##.
###....
...##.#
##....#

Oto kolejne wejście i wyjście.

Wejście:

5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4

Wynik:

#.#.#
#.#.#
.....
###.#
.....

C + PicoSAT , 2345 995 952 bajtów

#include<picosat.h>
#define f(i,a)for(i=a;i;i--)
#define g(a)picosat_add(E,a)
#define b calloc(z+1,sizeof z)
#define e(a,q)if(a)A[q]^A[p]?l[q]++||(j[++k]=q):s[q]||(i[q]=p,u(q));
z,F,v,k,n,h,p,q,r,C,*x,*A,*i,*l,*s,*j,*m;u(p){s[m[++n]=p]=1;e(p%F-1,p-1)e(p%F,p+1)e(p>F,p-F)e(p<=F*v-F,p+F)}t(){f(q,k)l[j[q]]=0;f(q,n)s[m[q]]=0;k=n=0;i[p]=-1;u(p);}main(){void*E=picosat_init();if(scanf("%d,%d",&F,&v)-2)abort();z=F*v;for(x=b;scanf("%d,%d,%d",&r,&p,&q)==3;g(p),g(0))x[p=F-p+q*F]=r;f(p,F*v-F)if(p%F)g(p),g(p+1),g(p+F),g(p+F+1),g(0);for(A=b,i=b,l=b,s=b,j=b,m=b;!C;){picosat_sat(E,C=h=-1);f(p,F*v)A[p]=picosat_deref(E,p)>0,i[p]=0;f(p,F*v)if(x[p])if(i[q=p]){for(g(-q);i[q]+1;)q=i[q],g(-q);g(C=0);}else if(t(),r=n-x[p]){f(q,r<0?k:n)g(r<0?j[q]:-m[q]);g(C=0);}f(p,F*v)if(!i[p])if(t(),A[p]){g(-++z);f(q,k)g(j[q]);g(C=0);f(q,n)g(-m[q]),g(z),g(0);}else{C&=h++;f(q,k)g(-j[q]);g(++z);g(++z);g(0);f(q,F*v)g(s[q]-z),g(q),g(0);}}f(p,F*v)putchar(A[p]?35:46),p%F-1||puts("");}

Wypróbuj online!

(Ostrzeżenie: ten link TIO to 30-kilobajtowy adres URL, który zawiera zminimalizowaną kopię PicoSAT 965, więc może nie być w stanie załadować go w niektórych przeglądarkach, ale ładuje się przynajmniej w przeglądarce Firefox i Chrome.

Jak to działa

Inicjalizujemy solver SAT zmienną dla każdej komórki (lądowej lub wodnej) i tylko następujące ograniczenia:

1. Każda ponumerowana komórka to ziemia.
2. Każdy prostokąt 2 × 2 ma co najmniej jeden ląd.

Reszta ograniczeń jest trudna do zakodowania bezpośrednio w SAT, więc zamiast tego uruchamiamy solver, aby uzyskać model, uruchamiamy sekwencję przeszukiwania w pierwszej kolejności, aby znaleźć połączone regiony tego modelu, i dodajemy dodatkowe ograniczenia w następujący sposób:

3. Dla każdej numerowanej komórki w obszarze lądowym, który jest zbyt duży, dodaj ograniczenie, że powinna istnieć co najmniej jedna komórka wodna wśród obecnych komórek lądowych w tym regionie.
4. Dla każdej ponumerowanej komórki w obszarze lądowym, który jest zbyt mały, dodaj ograniczenie, że powinna istnieć co najmniej jedna komórka lądowa wśród bieżących komórek wodnych graniczących z tym regionem.
5. Dla każdej ponumerowanej komórki w tym samym regionie lądowym co inna ponumerowana komórka dodaj ograniczenie, że powinna istnieć co najmniej jedna komórka wodna wzdłuż ścieżki bieżących komórek lądowych między nimi (znaleziona po przejściu wskaźników macierzystych pozostałych z przeszukiwania pierwszej głębokości ).
6. Dla każdego regionu lądowego, w tym bez ponumerowanych komórek, dodaj ograniczenia, które albo
   • wszystkie te obecne komórki lądowe powinny być wodą, lub
   • przynajmniej jedna z obecnych komórek wodnych graniczących z tym regionem powinna być lądem.
7. Dla każdego regionu wodnego dodaj ograniczenia, które albo
   • wszystkie obecne komórki wodne powinny znajdować się na lądzie, lub
   • każda komórka inna niż obecne komórki wodne powinna być lądowa, lub
   • przynajmniej jedna z obecnych komórek lądowych graniczących z tym regionem powinna być wodą.

Korzystając z interfejsu przyrostowego do biblioteki PicoSAT, możemy natychmiast ponownie uruchomić solver, w tym dodane ograniczenia, zachowując wszystkie poprzednie wnioski dokonane przez solver. PicoSAT daje nam nowy model i kontynuujemy iterację powyższych kroków, aż rozwiązanie będzie prawidłowe.

Jest to niezwykle skuteczne; rozwiązuje 15 × 15 i 20 × 20 instancji w ułamku sekundy.

(Dzięki Lopsy za zasugerowanie pomysłu interaktywnego ograniczania połączonych regionów w przyrostowym rozwiązaniu SAT, jakiś czas temu.)

Niektóre większe przypadki testowe z puzzle-nurikabe.com

Losowa strona twardych zagadek 15 × 15 ( 5057541 , 5122197 , 5383030 , 6275294 , 6646970 , 6944232 ):

15,15 1,5,1 3,9,1 5,4,2 1,6,2 2,11,2 2,2,3 3,9,3 2,4,4 1,10,4 5,12,4 3,1,5 1,3,5 3,8,5 1,13,5 5,5,6 1,12,6 1,2,8 2,9,8 1,1,9 2,6,9 6,11,9 3,13,9 5,2,10 2,4,10 4,10,10 1,5,11 2,12,11 2,3,12 2,8,12 5,10,12 1,5,13 1,9,13 1,6,14 1,8,14
15,15 4,2,0 2,5,0 1,3,1 2,14,2 1,3,3 2,11,3 1,13,3 1,5,4 11,7,4 1,9,4 1,4,5 1,8,5 2,10,5 12,14,5 3,5,6 1,4,7 2,10,7 3,9,8 4,0,9 1,4,9 1,6,9 3,10,9 1,5,10 1,7,10 8,9,10 1,1,11 10,3,11 2,11,11 6,0,12 1,11,13 2,9,14 1,12,14
15,15 2,2,0 8,10,0 2,3,1 2,14,2 2,3,3 3,5,3 3,9,3 2,11,3 5,13,3 6,0,4 3,7,4 3,3,5 2,11,5 2,6,6 1,8,6 1,4,7 2,10,7 1,6,8 2,8,8 5,3,9 2,11,9 2,7,10 7,14,10 2,1,11 4,3,11 2,5,11 1,9,11 2,11,11 2,0,12 4,6,13 1,11,13 3,4,14 1,12,14
15,15 2,0,0 2,4,0 3,6,1 2,10,1 1,13,1 2,5,2 2,12,2 3,0,3 2,2,3 4,7,3 2,9,3 1,14,3 1,4,4 1,8,4 2,12,5 4,2,6 3,4,6 1,14,6 7,7,7 1,10,8 2,12,8 3,2,9 2,14,9 2,0,10 2,6,10 1,10,10 2,5,11 4,7,11 2,12,11 1,14,11 3,2,12 3,9,12 1,1,13 2,4,13 3,8,13 2,10,14 5,14,14
15,15 1,3,0 1,14,0 3,7,1 3,10,1 2,13,1 3,1,2 4,5,2 2,12,3 3,3,4 1,8,4 1,1,5 3,5,5 1,9,5 5,13,5 3,3,6 1,8,6 2,2,7 2,12,7 1,6,8 1,8,8 2,11,8 2,1,9 4,5,9 2,9,9 2,13,9 2,6,10 4,11,10 1,2,11 3,9,12 2,13,12 3,1,13 2,4,13 3,7,13 1,0,14
15,15 2,8,0 2,4,1 2,7,1 1,10,1 6,4,3 1,1,4 12,5,4 3,11,4 5,13,4 3,10,5 3,0,6 1,6,6 2,8,6 4,13,7 2,3,8 1,6,8 3,8,8 2,14,8 2,4,9 5,1,10 4,3,10 1,9,10 6,13,10 3,8,11 1,10,11 3,4,13 2,7,13 3,10,13 1,6,14 1,14,14

Losowa strona 20 × 20 normalnych zagadek ( 536628 , 3757659 ):

20,20 1,0,0 3,2,0 2,6,0 1,13,0 3,9,1 3,15,1 2,7,2 3,13,2 3,0,3 2,3,3 3,18,3 3,5,4 2,9,4 2,11,4 2,16,4 1,0,5 2,7,5 1,10,5 1,19,5 3,2,6 1,11,6 2,17,6 2,0,7 3,4,7 5,6,7 2,9,7 4,13,7 3,15,7 1,3,8 1,10,8 1,14,9 2,18,9 3,1,10 2,4,10 1,8,10 1,10,10 3,12,10 3,16,10 1,9,11 1,17,11 2,19,11 2,0,12 2,2,12 1,4,12 4,6,12 2,13,12 2,15,12 1,14,13 2,17,13 1,3,14 2,5,14 4,7,14 2,15,14 3,0,15 1,2,15 2,13,15 3,18,15 3,7,16 7,10,16 1,17,16 2,0,17 2,3,17 2,5,17 3,11,17 3,15,17 1,0,19 1,2,19 1,4,19 2,6,19 5,8,19 1,11,19 1,13,19 3,15,19 2,18,19
20,20 1,0,0 1,4,0 5,8,0 1,17,0 1,19,0 2,17,2 3,6,3 2,10,3 2,12,3 4,14,3 6,0,4 3,4,4 4,7,4 1,11,4 1,18,4 1,6,5 3,12,5 4,15,5 4,4,6 2,16,6 2,19,6 6,0,7 3,10,7 2,12,8 2,17,8 3,3,9 2,5,9 4,8,9 2,10,9 3,0,10 1,2,10 5,14,10 2,16,10 2,19,10 7,7,11 3,12,12 2,17,12 2,2,13 4,4,13 3,6,13 4,14,13 3,0,14 1,3,14 1,5,14 3,16,14 1,2,15 1,9,15 2,11,15 5,13,15 3,19,15 1,4,16 3,6,16 1,3,17 1,12,17 1,14,17 1,16,17 6,0,19 2,2,19 3,5,19 2,7,19 5,9,19 1,11,19 2,13,19 1,15,19 4,17,19

GLPK , (niekonkurujące) 2197 bajtów

Jest to wpis niekonkurujący, as

• Nie podążam za formatem danych wejściowych (ponieważ GLPK może odczytywać tylko dane wejściowe z plików) i
• GLPK wydaje się być niedostępny w RIO.

Uratuję tutaj jeszcze nie ulepszoną, ale funkcjonalną wersję. W zależności od opinii, mogę spróbować ją skrócić + dodać wyjaśnienie, jeśli jest zainteresowanie. Jak dotąd nazwy ograniczeń służą jako dokumenty w miejscu.

Główną ideą jest zakodowanie ograniczenia „ciągłych wysp” poprzez wprowadzenie zachowanej zmiennej przepływu, która ma wstępnie określone źródło w miejscu podpowiedzi. Zmienna decyzyjna is_islandodgrywa następnie rolę zlewozmywaków umieszczalnych. Dzięki zminimalizowaniu całkowitej sumy tego przepływu wyspy są zmuszone pozostać połączone w optymalny sposób. Inne ograniczenia raczej bezpośrednio wdrażają różne reguły. Zastanawia mnie to, że wciąż potrzebuję island_fields_have_at_least_one_neighbor.

Wydajność tego preparatu nie jest jednak świetna. Przez bezpośrednie zjedzenie całej złożoności z dużą ilością ograniczeń, solver zajmuje prawie 15 sekund dla przykładu 15 x 15.

Kod (wciąż nie golfowy)

# SETS
param M > 0, integer; # length
param N > 0, integer; # width
param P > 0, integer; # no. of islands

set X := 0..N-1;  # set of x coords
set Y := 0..M-1;  # set of y coords
set Z := 0..P-1;  # set of islands

set V := X cross Y;
set E within V cross V := setof{
  (sx, sy) in V, (tx, ty) in V :

  ((abs(sx - tx) = 1) and (sy = ty)) or 
  ((sx = tx) and (abs(sy - ty) = 1))
} 
  (sx, sy, tx, ty);


# PARAMETERS
param islands{x in X, y in Y, z in Z}, integer, default 0;
param island_area{z in Z} := sum{x in X, y in Y} islands[x, y, z];

# VARIABLES
var is_river{x in X, y in Y}, binary;
var is_island{x in X, y in Y, z in Z}, binary;
var flow{(sx, sy, tx, ty) in E, z in Z} >= 0;

# OBJECTIVE
minimize obj: sum{(sx, sy, tx, ty) in E, z in Z} flow[sx, sy, tx, ty, z];

# CONSTRAINTS
s.t. islands_are_connected{(x, y) in V, z in Z}:

    islands[x, y, z] 
  - is_island[x, y, z]
  + sum{(sx, sy, tx, ty) in E: x = tx and y = ty} flow[sx, sy, x, y, z]
  - sum{(sx, sy, tx, ty) in E: x = sx and y = sy} flow[x, y, tx, ty, z]
  = 0;


s.t. island_contains_hint_location{(x, y) in V, z in Z}:

    is_island[x, y, z] >= if islands[x, y, z] > 0 then 1 else 0;


s.t. each_square_is_river_or_island{(x, y) in V}:

    is_river[x, y] + sum{z in Z} is_island[x, y, z] = 1;


s.t. islands_match_hint_area{z in Z}:

    sum{(x, y) in V} is_island[x, y, z] = island_area[z];


s.t. river_has_no_lakes{(x,y) in V: x > 0 and y > 0}:

  3 >= is_river[x, y] + is_river[x - 1, y - 1]
     + is_river[x - 1, y] + is_river[x, y - 1];


s.t. river_squares_have_at_least_one_neighbor{(x, y) in V}:

    sum{(sx, sy, tx, ty) in E: x = tx and y = ty} is_river[sx, sy] 
 >= is_river[x, y];


s.t. island_fields_have_at_least_one_neighbor{(x, y) in V, z in Z: island_area[z] > 1}:

    sum{(sx, sy, tx, ty) in E: x = tx and y = ty} is_island[sx, sy, z]
 >= is_island[x, y, z];


s.t. islands_are_separated_by_water{(x, y) in V, z in Z}:

    sum{(sx, sy, tx, ty) in E, oz in Z: x = sx and y = sy and z != oz} is_island[tx, ty, oz]
 <= 4 * P * (1 - is_island[x, y, z]);

solve;

for{y in M-1..0 by -1}
{
    for {x in X} 
    {
        printf "%s", if is_river[x, y] = 1 then "." else "#";
    }
    printf "\n";
}

Dane problemu

5 x 5

data;
param M := 5;
param N := 5;
param P := 5;
param islands :=
# x,y,z,area
  0,1,0,3
  4,1,1,1
  0,4,2,2
  2,4,3,2
  4,4,4,2;
end;

7 x 7

data;
param M := 7;
param N := 7;
param P := 8;
param islands :=
# x,y,z,area
  0,0,0,2 
  3,1,1,2 
  6,1,2,2 
  4,3,3,2 
  2,4,4,2 
  0,6,5,8 
  2,6,6,1 
  4,6,7,3;
end;

15 x 15

data;
param M := 15;
param N := 15;
param P := 34;
param islands :=
# x,y,   z,area
5,  1,   0, 1
9,  1,   1, 3
4,  2,   2, 5
6,  2,   3, 1
11, 2,   4, 2
2,  3,   5, 2
9,  3,   6, 3
4,  4,   7, 2
10, 4,   8, 1
12, 4,   9, 5
1,  5,  10, 3
3,  5,  11, 1
8,  5,  12, 3
13, 5,  13, 1
5,  6,  14, 5
12, 6,  15, 1
2,  8,  16, 1
9,  8,  17, 2
1,  9,  18, 1
6,  9,  19, 2
11, 9,  20, 6
13, 9,  21, 3
2,  10, 22, 5
4,  10, 23, 2
10, 10, 24, 4
5,  11, 25, 1
12, 11, 26, 2
3,  12, 27, 2
8,  12, 28, 2
10, 12, 29, 5
5,  13, 30, 1
9,  13, 31, 1
6,  14, 32, 1
8,  14  33, 1;
end;

Stosowanie

Zostały glpsolzainstalowane, modelu jako jeden plik (np river.mod), dane wejściowe w oddzielnym pliku (ów) (na przykład 7x7.mod). Następnie:

glpsol -m river.mod -d 7x7.mod

To plus odrobina cierpliwości wydrukuje rozwiązanie w określonym formacie wyjściowym (wraz z „niektórymi” wynikami diagnostycznymi).

Python 3 , 1295 bajtów

Jest to rozwiązanie tylko do Pythona. Nie używa bibliotek i ładuje płytę poprzez standardowe wejście. Dalsze wyjaśnienia w przyszłości. To moja pierwsza próba tak dużego golfa. Na dole znajduje się link do skomentowanego i nie golfowego kodu.

L,S,O,R,F=len,set,None,range,frozenset
U,N,J,D,I=S.update,F.union,F.isdisjoint,F.difference,F.intersection
def r(n,a,c):
 U(c,P)
 if L(I(N(Q[n],C[n]),a))<2:return 1
 w=D(P,N(a,[n]));e=S();u=S([next(iter(w))])
 while u:n=I(Q[u.pop()],w);U(u,D(n,e));U(e,n)
 return L(e)==L(w)
def T(a,o,i,c,k):
 s,p,m=a
 for _ in o:
  t=s,p,N(m,[_]);e=D(o,[_])
  if t[2] in c:o=e;continue
  c.add(t[2]);n=D(Q[_],m);U(k,n)
  if not J(i,n)or not r(_,N(m,i),k):o=e
  elif s==L(t[2]):yield t
  else:yield from T(t,N(e,n),i,c,k)
s,*p=input().split()
X,Y=eval(s)
A=[]
l=1,-1,0,0
P=F((x,y)for y in R(Y)for x in R(X))
exec("Q%sl,l[::-1]%s;C%s(1,1,-1,-1),l[:2]*2%s"%(('={(x,y):F((x+i,y+j)for i,j in zip(',')if X>x+i>-1<y+j<Y)for x,y in P}')*2))
for a in p:a,x,y=eval(a);k=x,y;A+=[(a,k,F([k]))]
A.sort(reverse=1)
k=F(a[1]for a in A)
p=[O]*L([a for a in A if a[0]!=1])
g,h=p[:],p[:]
i=0
while 1:
 if g[i]is O:h[i]=S();f=O;g[i]=T(A[i],Q[A[i][1]],D(N(k,*p[:i]),[A[i][1]]),S(),h[i])
 try:p[i]=g[i].send(f)[2]
 except:
  f=I(N(k,*p[:i]),h[i]);g[i]=p[i]=O;i-=1
  while J(p[i],f):g[i]=p[i]=O;i-=1
 else:
  i+=1
  if i==L(p):
   z=N(k,*p)
   if not any(J(z,F(zip([x,x+1]*2,[y,y,y+1,y+1])))for x in R(X-1)for y in R(Y-1)):break
   for c in h:U(c,z)
b=[X*['.']for i in R(Y)]
for x,y in z:b[y][x]='#'
for l in b[::-1]:print(''.join(l))

Wypróbuj online!

Spójrz na kod bez golfa .