29
\$\begingroup\$

Imagine a bunch of rectangles drawn in the plane, each rectangle with its vertices at integer coordinates and its sides parallel to the axes:

enter image description here

The rectangles partition the plane into a number of disjoint regions, coloured red and blue below:

enter image description here

Your goal is to find the number of such regions which are perfect squares. In the example above, there are three:

enter image description here

Note that the big square in the middle is not counted as it is not a single region, but is instead made up of several smaller disjoint regions.

Input

You may write a function or a full program for this challenge.

Input will be 4n nonnegative integers defining n rectangles in the plane. Each rectangle is represented by two opposing vertices, e.g. 4 9 7 8 represents the rectangle with opposing vertices (4, 9) and (7, 8). Note that this rectangle could also be represented as 7 8 4 9 or 4 8 7 9.

The exact input format is flexible (e.g. space-separated string, comma-separated string, single array of integers, list of coordinate tuples, and so on) but please be reasonable and give an example of how to run your code in your post. You may not reorder the input.

For simplicity, you can assume that no two edges will be overlapping — this includes overlapping at a vertex. In particular, this implies that no two rectangles will be touching edge-to-edge or corner-to-corner, and the rectangles will have nonzero area.

Output

Your program should print or return a single integer, which is the number of square regions.

Scoring

This is code golf, so the code in the fewest bytes wins.


Test cases

Input:

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

Output:

4

This is simply four disjoint squares:

enter image description here


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

Output:

3

This is the example test case at the start of the post.


Input:

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

Output:

7

enter image description here


Input:

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

Output:

14

enter image description here


Input:

0 99999 100000 0

Output:

0

This is just one big rectangle.


Input:

0 99999 100000 0
2 1 142857 285714

Output:

1

Two big rectangles which overlap.

\$\endgroup\$
0

3 Answers 3

14
\$\begingroup\$

Python 2, 480 436 386 352 bytes

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 "})

Takes a list of coordinate pairs through STDIN in the format:

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

and prints the result to STDOUT.


The actual program, after string replacement, is:

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)

Explanation

Instead of fiddling with complex polygons, this program deals with simple line segments. For each input rectangle, we add each of its four edges to a collective segment list, individually. Adding a segment to the list goes as follows: we test each of the existing segments for intersection with the new segment; if we find an intersection, we divide both segments at the point of intersection and continue. To make things easier, we actually keep two separate segment lists: a horizonal one and a vertical one. Since segments don't overlap, horizontal segments can only intersect vertical segments and vice versa. Better yet, it means that all intersections (not considering the edges of the same rectangle) are "proper," i.e., we don't have T-shaped intersections, so "both sides" of each segment are truly divided.

Once we've constructed the segment list(s), we start counting squares. For each combination of four segments (particularly, two horizontal segments and two vertical ones,) we test if they form a square. Furthermore, we verify that no vertex lies within this square (which can happen if, for example, we have a small square inside a bigger one.) This gives us the desired quantity. Note that even though the program tests each combination four times in different orders, the particular ordering of the segment coordinates guarantees that we count each square only once.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm pretty impressed by how quickly you solved this and the way you approached the problem! The for loops make me go "surely something can be done..." \$\endgroup\$
    – Sp3000
    Dec 16, 2014 at 14:34
  • \$\begingroup\$ @Sp3000 Yeah. I tried using itertools for the loops but it ended up being longer. I can shave a few bytes with exec + string replacements, but nothing too exciting. \$\endgroup\$
    – Ell
    Dec 16, 2014 at 15:56
10
\$\begingroup\$

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

This is a query for the PostGIS extension to PostgreSQL. I haven't counted the input values in the total.

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

Explanation

The query builds geometries for each coordinate pair. Unions the exterior rings to properly node the lines. Turns the results into polygons and tests the width against height and the area doubled against the sum of each side squared.

It will run as a standalone query on any PostgreSQL database with the PostGIS Extension.

Edit Found a couple more.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ ... and Haskell \$\endgroup\$
    – Optimizer
    Dec 18, 2014 at 18:21
  • \$\begingroup\$ @optimizer I doubt it will last :) \$\endgroup\$
    – MickyT
    Dec 18, 2014 at 18:22
  • \$\begingroup\$ @MickyT This has turned into a healthy competition. :) \$\endgroup\$
    – Zgarb
    Dec 19, 2014 at 9:05
  • \$\begingroup\$ @zgarb it has a bit:-) but I don't think I got anything else to go. \$\endgroup\$
    – MickyT
    Dec 19, 2014 at 9:43
5
\$\begingroup\$

Haskell, 276 266 250 237 225 222 217 bytes

It keeps getting shorter... and more obfuscated.

(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]])[[],[]]

Evaluate n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)] for the first test case. I think I'm getting close to the limits of golfing this algorithm on Haskell.

This function is so slow (at least O(n3) where n is the total perimeter of all rectangles in the input) that I cannot evaluate it on the last two test cases. When I compiled it with optimizations turned on and run it on the 400-times shrunk version [(0,249,250,0),(2,1,357,714)] of the last test, it finished in a little over 12 seconds. Based on this, the actual test case would finish in about 25 years.

Explanation (partial, I will expand this when I have time)

We first build two lists h and v as follows. For each rectangle in the input, we split its border into segments of length 1. The west endpoints of horizontal segments are stored in h, and the south endpoints of vertical segments in v, as lists [x,y] of length 2. The coordinates in v are stored in a reversed form as [y,x] for golfing reasons. Then we just loop over both lists and search for horizontal edge [x,j] and vertical edge [i,y] such that x < i and i-x == j-y (so they are the northwest and southeast corners of a square), and check that the borders of the square are in the correct lists h and v, while the interior coordinates are not. The number of the positive instances of the search is the output.

\$\endgroup\$
5
  • \$\begingroup\$ Well done, I think I'll have to concede now:) \$\endgroup\$
    – MickyT
    Dec 21, 2014 at 17:01
  • \$\begingroup\$ @MickyT It's been a week so I've accepted Zgarb's answer for now, but if you manage to beat it later the check mark might move! Honestly I'm very impressed at how far you two managed to go \$\endgroup\$
    – Sp3000
    Dec 29, 2014 at 17:14
  • \$\begingroup\$ @Zgarb well deserved win:-) \$\endgroup\$
    – MickyT
    Dec 30, 2014 at 8:22
  • \$\begingroup\$ @Sp3000 thanks for a nice little challenge. \$\endgroup\$
    – MickyT
    Dec 30, 2014 at 8:24
  • \$\begingroup\$ @Sp3000 Thanks! I had much fun golfing this. \$\endgroup\$
    – Zgarb
    Dec 30, 2014 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.