Squarefinder - Lokalizowanie regularnych tetragonów

27

Wyobraź sobie kilka prostokątów narysowanych w płaszczyźnie, każdy prostokąt z wierzchołkami o współrzędnych całkowitych i bokami równoległymi do osi:

wprowadź opis zdjęcia tutaj

Prostokąty dzielą płaszczyznę na kilka rozłącznych regionów, które mają kolor czerwony i niebieski poniżej:

wprowadź opis zdjęcia tutaj

Twoim celem jest znalezienie liczby takich regionów, które są idealnymi kwadratami. W powyższym przykładzie są trzy:

wprowadź opis zdjęcia tutaj

Zauważ, że duży kwadrat pośrodku nie jest liczony, ponieważ nie jest to pojedynczy region, ale składa się z kilku mniejszych, niepowiązanych regionów.

Wkład

Możesz napisać funkcję lub pełny program dla tego wyzwania.

Dane wejściowe będą 4nnieujemnymi liczbami całkowitymi definiującymi nprostokąty w płaszczyźnie. Każdy prostokąt jest reprezentowany przez dwa przeciwstawne wierzchołki, np. 4 9 7 8Reprezentuje prostokąt z przeciwległymi wierzchołkami (4, 9)i (7, 8). Zauważ, że ten prostokąt można również przedstawić jako 7 8 4 9lub 4 8 7 9.

Dokładny format wejściowy jest elastyczny (np. Ciąg oddzielony spacją, ciąg oddzielony przecinkami, pojedyncza tablica liczb całkowitych, lista krotek współrzędnych itd.), Ale bądź rozsądny i podaj przykład, jak uruchomić kod w poście. Nie możesz zmienić kolejności danych wejściowych.

Dla uproszczenia można założyć, że żadne dwie krawędzie nie będą się pokrywać - dotyczy to także nakładania się na wierzchołek. W szczególności oznacza to, że żadne dwa prostokąty nie będą się stykać od krawędzi do krawędzi lub od narożnika do narożnika, a prostokąty będą miały niezerowe pole.

Wydajność

Twój program powinien wydrukować lub zwrócić pojedynczą liczbę całkowitą, czyli liczbę kwadratowych regionów.

Punktacja

To jest kod golfowy, więc kod w najmniejszej liczbie bajtów wygrywa.


Przypadki testowe

Wkład:

0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2

Wydajność:

4

To po prostu cztery rozłączne kwadraty:

wprowadź opis zdjęcia tutaj


Wkład:

2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17

Wydajność:

3

To jest przykładowy przypadek testowy na początku postu.


Wkład:

0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8

Wydajność:

7

wprowadź opis zdjęcia tutaj


Wkład:

5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14

Wydajność:

14

wprowadź opis zdjęcia tutaj


Wkład:

0 99999 100000 0

Wydajność:

0

To tylko jeden duży prostokąt.


Wkład:

0 99999 100000 0
2 1 142857 285714

Wydajność:

1

Dwa duże prostokąty, które zachodzą na siebie.

Sp3000
źródło

Odpowiedzi:

9

SQL (POSTGIS), 286 269 261 240 226 218 216

To jest zapytanie o rozszerzenie PostGIS do PostgreSQL. Nie policzyłem wartości wejściowych w sumie.

SELECT SUM(1)FROM(SELECT(ST_Dump(ST_Polygonize(g))).geom d FROM(SELECT ST_Union(ST_Boundary(ST_MakeEnvelope(a,b,c,d)))g FROM(VALUES
-- Coordinate input
(2, 1, 3, 11)
,(1, 10, 5, 19)
,(6, 10, 11, 3)
,(8, 8, 15, 15)
,(13, 13, 9, 5)
,(15, 1, 19, 7)
,(17, 19, 19, 17)
)i(a,b,c,d))i)a WHERE(ST_XMax(d)-ST_XMin(d))^2+(ST_YMax(d)-ST_YMin(d))^2=ST_Area(d)*2

Wyjaśnienie

Zapytanie tworzy geometrie dla każdej pary współrzędnych. Łączy zewnętrzne pierścienie, aby prawidłowo węzły linii. Przekształca wyniki w wielokąty i sprawdza szerokość względem wysokości, a obszar podwaja się w stosunku do sumy każdej strony do kwadratu.

Będzie działał jako samodzielne zapytanie w dowolnej bazie danych PostgreSQL z rozszerzeniem PostGIS.

Edytuj Znaleziono jeszcze kilka.

MickyT
źródło
1
... i Haskell
Optymalizator
@optimizer Wątpię, żeby to trwało :)
MickyT,
@MickyT To zamieniło się w zdrową konkurencję. :)
Zgarb,
@zgarb ma trochę :-), ale nie sądzę, że mam już coś do zrobienia.
MickyT,
13

Python 2, 480 436 386 352 bajty

exec u"""s=sorted;H=[];V=[]
FRIinput():
 S=2*map(s,zip(*R))
 FiI0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    FeIs(H):
     C,(A,B)=e
     if a<C<b&A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D)&c==C==(b,B)&B-b==D-d&1-any(d<X[0]<D&b<y<B Fy,XIH)Fb,aIH FB,AIH Fd,cIV FD,CIV)""".translate({70:u"for ",73:u" in ",38:u" and "})

Pobiera listę par współrzędnych przez STDIN w formacie:

[  [(x, y), (x, y)],  [(x, y), (x, y)],  ...  ]

i drukuje wynik do STDOUT.


Rzeczywistym programem, po zamianie łańcucha, jest:

