W tym wyzwaniu otrzymujesz dwa nakładające się prostokąty i musisz obliczyć prostokąty utworzone przez usunięcie jednego z drugiego.
Na przykład, jeśli usuniesz czerwony prostokąt z czarnego:
Otrzymasz jeden z następujących dwóch zestawów prostokątów:
Będziesz także musiał wykonać następujące czynności:
Mówiąc dokładniej:
- Podasz współrzędne dwóch prostokątów, A i B.
- Musisz wygenerować jak najmniej nie nakładających się prostokątów, które pokrywają cały obszar A bez B. Dozwolone jest jakiekolwiek możliwe pokrycie
- Współrzędne prostokątne są przekazywane jako 4 liczby całkowite. Możesz przekazać je w dwóch parach (reprezentujących dwa punkty narożne) lub jako krotkę / listę 4 liczb całkowitych. Twoje dane wejściowe i wyjściowe muszą być spójne.
- A i B niekoniecznie będą się nakładać lub dotykać, a każdy z nich będzie miał powierzchnię co najmniej 1
Przypadki testowe:
[(0 0) (5 5)] [(3 4) (8 7)] -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)] -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)] #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)] -> #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)] -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)] #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)] -> [(1 5) (7 8)] #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)] -> [(4 1) (10 5)] [(4 7) (10 9)] #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)] -> [(1 1) (8 6)] #Only possible output
To jest gra w golfa , więc ustaw swój kod tak krótko, jak to możliwe!
code-golf
geometry
grid
set-partitions
Nathan Merrill
źródło
źródło
{(x1, y1), (x2, y2)}
wstrzymanex1 < x2
iy1 < y2
?Odpowiedzi:
Python 2 ,
375360345343 bajtówWypróbuj online!
EDYCJE: -15 z sugestii @notjagan; kolejny -15 przez ponowne kodowanie tablicy prostokątów rozwiązania do formatu int36 i krótkiej tabeli odnośników; kolejne -2, zamieniając produkt na p zgodnie z @musicman.
Funkcja, która przyjmuje dwa prostokąty, z których każdy jest krotką ((lewy, górny), (prawy, dolny)); zwraca listę wynikowych prostokątów.
Podstawowa strategia:
Na powyższym schemacie punkty A i B są odpowiednio górną lewą i dolną prawą prostokątem „Źródła” (pierwszy prostokąt).
Znajdujemy położenie każdego górnego lewego
(u,v)
i dolnego prawego(x,y)
prostokąta „Maska” w tej siatce.Jeśli oba te punkty znajdują się w pierwszej lub ostatniej kolumnie; lub pierwszy lub ostatni rząd; wtedy nie ma nakładania się; i możemy zwrócić tylko źródło Source.
W przeciwnym razie pozostało 16 przypadków; na przykład pierwszym przykładem PO jest przypadek, który możemy oznaczyć
(1,1),(2,2)
. Każdy przypadek można odwzorować na zbiór wynikowych prostokątów, których narożniki są zawsze współrzędne z wartościami poziomymi w prostokątach źródłowych po lewej, prawej stronie lub prostokątach maski po lewej, prawej stronie; i podobnie dla wartości pionowych, góry, dołu lub masek źródła.Na przykład w tym
(1,1),(2,2)
przypadku prostokąty będą,((l,t),(T,r))
a((l,T),(R,b))
gdziel,t,r,b
iL,T,R,B
są odpowiednio lewą, górną, prawą i dolną prostokątami Źródło i Maska.Możemy więc utworzyć tabelę przeglądową, która odwzorowuje współrzędne na zbiór wszystkich takich możliwych kombinacji (o co chodzi w tym
product(product(*zip(*)))
bicie) na zbiór prostokątów, które powinny być zapewnione dla każdego z przypadków (które po pewnym dekompresji golfa , dotyczy reszty rzeczy na liście).źródło
p=product
i zastąpienieproduct(product
zp(p
JavaScript, 115 bajtów
nakładająca się wersja:
Wprowadź w następującym formacie:
f([1,1,8,8])([0,6,9,9])
Oznacz dane wejściowe jako ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))
Jeśli którykolwiek z poniższych warunków jest spełniony, zwróć pierwszy prostokąt bez zmian:
Inaczej
źródło
f([0, 30, 10, 40])([5, 1, 6, 2])
powinien wrócić,[[0, 30, 10, 40]]
ale zamiast tego powraca[[0,30,5,40],[6,30,10,40]]
Java, 268 bajtów
Nie golfił
Przekaż dane wejściowe jako argumenty. Przykład
źródło
Python 2 , 272 bajty
Wypróbuj online!
Działa to poprzez przetestowanie każdej komórki w pierwszym prostokącie pod kątem lewości = 1, aboveness = 4, prawości = 2 i belowness = 8 w / r względem drugiej i ORing wyniku. Jeśli drugi nie przecina = 0 z pierwszym, wówczas oryginał jest zwracany, w przeciwnym razie zwracana jest kombinacja lewego plasterka, prawego plasterka, górnego plasterka i dolnego plasterka, z zakwaterowaniem dla nakładania się.
źródło