Siatki mogą być kręte. Jak długo jest twój

12

Rozważ przedstawienie prostej , otwartej , dwuwymiarowej krzywej na siatce tekstu o szerokości W i szerokości H, gdzie Xreprezentuje część krzywej i .reprezentuje pustą przestrzeń i nie używa się żadnych innych znaków.

Każda przestrzeń siatki ma 8 sąsiednich pól siatki, sąsiedztwo Moore . Przestrzenie siatki poza granicami są uważane za puste.

Siatka zawiera krzywą, jeśli ma dokładnie jedną X OR, jeśli ma więcej niż jedną, Xgdzie:

  • Dokładnie dwa Xs mają tylko jeden sąsiadujący X. To są punkty końcowe krzywej.
  • Każdy Xoprócz punktów końcowych sąsiadów dokładnie dwa Xs. Tworzą one większość krzywej.

Na przykład ta siatka, w której W = 9 i H = 4 zawiera krzywą:

....X....
.X.X.X.X.
X..X..X.X
.XX.....X

Podobnie, te siatki (W = 4, H = 3) mają krzywe:

....  .X..  ....  ....  .X.X
....  X..X  ..X.  XX..  X.X.
..X.  .XX.  .X..  ....  ....

Te siatki nie zawierają jednak krzywej:

....  .XX.  ...X  XX..  ....  X.X.
....  X..X  ..XX  XX..  .X.X  .X..
....  .XX.  .X..  ....  ...X  X.X.

Długość krzywej możemy znaleźć, sumując odległości między wszystkimi sąsiadującymi parami Xs:

  • Odległość między dwoma sąsiadującymi prostopadle Xs wynosi 1 jednostkę.

    XX
    X
X

  • Odległość między dwoma sąsiednimi ukośnie Xs wynosi units2 jednostki.

    X.
.X
    .X
X.

Na przykład długość krzywej w siatce

XXX.
...X
..X.

może być zwizualizowane jako

przykład długości

więc możemy zobaczyć, że jest to 1 + 1 + √2 + √2 = 4,828427 ...

Długość krzywej z tylko jednym Xwynosi zero.

Gdy siatka nie tworzy krzywej, jej długość nie jest dobrze określona.

Wyzwanie

Biorąc pod uwagę siatkę tekstu Xs i .s, wypisz długość zawartej krzywej lub wypisz coś takiego jak -1lub, Nullaby wskazać, że siatka nie ma krzywej.

Do wprowadzania można używać innych znaków niż Xi, .jeśli to pożądane, a H i W mogą być przyjmowane jako dane wejściowe w razie potrzeby. Wprowadzanie jako zagnieżdżona lista lub macierz wypełniona 1 i 0 zamiast ciągów również jest w porządku.

Możesz wyprowadzić liczbę zmiennoprzecinkową dla długości krzywej lub alternatywnie dwie liczby całkowite A i B gdzie length = A + B*√2.

Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

XXX.
...X
..X.
2 + 2*√2 = 4.828427...

....X....
.X.X.X.X.
X..X..X.X
.XX.....X
3 + 8*√2 = 14.313708...

....
....
..X.
0 + 0*√2 = 0

.X..
X..X
.XX.
1 + 3*√2 = 5.242640...

....
..X.
.X..
0 + 1*√2 = 1.414213...

....
XX..
....
1 + 0*√2 = 1

.X.X
X.X.
....
0 + 3*√2 = 4.242640...

....
....
....
....
-1

.XX.
X..X
.XX.
-1

...X
..XX
.X..
-1

....
.X.X
...X
-1

X.X.
.X..
X.X.
-1
code-golf arithmetic geometry grid graph-theory Hobby Calvina
źródło
Zalecam zezwolenie solverowi na wybór formatu wyjściowego dla siatek, które nie mają krzywych (dowolna spójna wartość, która nie ma postaci m + n * sqrt (2) dla dowolnego m, n≥0).
Greg Martin
@Greg Brzmi dobrze. Gotowe
Calvin's Hobbies
[x.x,...,.x.]nie jest poprawna krzywa, prawda?
Magic Octopus Urn
@carusocomputing poprawnie
Calvin's Hobbies

Odpowiedzi:

3

MATL , 52 51 bajtów

t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/

Dane wejściowe to macierz zer i jedynek.

Wyjście jest Bwięc A. Brak krzywych daje wynik ujemny A.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Przy obliczaniu długości krzywej wykorzystuje się dwa zwoje 2D 1 : jeden z maską Moore'a, a drugi z maską zawierającą tylko ukośnych sąsiadów. Wyniki są dwie macierze o tej samej wielkości wejściowych, które będą oznaczone jako M i D , odpowiednio. M podaje całkowitą liczbę sąsiadów dla każdego punktu, podczas gdy D podaje liczbę diagonalnych sąsiadów.

Wyniki w M i D muszą być filtrowane, aby odrzucić punkty, które nie należą do krzywej. Ponadto należy je podzielić przez 2, ponieważ „bycie sąsiadem” jest relacją symetryczną, więc każdy punkt na krzywej jest liczony dwukrotnie.

