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 L
z n
punktów płaszczyzny, a także wykaz T
3-krotki z wpisami z 0...n-1
. Dla każdego elementu w T
krotce (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 T
tym zachodzeniu. Dodatkowym zastrzeżeniem jest to, że nie będziesz musiał dezynfekować danych wejściowych L
i T
nie 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.
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.
Zadanie polega na napisaniu najkrótszy program (lub funkcja), która pobiera L
i T
jako 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
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łączonaT=1,2,3/1,4,5
jest podłączony, ale nie podłączony do krawędzi)Odpowiedzi:
GolfScript (23 znaki)
Przyjmuje format wejściowy przy użyciu notacji tablicowej GolfScript i współrzędnych cytowanych (lub całkowych). Na przykład
( Odpowiednik online )
lub
( Odpowiednik online )
źródło
Python, 71
Poniżej znajduje się program (nie funkcja ), który oblicza pożądaną liczbę.
Przykładowe użycie:
źródło
APL, 36
Funkcja przyjmuje
L
za swój lewy argument iT
za prawy.Na przykład:
Objaśnienie, przechodząc od prawej do lewej:
⍴⍺,⍵
łączy dwa wektory wejściowe i zwraca ich długość (V + F
)¨⍵
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ść.E
)1
jest zrozumiałe (mam nadzieję ...)Cała funkcja następnie zwraca
1+E-(V+F)
, lub1-(F+V-E)
.źródło
Mathematica, 93 (jeszcze mało golfa)
(Dodano spacje dla zachowania przejrzystości)
Testowanie:
źródło
Erosion
)?Rubinowy, 239 znaków (227 treści)
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):
Test:
źródło
Mathematica
76 73 72 6762Po 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
v
zostaną użyte zamiastL
oryginalnego preparatu; to znaczy, że zawiera same wierzchołki (nie V, liczba wierzchołków)f
jest stosowanyT
z oryginalnego preparatu; to znaczy zawiera trójkąty, reprezentowane jako uporządkowany potrójny indeks wierzchołków.Kod
(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}};
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}};
Zatem 2 otwory są w przykładzie 2.
źródło
MorphologicalEulerNumber[]
). Mma 9.01, Win XP.MorphologicalEulerNumber
czasami 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.Python, 107
Uświadomiłem sobie, że bezpośrednie parowanie było krótsze niż
from itertools import*
i pisaniecombinations()
. 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.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.
Przykład użycia:źródło