s=sorted;H=[];V=[]
for R in input():
 S=2*map(s,zip(*R))
 for i in 0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    for e in s(H):
     C,(A,B)=e
     if a<C<b and A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D) and c==C==(b,B) and B-b==D-d and 1-any(d<X[0]<D and b<y<B for y,X in H)for b,a in H for B,A in H for d,c in V for D,C in V)

Wyjaśnienie

Zamiast bawić się skomplikowanymi wielokątami, ten program zajmuje się prostymi segmentami linii. Dla każdego prostokąta wejściowego dodajemy każdą z czterech krawędzi osobno do listy segmentów zbiorczych. Dodanie segmentu do listy przebiega następująco: testujemy każdy z istniejących segmentów pod kątem przecięcia z nowym segmentem; jeśli znajdziemy skrzyżowanie, dzielimy oba segmenty w punkcie przecięcia i kontynuujemy. Aby to ułatwić, w rzeczywistości prowadzimy dwie oddzielne listy segmentów: horyzontalną i pionową. Ponieważ segmenty nie zachodzą na siebie, segmenty poziome mogą przecinać tylko segmenty pionowe i odwrotnie. Co więcej, oznacza to, że wszystkie przecięcia (nie biorąc pod uwagę krawędzi tego samego prostokąta) są „właściwe”, tj. Nie mamy przecięć w kształcie litery T, więc „obie strony” każdego segmentu są naprawdę podzielone.

Po zbudowaniu listy segmentów zaczynamy odliczać kwadraty. Dla każdej kombinacji czterech segmentów (szczególnie dwóch segmentów poziomych i dwóch pionowych) sprawdzamy, czy tworzą one kwadrat. Ponadto sprawdzamy, czy żaden wierzchołek nie leży w tym kwadracie (co może się zdarzyć, jeśli na przykład mamy mały kwadrat w większym). To daje nam pożądaną ilość. Należy pamiętać, że mimo iż program testuje każdą kombinację cztery razy w różnych zamówieniach, to szczególne uporządkowanie współrzędnych segmentu gwarantuje, że każde kwadraty liczymy tylko raz.

Łokieć
źródło
1
Jestem pod wrażeniem tego, jak szybko to rozwiązałeś i jak podszedłeś do problemu! Pętle for powodują, że „na pewno coś da się zrobić ...”
Sp3000,
@ Sp3000 Tak. Próbowałem użyć itertoolspętli, ale skończyło się to na dłuższym czasie. Mogę ogolić kilka bajtów za pomocą execzamiany ciągów +, ale nic zbyt ekscytującego.
Ell
4

Haskell, 276 266 250 237 225 222 217 bajtów

Staje się coraz krótszy ... i coraz bardziej zaciemniony.

(x#i)l=mapM id[[min x i..max x i-1],l]
(y!j)l f=and[p l==p(f[y,j])|p<-map elem$f[y..j]]
s[h,v]=sum[1|[x,j]<-h,[y,i]<-v,x<i,i-x==j-y,(y!j)h$x#i,(x!i)v$y#j]
n=s.foldr(\(x,y,i,j)->zipWith(++)[x#i$[y,j],y#j$[x,i]])[[],[]]

Oceń n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]pierwszy przypadek testowy. Myślę, że zbliżam się do granic grania w golfa w tym algorytmie na Haskell.

Ta funkcja jest tak wolna (co najmniej O (n 3 ), gdzie n jest całkowitym obwodem wszystkich prostokątów na wejściu), że nie mogę jej ocenić w dwóch ostatnich przypadkach testowych. Kiedy skompilowałem go z włączonymi optymalizacjami i uruchomiłem na 400-krotnej zmniejszonej wersji [(0,249,250,0),(2,1,357,714)]ostatniego testu, zakończyłem go w nieco ponad 12 sekund. Na tej podstawie rzeczywisty przypadek testowy zakończyłby się za około 25 lat.

Wyjaśnienie (częściowe, rozwinę to, gdy będę miał czas)

Najpierw tworzymy dwie listy hi vw następujący sposób. Dla każdego prostokąta na wejściu dzielimy jego granicę na segmenty o długości 1. Zachodnie punkty końcowe segmentów poziomych są przechowywane w h, a południowe punkty końcowe segmentów pionowych vjako listy [x,y]długości 2. Współrzędne vsą przechowywane w odwróconym forma jak [y,x]z powodów golfowych. Następnie po prostu zapętlamy obie listy i szukamy poziomej krawędzi [x,j]i pionowej krawędzi [i,y]tak, że ( x < ii i-x == j-ysą to północno-zachodnie i południowo-wschodnie narożniki kwadratu), i sprawdzamy, czy granice kwadratu znajdują się na prawidłowych listach hi v, podczas gdy wnętrze współrzędne nie są. Liczba pozytywnych wystąpień wyszukiwania jest wynikiem.

Zgarb
źródło
Dobra robota, myślę, że muszę się teraz
poddać
@MickyT Minął tydzień, więc na razie zaakceptowałem odpowiedź Zgarba, ale jeśli uda ci się ją pokonać później, znak wyboru może się przesunąć! Szczerze mówiąc, jestem pod wielkim wrażeniem tego, jak daleko udało wam się dojść
Sp3000,
@Zgarb zasłużone zwycięstwo :-)
MickyT,
@ Sp3000 dzięki za miłe małe wyzwanie.
MickyT,
@ Sp3000 Thanks! Miałem dużo zabawy w golfa.
Zgarb