Czy moje więzienie jest bezpieczne?

58

Twoje wyzwanie otrzymuje układ więzienny, aby dowiedzieć się, czy któryś z więźniów może uciec.

Wejście

Wejście może być w żadnym rozsądnym formacie takim jak łańcuch, tablica tablicy tablic itd. Wejście będzie się składać z trzech znaków, w tym przypadku #, Pi przestrzeni. Dane wejściowe niekoniecznie będą zawierać wszystkie trzy znaki.

  • #: Ściana
  • P: Więzień
  • spacja: pusta przestrzeń

Przykładowe dane wejściowe będą wyglądały następująco:

#####
#   #
# P #
#   #
#####

Wynik

Prawda / falsey, czy więzienie jest bezpieczne, czy nie. Więzienie jest bezpieczne tylko wtedy, gdy może pomieścić wszystkich więźniów. Jeśli jakikolwiek więzień może uciec, nie jest to bezpieczne.

Więzień może uciec, jeśli nie jest całkowicie otoczony murem. Łączenie po przekątnej jest całkowicie zamknięte.

Przypadki testowe

############# Truthy
# P #  P#   #
#   #   # P #
#############

############# Truthy
# P    P    #
#   #   # P #
#############

############# Falsey
# P #  P#   #
#   #   # P #
########## ##

####          Truthy
#   #
 #   #
  # P ####
  ####

P             Falsey

###           Falsey
# #
# #
### P
TheLethalCoder
źródło
8
Mam wrażenie, że jest to duplikat lub przynajmniej podobne wyzwanie. Dobre wyzwanie i tak.
John Dvorak
2
@JanDvorak Być może, ale z moim ograniczonym Google Fu nie mogłem znaleźć duplikatu.
TheLethalCoder
2
powiązane (Flood-fill a 2D grid)
Esolanging Fruit
3
Dobrze byłoby mieć przykłady Falsey, w których do ucieczki wymagany jest ruch poziomy i pionowy.
xnor
2
@tfbninja Naprawdę nie duplikat. Ten prosi o próbę ekstrapolacji programu na podstawie danych w celu ustalenia, czy słowo znajduje się w polu. Ten jest wypełnieniem zalewowym BFS, aby sprawdzić, czy istnieją niezamknięte przestrzenie o zaznaczonych wartościach.
HyperNeutrino

Odpowiedzi:

54

Ślimaki , 13 bajtów

!(t\P(o\ ),o~

Wypróbuj online!

Drukuje 0dla niepewnych więzień i rozmiar obwiedni wejściowej dla bezpiecznych więzień.

Chodzi o to, aby upewnić się, że nie możemy znaleźć ścieżki od Pkomórki do poza granicami ( ~) poruszającej się tylko ortogonalnie ( o) przez spacje. tJest teleport tak, że niezależnie gdzie spróbujemy mecz próbuje wszystkie możliwe pozycje wyjściowe do znalezienia P.

Martin Ender
źródło
23
Właściwe narzędzie.
Jonathan Allan
16

C # (.NET Core) , 485 480 474 470 421 408 bajtów

Absolutnie złe narzędzie i podejście, ale jednak ...

  • 7 bajtów (i więcej) zapisanych dzięki przydatnym wskazówkom TheLethalCoder.
  • 4 bajty zapisane przez zwrócenie liczby całkowitej.
  • Jeszcze 4 bajty zapisane (raz jeszcze) dzięki TheLethalCoder, zastępując ' 'je 32w porównaniach.
  • DUŻO bajtów zapisanych przez refaktoryzację kodu.
  • 13 bajtów więcej dzięki (zgadnij kto?) TheLethalCoder. :) Ciągle zapominam o jego wskazówkach, a on mi je przypomina.
m=>{var p='P';int a=m.Length,b=m[0].Length,i=0,j,x,y;var c=new System.Collections.Stack();for(;i<a;i++)for(j=0;j<b;j++)if(m[i][j]==p)c.Push(new[]{i,j});while(c.Count>0){var t=(int[])c.Pop();x=t[0];y=t[1];if(x<1|x>a-2|y<1|y>b-2)return 0;foreach(var v in new[]{-1,1}){var z=x>0&x<a-1&y>0&y<b-1;if(z&m[x+v][y]==32){m[x][y]=p;c.Push(new[]{x+v,y});}if(z&m[x][y+v]==32){m[x][y]=p;c.Push(new[]{x,y+v});}}}return 1;}

Wypróbuj online!

Zasadniczo rozszerzam pozycje P, ilekroć jest biała przestrzeń, aż osiągnie (lub nie) granicę układu.

Niektóre licencje:

  • Używam a char[][]jako danych wejściowych dla układu.
  • Zwraca się 0jako niepewne i 1bezpieczne.
