Liczba otworów w wielokącie

11

Problem : Policz liczbę otworów w połączonym wielokącie. Łączność wielokąta jest gwarantowana pod warunkiem, że każdy trójkąt w triangulacji wejściowej dzieli co najmniej 1 bok z innym trójkątem i że istnieje tylko jeden taki połączony zestaw trójkątów.

Wejście znajduje się lista Lz npunktów płaszczyzny, a także wykaz T3-krotki z wpisami z 0...n-1. Dla każdego elementu w Tkrotce (t_1,t_2,t_3)reprezentuje trzy wierzchołki (z listy L) trójkąta w triangulacji. Zauważ, że jest to triangulacja w sensie „triangulacji wielokąta” , z tego powodu nigdy nie będzie dwóch trójkątów na Ttym zachodzeniu. Dodatkowym zastrzeżeniem jest to, że nie będziesz musiał dezynfekować danych wejściowych Li Tnie będzie zawierał żadnych powtórzeń.

Przykład 1 : Jeśli L = {{0,0},{1,0},{0,1},{1,2}}i T = {{0,1,2},{1,2,3}}wtedy podany wielokąt ma liczbę otworów równą 0.

Rycina 1

Przykład 2 : Jeśli L = {{0,0},{1,0},{2,0},{2,1},{2,2},{1,2},{0,2},{0,1},{.5,.5},{1.5,.5},{1.5,1.5},{.5,1.5}}i T = {{5,6,11},{5,10,11},{4,5,10},{3,8,10},{2,3,9},{2,8,9},{1,2,8},{0,1,8},{0,8,11},{0,7,11},{6,7,11},{3,4,10}}wtedy wejście wielokąta powinno dać wynik 2.

Rysunek 2

Zadanie polega na napisaniu najkrótszy program (lub funkcja), która pobiera Li Tjako wejście i zwraca liczbę otworów. „Zwycięzca” zostanie uznany za zgłoszenie o najmniejszej liczbie znaków (wstępna data zakończenia 1 czerwca).

Przykładowe formatowanie wejściowe (zwróć uwagę na indeksowanie 0):

0,0
1,0
0,1
1,2
0,1,2
1,2,3    
Kaya
źródło
1
„Łączność wielokąta jest gwarantowana pod warunkiem, że każdy trójkąt w triangulacji wejściowej dzieli co najmniej 1 bok z innym trójkątem”. - nie To nie jest wystarczający warunek. Weźmy na przykład T=1,2,3/1,2,4/5,6,7/5,6,8. Każdy trójkąt dzieli krawędź z innym trójkątem, ale triangulacja jest rozłączona
John Dvorak
Czy możemy założyć, że dane wejściowe reprezentują prawidłową częściową triangulację (żadne dwa trójkąty nie zachodzą na siebie i żaden trójkąt nie występuje dwa razy) i triangulacja jest połączona?
John Dvorak,
Czy możemy również założyć, że wejście jest połączone krawędzią w tym sensie, że nie można usunąć skończonego zestawu punktów, aby rozłączyć kształt? (np. T=1,2,3/1,4,5jest podłączony, ale nie podłączony do krawędzi)
John Dvorak,
2
Nie jestem pewien, dlaczego ostatnio zaczęła pojawiać się ta firma dotycząca dat zakończenia. Możesz zmienić zaakceptowaną odpowiedź, więc nie musisz ustalać daty zakończenia. Rozsądne jest, abyś pomyślał, że musisz poczekać tydzień przed wybraniem odpowiedzi, aby nie odstraszyć ludzi od myślenia, że ​​pierwsza odpowiedź jest nie do pobicia, ale dopóki jesteś aktywny w witrynie, możesz zmienić wybraną odpowiedź jeśli ktoś opublikuje lepszy. Odpowiednie dyskusje na temat meta obejmują meta.codegolf.stackexchange.com/q/542/194 i meta.codegolf.stackexchange.com/q/193/194
Peter Taylor

Odpowiedzi:

5

GolfScript (23 znaki)

~.{2*2/~}%{$}%.&,@@+,-)

Przyjmuje format wejściowy przy użyciu notacji tablicowej GolfScript i współrzędnych cytowanych (lub całkowych). Na przykład

$ golfscript codegolf11738.gs <<<END
[["0" "0"] ["1" "0"] ["2" "0"] ["2" "1"] ["2" "2"] ["1" "2"] ["0" "2"] ["0" "1"] [".5" ".5"] ["1.5" ".5"] ["1.5" "1.5"] [".5" "1.5"]] [[5 6 11] [5 10 11] [4 5 10] [3 8 10] [2 3 9] [2 8 9] [1 2 8] [0 1 8] [0 8 11] [0 7 11] [6 7 11] [3 4 10]]
END
2

