tło
Chcę zbudować ogrodzenie. W tym celu zebrałem kilka tyczek i przyłożyłem je do ziemi. Zebrałem też wiele desek, które przykleję do słupów, aby zrobić prawdziwe ogrodzenie. Podczas budowania przedmiotów mam tendencję do uniesienia się i najprawdopodobniej po prostu przybijam deski do tyczek, dopóki nie będzie już miejsca na ich ułożenie. Chcę, żebyś wyliczył możliwe ogrodzenia, z którymi mogę skończyć.
Wejście
Twoje dane wejściowe to lista dwuwymiarowych współrzędnych całkowitych reprezentujących pozycje biegunów, w dowolnym dogodnym formacie. Możesz założyć, że nie zawiera duplikatów, ale nie możesz zakładać niczego o jego kolejności.
Deski są reprezentowane przez proste linie między biegunami, a dla uproszczenia rozważamy tylko poziome i pionowe deski. Deska może być połączona z dwoma biegunami, jeśli nie ma między nimi innych biegunów lub desek, co oznacza, że deski nie mogą się przecinać. Rozmieszczenie biegunów i desek jest maksymalne, jeśli nie można do niego dodać żadnych nowych desek (równoważnie, między dowolnymi dwoma biegunami ustawionymi poziomo lub pionowo jest słup lub deska).
Wynik
Twój wynik to liczba maksymalnych układów, które można zbudować za pomocą biegunów.
Przykład
Rozważ listę danych wejściowych
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]
Patrząc z góry odpowiedni układ biegunów wygląda mniej więcej tak:
o
o o
o o
o o
o
Istnieją dokładnie trzy maksymalne układy, które można zbudować za pomocą tych biegunów:
o o o
o-o o|o o-o
o----o o||| o o| | o
o-o o|o o-o
o o o
Zatem prawidłowe wyjście to 3
.
Zasady
Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.
Przypadki testowe
[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8
(0,-2)
dobry połów. Zmieniam się teraz.Odpowiedzi:
Mathematica, 301 bajtów
Jest to funkcja bez nazwy, która przyjmuje współrzędne jako zagnieżdżone
List
i zwraca liczbę całkowitą. Oznacza to, że możesz nadać mu nazwę i nazwać ją lub po prostu dołączyćZ wcięciem:
Nie potrafię nawet wyrazić, jak naiwna jest ta implementacja ... zdecydowanie nie może być bardziej brutalna ...
o--o--o
dają tylko dwa ogrodzenia zamiast trzech).Zaskakująco rozwiązuje wszystkie przypadki testowe praktycznie natychmiast.
Naprawdę fajną sztuczką, którą odkryłem w tym celu, jest
Orderless
ograniczenie liczby wzorów, które muszę dopasować. Zasadniczo, gdy chcę porzucić zestawy ogrodzeń za pomocą ogrodzeń krzyżowych, muszę znaleźć parę ogrodzenia pionowego i poziomego i sprawdzić na nich stan. Ale nie wiem, w jakiej kolejności będą się pojawiać. Ponieważ wzorce list są zwykle zależne od kolejności, powstałyby dwa naprawdę długie wzorce. Zamiast tego zastępuję otaczającą listę funkcjąt
zt @@@
- która nie jest zdefiniowana, więc jest utrzymywana bez zmian. Ale ta funkcja jestOrderless
taka, że mogę po prostu sprawdzić pojedyncze zamówienie we wzorcu, a Mathematica sprawdzi je pod kątem wszystkich permutacji. Następnie ponownie umieszczam listy za pomocąList @@@
.Żałuję, że nie ma wbudowanej funkcji, która jest a)
Orderless
, b) nieListable
i c) nie zdefiniowana dla 0 argumentów lub listy argumentów. Wtedy mógłbym to zastąpićt
. Ale wydaje się, że nie ma takiego operatora.źródło
Haskell, 318 bajtów
Zastosowanie:
p [(1,0),(0,1),(-1,0),(0,-1)]
. Wynik:2
Jak to działa:
źródło