Czy te prostokąty mogą wypełnić prostokątną przestrzeń?
Biorąc pod uwagę wiele prostokątów, pytamy Cię, czy można je ustawić tak, aby wypełniały prostokątną przestrzeń.
Okular
Biorąc pod uwagę garść dowolnych m x n
prostokątów; 0 <= m, n <= 1000
, określ, czy można je ułożyć tak, aby pokrywały dokładnie prostokątny obszar bez żadnych otworów lub zakładek. Prostokąty nie mogą być obracane, a każdy prostokąt może być umieszczony tylko raz.
Wkład
Dane wejściowe w tym celu są bardzo elastyczne, o ile dane wejściowe dają jakąś listę wymiarów 2-przestrzeni. Na przykład oba poniższe są poprawne:
Rozdzielone spacją, Return
1 2
1 5
4 5
3 6
Lista wymiarów
[[1, 2], [1, 5], [4, 5], [3, 6]]
Wydajność
Wszelkie wartości prawda / fałsz, takie jak prawda / fałsz, 0/1, T / F, prawda / fałsz itp. Jeśli zamierzasz użyć metody wyjściowej, która nie jest zbyt oczywista, proszę podać w swojej odpowiedzi.
Przykłady
Przypadek testowy 1
Wkład:
1 1
1 5
2 6
Wyjście:
true
(lub coś podobnego)
Jak to zorganizować:
XYYYYY
ZZZZZZ
ZZZZZZ
Przypadek testowy 2
Wkład:
1 1
2 2
Wyjście:
false
(lub coś podobnego)
Objaśnienie: Staje się oczywiste, że nie można ustawić dwóch kwadratów o różnych rozmiarach i ustawić ich krawędzi w jednej linii.
Przypadek testowy 3
Wkład:
1 1
1 2
1 2
2 1
2 1
Wyjście:
true
(lub coś podobnego) Jak to zorganizować:
AAB
DEB
DCC
Jak wskazano @ETHProductions, dla wszystkich pozostałych przypadków testowych możesz nadal łączyć prostokąty o wspólnej długości krawędzi, dopóki nie będziesz mieć tylko jednego prostokąta, więc ten przypadek testowy służy tylko do złamania kodu używającego tego pomysłu.
Przypadek testowy 4
Wkład:
3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1
Wyjście:
true
(lub coś podobnego)
Jak to zorganizować:
AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH
Uwaga : Nie musisz określać, jak to zaaranżować, musisz jedynie ustalić, czy nie można tego zaaranżować.
To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach! Przyjmę najkrótszą odpowiedź od 14 stycznia, ale nie krępuj się przesyłać odpowiedzi później, ponieważ wciąż mogę wyrazić opinię! :)
Miłej gry w golfa!
~ AL
PS Jeśli wiesz, jaki tag należy zastosować do tego problemu, proszę go dodać, absolutnie nie mam pojęcia, co umieścić jako tag inny niż kod-golf.
EDYCJA : Twój program powinien być w stanie przetworzyć do 25 prostokątów, najwyżej 10 sekund na przyzwoitym komputerze (będę dość elastyczny na tej zasadzie).
EDYCJA : Przedłużyłem termin przyjmowania zgłoszeń do ostatniego dnia roku, ale wątpię, czy do tego czasu otrzymam odpowiedź ...
EDYCJA : Przedłużyłem termin przyjmowania zgłoszeń o 2 tygodnie, więc jeśli do tego czasu nie otrzymają więcej odpowiedzi, aktualna odpowiedź C zostanie zaakceptowana! :)
źródło
[[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]]
(co można ustawićABB ACD EED
). Możesz dodać ten prosty przypadek testowy.Odpowiedzi:
C, 1135
115812311598bajtówCóż, minął wyznaczony termin, ale widząc, jak nie ma jeszcze odpowiedzi, oto jedna (nieco długa) w C.
Zwroty:
Aktualizacja:
Oryginalny kod może utknąć na niektórych matrycach, co zajmuje znacznie dłużej niż dozwolone 10s. Obecna wersja powinna uzupełnić wszystkie macierze poniżej 1s. Odbywa się to poprzez 1) sortowanie prostokątów wejściowych i 2) pomijanie powtarzających się rozmiarów podczas dopasowywania.
Gra w golfa:
UnGolfed:
Objaśnienie: Mamy 6 funkcji:
main
,O
,Q
,F
,L
iT
.T
t EST aby sprawdzić, czy nie ma miejsca dla prostokąta w danym miejscu.L
fil l s prostokąta w buforze wyjściowym, lub alternatywnie usunięcie jednego przez nadpisanie.O
iQ
tworzyć na lewo i do góry ścian, odpowiednio, iF
f bolączki resztę prostokąt iteracyjnego.Chociaż podstawowe wyszukiwanie jest iteracyjne, eliminujemy zdecydowaną większość możliwych wektorów wyszukiwania, najpierw poprzez utworzenie dozwolonych kombinacji szerokości i wysokości dla głównego prostokąta, a następnie wyeliminowanie niemożliwych konfiguracji. Dodatkową prędkość można uzyskać w większych prostokątach, określając dolne i prawe ściany przed wypełnieniem środka, ale nie jest to wymagane do przyzwoitej prędkości przy ograniczeniu do 25 wewnętrznych prostokątów.
źródło
Haskell, 226 bajtów
Wypróbuj na Ideone
Jak to działa
Rekurencyjnie wyszukuje wszystkie częściowe nachylenia, których kształt jest diagramem Younga , dodając jeden prostokąt na raz i sprawdza, czy którykolwiek z końcowych wyników jest prostokątami.
Aby zobaczyć, że dowolne kafelki prostokąta można zbudować w ten sposób: na dowolnym kafelku niepustego diagramu Younga niech R będzie zbiorem prostokątów w kafelku, którego południowy zachód nie dotyka żadnego innego prostokąta. Ponieważ każdy wklęsły wierzchołek diagramu Younga przylega do krawędzi (nie tylko do rogu) do co najwyżej jednego prostokąta w R, a liczba tych wklęsłych wierzchołków jest o jeden mniejsza niż liczba prostokątów w R, musi być co najmniej jeden prostokąt w R, który przylega do krawędzi do żadnego z tych wklęsłych wierzchołków. Usunięcie go daje kolejny schemat Younga, więc możemy przejść przez indukcję.
źródło