( Odpowiednik online )

lub

$ golfscript codegolf11738.gs <<<END
[[0 0] [1 0] [0 1] [1 2]] [[0 1 2] [1 2 3]]
END
0

( Odpowiednik online )

Peter Taylor
źródło
5

Python, 71

Poniżej znajduje się program (nie funkcja ), który oblicza pożądaną liczbę.

len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1

Przykładowe użycie:

>>> L = ((0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,1),(.5,.5),(1.5,.5),(1.5,1.5),(.5,1.5))
>>> T = ((5,6,11),(5,10,11),(4,5,10),(3,8,10),(2,3,9),(2,8,9),(1,2,8),(0,1,8),(0,8,11),(0,7,11),(6,7,11),(3,4,10))
>>> len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1
2
Przywróć Monikę
źródło
+1 za używanie ikony, korzystanie z frozenset zamiast sortowania, zip (nie mogę powiedzieć, że kiedykolwiek go użyłem, muszę się zapoznać).
Kaya
3

APL, 36

{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}

Funkcja przyjmuje Lza swój lewy argument i Tza prawy.

Na przykład:

      L←(0 0)(1 0)(0 1)(1 2)
      T←(0 1 2)(1 2 3)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
0
      L←(0 0)(1 0)(2 0)(2 1)(2 2)(1 2)(0 2)(0 1)(.5 .5)(1.5 .5)(1.5 1.5)(.5 1.5)
      T←(5 6 11)(5 10 11)(4 5 10)(3 8 10)(2 3 9)(2 8 9)(1 2 8)(0 1 8)(0 8 11)(0 7 11)(6 7 11)(3 4 10)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
2

Objaśnienie, przechodząc od prawej do lewej:

  • ⍴⍺,⍵łączy dwa wektory wejściowe i zwraca ich długość ( V + F)
  • Wchodzenie do następnego bloku:
    • ¨⍵ stosuje funkcję po lewej do każdego elementu prawego argumentu i zwraca wynik
    • ⍵,⍵ zwraca właściwy argument skonkatenowany z samym sobą
    • 3 2⍴kształtuje argument wektorowy na trzy pary. W tym przypadku łączy w sobie pierwszą i drugą, trzecią i pierwszą oraz drugą i trzecią pozycję wektora.
    • ,/ łączy ze sobą argument wektorowy
    • ⍵[⍋⍵] sortuje właściwy argument
    • ∪/ odfiltrowuje wszelkie duplikaty
    • ⍴⊃ zamienia zagnieżdżony skalar w wektor i zwraca jego długość.
    • Cała funkcja zwraca liczbę krawędzi w kształcie ( E)
  • 1 jest zrozumiałe (mam nadzieję ...)

Cała funkcja następnie zwraca 1+E-(V+F), lub 1-(F+V-E).

Zmienność
źródło
Prawie dokładnie to, co robi moje rozwiązanie GolfScript. Dziwi mnie, że jest o wiele dłużej niż GolfScript.
Peter Taylor
@PeterTaylor Byłem zaskoczony, że Twoje rozwiązanie GolfScript było o wiele krótsze! (Ale z drugiej strony jest to GolfScript)
Zmienność
2

Mathematica, 93 (jeszcze mało golfa)

f[l_, t_] :=  Max@MorphologicalComponents[Erosion[Graphics[
                                                        GraphicsComplex[l, Polygon[t + 1]]], 1]] - 1

(Dodano spacje dla zachowania przejrzystości)

Testowanie:

f[{{0, 0}, {1, 0}, {0, 1}, {1, 2}}, {{0, 1, 2}, {1, 2, 3}}]
(*
 -> 0
*)

{l, t} = {{{0, 0}, {1,   0}, {2,    0}, {2,     1}, {2,    2}, {1, 2}, {0, 2}, 
           {0, 1}, {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}}, 

           {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3,  9}, 
            {2, 8,  9}, {1,  2,  8}, {0, 1,  8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}}};
f[l, t]
 (*
  -> 2
 *)