Ustalenie, czy krzywa jest poprawna, jest bardziej kłopotliwe niż się spodziewałem. Aby to zrobić, kod testuje trzy warunki:

  1. Czy liczba jedności w M jest równa 2? (Czy są dokładnie dwa punkty z jednym sąsiadem?)
  2. Czy całkowita suma M jest równa liczbie punktów na krzywej wejściowej razy 2minus 2? (Wraz z warunkiem 1 sprawdza się, czy wszystkie niezerowe wartości w M, z wyjątkiem dwóch równych 2)
  3. Czy krzywa wejściowa zawiera jeden punkt?

Krzywa jest ważna, jeśli warunki 1 i 2 są prawdziwe, lub jeśli warunek 3 jest spełniony.

t       % Implicit input matrix of zeros and ones. Duplicate
2Y6~    % Push [1 0 1; 0 0 0; 1 0 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix D
ss      % Sum of matrix D
Gt      % Push input again wtice
3Y6     % Push [1 1 1; 1 0 1; 1 1 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix M
tt      % Duplicate twice
1=z     % Number of ones
2=      % Does it equal 2? This is condition 1
wss     % Swap. Sum of matrix
G       % Push input again
zqE     % Number of nonzeros values minus 1, and then multiplied by 2
=       % Are they equal? This is condition 2
*       % Multiply. This is a logical AND of conditions 1 and 2
G       % Push input again
z1=     % Does it contain exactly one nonzero value? This is condition 3
+       % Add. This is a logical OR with condition 3
?}      % If result was false
  _q    %   Negate and subtract 1. This makes sure we get a negative value
]       % End
ss      % Sum of matrix M
y       % Duplicate sum of matrix D from below
-       % Subtract
h       % Concatenate horizontally
2/      % Divide by 2. Implicitly display

1 Konwolucja jest kluczem do sukcesu .

Luis Mendo
źródło
1

Python 3 , 316 315 311 bajtów

Myślę, że dotyczy to wszystkich przypadków; przynajmniej przypadki testowe działają.

Ponadto z pewnością jest jeszcze wiele do gry w golfa, prawdopodobnie na początku, gdy obsługiwane są skrzynki krawędziowe.

def f(d,R,C):
 s=sum;d=[0]*(C+2),*[[0,*r,0]for r in d],[0]*(C+2);o=-1,0,1;k=[[[(1,0),(0,1)][i*j]for i in o for j in o if d[r+i][c+j]and i|j]for c in range(1,-~C)for r in range(1,-~R)if d[r][c]];w=[x/2for x in map(s,zip(*s(k,[])))]or[0,0];print([w,-1][s(w)!=s([s(z)for z in d])-1or[len(t)for t in k].count(1)>2])

Wypróbuj online!

Jak to działa:

  1. d,R,C to 1. lista list z 1 jako krzywą i 0 jako tłem, 2. liczbą wierszy i kolumn
  2. Wstaw wiersz zer przed i po oraz kolumnę zer przed i po d, abyśmy nie musieli martwić się o krawędź tablicy 2d
  3. Dla każdego 1 w tablicy 2d przeskanuj sąsiedztwo w poszukiwaniu 1 i dodaj (1,0) do listy, jeśli relacja jest ukośna, w przeciwnym razie dodaj (0,1)
  4. Zsumuj wszystkie krotki, tak aby (n, m) reprezentowała odpowiednio liczbę diagonalnych i nieprzekątnych sąsiadów
  5. Sprawdź, czy liczba relacji jest dokładnie liczbą jeden minus 1; jeśli nie, nie krzywą.

Dzięki @Helka Homba za wskazanie brakującej sprawy. Dzięki @TuukkaX i @Trelzevir za wskazówki dotyczące gry w golfa.

Nil
źródło
Wygląda na to, d=[[1,0,1],[0,1,0],[1,0,1]]że tutaj się nie powiedzie (dodana walizka testowa).
Calvin's Hobbies
@HelkaHomba Masz rację, nadzorowałem to. Dzięki! Naprawiono (teraz niestety z większą liczbą bajtów).
Nile
1
s=sumoszczędza 4 bajty.
Trełżewir
0

Mathematica, 153 150 bajtów

Switch[Sort[Join@@BlockMap[If[#[[2,2]]<1,Nothing,Tr[Tr/@#]]&,#~ArrayPad~1,{3,3},1]],{1},0,{2,2,3...},1/.#~ComponentMeasurements~"PolygonalLength",_,]&

Pobiera tablicę 2D z 0s dla .s i 1s dla Xs. Dane wyjściowe Nulldla nie-krzywych.

1/.#~ComponentMeasurements~"PolygonalLength"&

Mathematica ma do tego wbudowane 45 bajtów, ale generuje pewne liczby dla niekrzywych i 1 / sqrt (2) dla danych wejściowych {{1}}. Korekta tych kosztów kosztuje 105 bajtów (czy można grać w golfa?).

JungHwan Min
źródło