Charlie
źródło
Nie możesz wziąć dodatkowych danych wejściowych do funkcji, abyś mógł przyjąć wymiary ... Chyba że możesz znaleźć meta post, aby przekonać mnie inaczej.
TheLethalCoder
1>0i 1<0są krótsze niż truei false.
TheLethalCoder
1
Może ==0zostać <1? Masz co najmniej 1 bajt niepotrzebnych białych znaków. Czy możesz usunąć new[]s? (Nie zawsze działa, ale czasem się podoba int[] n = {1,2,3};).
TheLethalCoder
1
{m[x][y]= p; c.Push(new[]->{m[x][y]=p;c.Push(new[]
TheLethalCoder
1
Możesz porównać chars do ints, więc uważam, że możesz zastąpić ==' 'to, ==32aby zapisać bajty. Powinieneś być w stanie to zrobić również w podobnych porównaniach.
TheLethalCoder
15

Perl 5 , 69 bajtów

-10 bajtów dzięki @Grimy .

-2 bajty dzięki @Neil .

77 bajtów kodu + -p0flagi.

/
/;$_=s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s?redo:!/\A.*P|P.*\Z|^P|P$/m

Wypróbuj online!

Kilka krótkich wyjaśnień:
Chodzi o to, aby umieścić Pwszędzie, gdzie więźniowie mogą się udać. Jeśli któryś z nich Pznajduje się na pierwszej / ostatniej linii lub pierwszej / ostatniej kolumnie, więźniowie mogą się tam udać i uciec, co oznacza, że ​​więzienie nie jest bezpieczne.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/szastępuje miejsca na prawej lub ryczeć Pz Plub miejsca po lewej stronie lub na górze P.
Na koniec /\A.*P|P.*\Z|^P|P$/msprawdza, czy linia zaczyna się, czy kończy na a P, czy jest Pna pierwszej lub ostatniej linii.

Dada
źródło
fajne podejście za pomocą wyrażeń regularnych! (ale prawdopodobnie BARDZO drogie, gdy przestrzeń się powiększa)
Olivier Dulac
W rzeczywistości nie jest to tak nieefektywne. W szczególności nie wymaga dużo cofania, nie ma *lub +najdłuższym dopasowaniem, jaki może zrobić, jest rozmiar linii ... Teraz oczywiście, jeśli porównasz z podejściem bardziej ręcznym, na przykład na podstawie tablic , to tak, jest to dość nieefektywne!
Dada
1
-6 bajtów poprzez połączenie dwóch podstawników: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.
Grimmy,
1
-2 bajty według golfa połączoną podstawień: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.
Grimmy,
2
@Grimy bardzo fajna gra w golfa wyrażenia regularnego! Dzięki :)
Dada,
7

JavaScript (ES6), 134 133 bajtów

Pobiera dane wejściowe jako tablicę tablic znaków. Zwraca 0(niepewny) lub 1(bezpieczny).

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

Przypadki testowe

Arnauld
źródło
Czy może po &&prostu być &?
TheLethalCoder
@TheLethalCoder Nie pierwszy, ale drugi można zastąpić |. Dzięki!
Arnauld
Nie wiedziałem, że operator spread działa na ciągach. Chłodny!
aebabis
6

JavaScript (ES6), 121 bajtów

f=s=>s==(s=s.replace(eval('/( |P)([^]{'+s.search`
`+'})?(?!\\1)[ P]/'),'P$2P'))?!/^.*P|P.*$/.test(s)&!/^P|P$/m.test(s):f(s)

Pobiera dane wejściowe jako ciąg prostokątny rozdzielany znakiem nowej linii. Zwraca 0 dla niepewnych i 1 dla bezpiecznych. Opierając się na mojej odpowiedzi na Detect Failing Castles , chociaż bardziej efektywne byłoby testowanie uciekającego więźnia na każdym kroku, niż po zakończeniu zwiedzania więzienia.

Neil
źródło
2

Oktawa, 64 55 bajtów

@(a,z=padarray(a,[1 1]))~nnz(bwfill(z==35,1,1,4)&z>35);

Wypróbuj online!

lub

Sprawdź wszystkie przypadki testowe!

Wyjaśnienie:

z=padarray(a,[1 1])       %add a boundary(of 0s) around the scene
F = bwfill(z==35,1,1,4)   %flood fill the prison starting from the boundary
~nnz(F&z>35);             %if position of at least a prisoner  is filled then the prison is not secure 
rahnema1
źródło
2

APL (Dyalog Classic) , 40 bajtów

{⊃2≠(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡(⌽1,⍉)⍣4'# '⍳⍵}

Wypróbuj online!

'# '⍳⍵kodowania '#', ' ', 'P'jak: 0 1 2

(⌽1,⍉)⍣4 surround z 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ maksymalna liczba sąsiadów wypełnia niezerowe komórki

⊃2≠ czy nie mamy 2 w lewym górnym rogu?

ngn
źródło
1

Stax , 35 bajtów CP437

ä¬my■╡╤▲l@┤êr*⌠\¶ƒläå─▄¶√¿ [Uy⌠Só4↔

Wypróbuj online!

Z pewnością potrafi to zrobić język golfowy bez wewnętrznego systemu wyszukiwania ścieżek!

Wyjaśnienie

Do wyjaśnienia używa rozpakowanego formatu.

zLz]Y+Mys+y+{{{" P|P ""PP"Rm}Y!My!Mgphh' =
zLz]Y+Mys+y+                                  Surround the original matrix with four borders of whitespaces
            {                      gp         Iterate until a fixed point is found, return the single fixed point
             {              }Y!               Store the block in register Y and execute it
              {" P|P ""PP"Rm                  For each row, flood every space adjacent to a P with P.
                               My!            Transpose the matrix and do the flooding again
                                     hh' =    The final matrix has a space on the upper left corner that has not been flooded by P 
Weijun Zhou
źródło
1

SmileBASIC, 154 146 bajtów

Miałem nadzieję, że odpowiedź wypełniająca powódź będzie krótsza niż ta.

DEF S P
FOR J=0TO 1X=1Y=1FOR I=0TO LEN(P)-1GPSET X,Y,-(P[I]=="#")GPAINT X,Y,-1,-J*(P[I]>@A)X=X*(P[I]>"31")+1INC Y,X<2NEXT
NEXT?!GSPOIT(0,0)GCLS
END

Zamień 31na odpowiedni znak ASCII.

12Me21
źródło