Dr Belizariusz
źródło
Czy to nie polega na tym, że trójkąty lub dziury mają pewien minimalny rozmiar (argument na to Erosion)?
John Dvorak,
@JanDvorak Być może się mylę, ale myślę, że jeśli nie użyjesz nieskończonej precyzji arytmetyki, każde rozwiązanie będzie działać, dopóki nie osiągniesz określonego minimalnego rozmiaru (musisz zdecydować, czy trzy punkty są wyrównane, czy nie). Po prostu w tego rodzaju rozwiązaniu problem jest wyraźnie określony.
Dr Belisarius
jeśli zastosujesz podejście topologiczne, nie musisz. Jeśli są trzy punkty współliniowe, potrzebujesz trójkąta o zerowej powierzchni - w przeciwnym razie masz dziurę.
John Dvorak,
@belisarius. Oto odpowiedź, którą otrzymałem od pomocy technicznej Wolfram na temat rozbieżności między naszymi wynikami: „Cześć - dziękuję za wiadomość e-mail. Potwierdziłem, że kod daje różne wyniki na komputerach Mac i Windows. Nie sądzę, że jest to zamierzone zachowanie, więc Złożyłem raport z naszymi programistami na ten temat. Z pewnością przekażę wszelkie przydatne informacje, które otrzymam od naszych programistów na ten temat. Daj mi znać, jeśli masz dodatkowe pytania ... Wsparcie techniczne Wolfram Research , Inc. ”
DavidC
@DavidCarraher „Tak, mam dodatkowe pytania: Czy wyślesz mi czek na każdy błąd?”
Dr Belisarius
2

Rubinowy, 239 znaków (227 treści)

def f t
e=t.flat_map{|x|x.permutation(2).to_a}.group_by{|x|x}.select{|_,x|x.one?}.keys
n=Hash[e]
(u,n=n,n.dup;e.map{|x|a,b=*x;n[a]=n[n[a]]=n[b]})until n==u
n.values.uniq.size+e.group_by(&:last).map{|_,x|x.size}.reduce(-1){|x,y|x+y/2-1}
end

zauważ, że rozważam tylko topologię. W żaden sposób nie używam pozycji wierzchołków.

osoba dzwoniąca (oczekuje T w formacie Mathematica lub JSON):

input = gets.chomp
input.gsub! "{", "["
input.gsub! "}", "]"
f eval(input)

Test:

f [[0,1,2],[1,2,3]]
#=> 0
f [[5, 6, 11], [5, 10, 11], [4, 5, 10], [3, 8, 10], [2, 3, 9], [2, 8, 9], [1, 2, 8], [0, 1, 8], [0, 8, 11], [0, 7, 11], [6, 7, 11], [3, 4, 10]]
#=> 2
f [[1,2,3],[3,4,5],[5,6,1],[2,3,4],[4,5,6],[6,1,2]]
#=> 1
John Dvorak
źródło
Yay, podejście charakterystyczne dla eulera. Tak to zrobiłem w Pythonie.
Kaya
2
@Kaya. (Zobacz Egg of Columbus en.wikipedia.org/wiki/Egg_of_Columbus ) Gdy ktoś udzieli odpowiedzi Eulerian na twoje pytanie, prawdopodobieństwo, że inni pójdą za nim, znacznie wzrośnie. Zapewniam cię, że odkrywanie tego podejścia jest o wiele trudniejsze i satysfakcjonujące, dopiero później nawiązując do pracy Eulera z wielościanami.
DavidC
2

Mathematica 76 73 72 67 62

Po wielu eksperymentach zdałem sobie sprawę, że dokładna lokalizacja wierzchołków nie ma znaczenia, więc przedstawiłem problem z grafami. Niezbędne niezmienniki, liczba trójkątów, krawędzi i wierzchołków pozostały niezmienne (pod warunkiem, że uda się uniknąć przekroczenia linii).

Na wykresie były dwa rodzaje wewnętrznych „trójkątów”: były to prawdopodobnie twarze, tj. „Wypełniony” trójkąt, i te, których nie było. Liczba ścian wewnętrznych nie miała żadnego związku z krawędziami lub wierzchołkami. Oznaczało to, że dziurkowanie w pełni „wypełnionych” wykresach zmniejszało tylko liczbę twarzy. Bawiłem się systematycznie z wariacjami między trójkątami, śledząc twarze, wierzchołki i krawędzie. W końcu zdałem sobie sprawę, że liczba otworów zawsze była równa 1 - # twarzom - # wierzchołkom + # krawędziom. Okazało się, że wynosi 1 minus charakterystykę Eulera (o której wiedziałem tylko w kontekście regularnych wielościanów (chociaż długość krawędzi wyraźnie nie miała znaczenia).

Poniższa funkcja zwraca liczbę otworów, gdy wprowadzane są wierzchołki i trójkąty. W przeciwieństwie do mojego wcześniejszego zgłoszenia, nie polega on na skanowaniu obrazu. Możesz myśleć o tym jako o 1 - charakterystyce Eulera, tj. 1 - (F + V -E) gdzie F= #faces, V= # wierzchołki, E= # krawędzie. Funkcja zwraca liczbę otworów, 1 - (F + V -E)biorąc pod uwagę rzeczywiste ściany (trójkąty) i wierzchołki.

Można łatwo wykazać, że usunięcie dowolnego trójkąta na zewnątrz kompleksu nie ma wpływu na charakterystykę Eulera, niezależnie od tego, czy dzieli on jeden czy 2 boki z innymi trójkątami.

Uwaga: Małe litery vzostaną użyte zamiast Loryginalnego preparatu; to znaczy, że zawiera same wierzchołki (nie V, liczba wierzchołków)

fjest stosowany Tz oryginalnego preparatu; to znaczy zawiera trójkąty, reprezentowane jako uporządkowany potrójny indeks wierzchołków.

Kod

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&

(Podziękowania dla pana Kreatora za usunięcie 5 znaków przez wyeliminowanie reguły zastępowania.)


Przykład 1

v = {{0, 0}, {1, 0}, {0, 1}, {1, 2}}; f = {{0, 1, 2}, {1, 2, 3}};

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

0

Zero otworów.


Przykład 2

v = {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}, {1, 2}, {0, 2}, {0, 1} , {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}}; f = {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3, 9}, {2, 8, 9} , {1, 2, 8}, {0, 1, 8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}};

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

2)

Zatem 2 otwory są w przykładzie 2.

DavidC
źródło
czy w zasadzie rasteryzujesz triangulację i zrzucasz bibliotekę graficzną na ten obraz? Czy to nie zawodzi, jeśli dziura jest zbyt mała?
John Dvorak,
1
twój drugi przykład zwraca tutaj 0 (dlatego nie użyłem MorphologicalEulerNumber[]). Mma 9.01, Win XP.
Dr Belisarius
Używam również wersji 9.0.1, ale na komputerze Mac. Mówisz, że Mathematica zwraca inną odpowiedź niż moja w systemie Windows? Jeśli tak, to brzmi jak błąd (w wersji Windows XP).
DavidC
@DavidCarraher Tak: i.stack.imgur.com/LKcr1.png
Dr Belisarius
@Jan Dvorak. MorphologicalEulerNumberczasami wymaga obrazu; odmawia przyjęcia obiektu graficznego. W takich przypadkach rozmiar dziury i rozdzielczość mają kluczowe znaczenie (patrz codegolf.stackexchange.com/questions/8706/… ). Ale tutaj działa bezpośrednio z obiektem Graphics, który wyraźnie zawiera wszystkie wierzchołki. Wyobraziłem sobie (lub miałem nadzieję), że zastosuje podejście, które nie zależy od obrazu. Chciałbym wiedzieć, jak próbował rozwiązać problem. Być może niektóre spelunkowanie w kodzie źródłowym funkcji wyjaśni rzeczy.
DavidC
1

Python, 107

Uświadomiłem sobie, że bezpośrednie parowanie było krótsze niż from itertools import*i pisanie combinations(). Zauważyłem również, że moje rozwiązanie opierało się na wejściowych trójkątnych ścianach, których wierzchołki były wymienione w spójnej kolejności. Dlatego wzrost liczby znaków nie jest tak duży.

f=lambda l,t:1-len(l+t)+len(set([tuple(sorted(m))for n in[[i[:2],i[1:],[i[0],i[2]]]for i in t]for m in n]))

Python, 115

Podejście charakterystyczne dla Eulera, gadatliwość itertoolów wydaje się niemożliwa do uniknięcia. Zastanawiam się, czy taniej byłoby zastosować bardziej bezpośrednią technikę tworzenia par wierzchołków.

from itertools import*
f=lambda l,t:1-len(l+t)+len(set([m for n in[list(combinations(i,2)) for i in t]for m in n]))

Przykład użycia:

> f([[0,0],[1,0],[0,1],[1,2]],[[0,1,2],[1,2,3]])
> 0
> f([[0,0],[1,0],[2,0],[2,1],[2,2],[1,2],[0,2],[0,1],[.5,.5],[1.5,.5],[1.5,1.5],[.5,1.5]],[[5,6,11],[5,10,11],[4,5,10],[3,8,10],[2,3,9],[2,8,9],[1,2,8],[0,1,8],[0,8,11],[0,7,11],[6,7,11],[3,4,10]])
> 2
Kaya
źródło