Created
August 13, 2017 20:57
-
-
Save PiJoules/dfe2ed724f798f0c34bfbf600968ecf3 to your computer and use it in GitHub Desktop.
This took me longer than I would have liked it to
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!usr/bin/env python | |
class Rectangle: | |
"""All rectangle methods are constant time.""" | |
def __init__(self, x1, y1, x2, y2): | |
"""Opposite corners of a rectangle. | |
These points will not be changed once set.""" | |
assert(x1 != x2) | |
assert(y1 != y2) | |
self.x1 = x1 | |
self.x2 = x2 | |
self.y1 = y1 | |
self.y2 = y2 | |
def left(self): | |
return min(self.x1, self.x2) | |
def right(self): | |
return max(self.x1, self.x2) | |
def top(self): | |
return max(self.y1, self.y2) | |
def bottom(self): | |
return min(self.y1, self.y2) | |
def area(self): | |
"""Constant but can be optomized""" | |
return abs(self.x1-self.x2) * abs(self.y1-self.y2) | |
def contains(self, x, y): | |
""" | |
Checks if the rectangle contains a point. | |
Constant but can be optomized | |
""" | |
return (min(self.x1, self.x2) < x < max(self.x1, self.x2) and | |
min(self.y1, self.y2) < y < max(self.y1, self.y2)) | |
def intersects(self, other): | |
""" | |
Returns: | |
bool: True if the rectangles do intersect. False otherwise. | |
Constant but can be optomized | |
""" | |
return self.union(other) is not None | |
def union(self, other): | |
""" | |
Intersection between 2 rectangles. | |
Returns: | |
Optional(Rectangle): Returns intersecting rectangle if they do intersect. | |
None otherwise. | |
Constant but can be optomized | |
""" | |
left = max(self.left(), other.left()) | |
right = min(self.right(), other.right()) | |
bottom = max(self.bottom(), other.bottom()) | |
top = min(self.top(), other.top()) | |
if left >= right or top <= bottom: | |
return None | |
return Rectangle(left, bottom, right, top) | |
def __str__(self): | |
return "Rectangle[x1={},y1={},x2={},y2={}]".format( | |
self.x1, self.y1, self.x2, self.y2 | |
) | |
def __hash__(self): | |
"""Constant but can be optomized""" | |
return hash(tuple(self.x1, self.x2, self.y1, self.y2)) | |
def __eq__(self, other): | |
"""Constant but can be optomized""" | |
return (self.x1 == other.x1 and | |
self.x2 == other.x2 and | |
self.y1 == other.y1 and | |
self.y2 == other.y2) | |
def powerset(s): | |
""" | |
Assumption: s is a set, so all items in it are unique | |
Args: | |
s(list[Any]) | |
Returns: | |
list[list[Any]] | |
O(n^n) time complexity, but ideally powerset is 2^n | |
""" | |
if not s: | |
return [[]] | |
else: | |
current = s[0] | |
p_rest = powerset(s[1:]) # linear slice | |
# Add current to powerset of rest | |
inclusions = [] | |
for other_set in p_rest: | |
inclusions.append([current] + other_set) | |
return inclusions + p_rest | |
def organized_powerset(s): | |
""" | |
Sort the powerset by descending size order and pack the sets of the same | |
size. | |
organized_powerset([1, 2, 3]) == [[[]], | |
[[1], [2], [3]], | |
[[1, 2], [2, 3], [1, 3]], | |
[[1, 2, 3]]] | |
O(n^n) time complexity; dominated by poweset function | |
""" | |
ps = powerset(s) | |
# Linear | |
container = [[] for i in range(len(s) + 1)] | |
for s in ps: | |
container[len(s)].append(s) | |
return container | |
def unionize(rectangles): | |
"""Take the intersection of a sequence of rectangles. | |
If any one of them does not intersect any of the others, there is no | |
intersection. | |
Linear | |
""" | |
if not rectangles: | |
return None | |
ref = rectangles[0] | |
for other in rectangles[1:]: | |
union = ref.union(other) | |
if union: | |
ref = union | |
else: | |
return None | |
return ref | |
def total_area(rectangles): | |
"""Find the total area of a sequence of potentially overlapping | |
rectangles. | |
O(n^n) complexity; dominated by powerset | |
""" | |
p_rectagles = organized_powerset(rectangles) | |
area = 0 | |
# First contains empty set | |
for i in range(1, len(p_rectagles)): # n^3 | |
if i % 2: | |
# Addative | |
sign = 1 | |
else: | |
# Subtract | |
sign = -1 | |
group = p_rectagles[i] | |
# Take union of each sub group | |
unions = [] | |
for subgroup in group: # n^2 | |
union = unionize(subgroup) # linear | |
if union: | |
unions.append(union) | |
area += sign * sum(u.area() for u in unions) | |
return area | |
def test_powerset(): | |
s = [1, 2, 3] | |
p_s = powerset(s) | |
assert(len(p_s) == 2**len(s)) | |
expected = [ | |
[1, 2, 3], | |
[1, 2], [2, 3], [1, 3], | |
[1], [2], [3], | |
[], | |
] | |
for answer in expected: | |
assert(answer in p_s), "{} not in {}".format(answer, p_s) | |
p_s_sorted = organized_powerset(s) | |
assert(all(map(lambda x: len(x) == 0, p_s_sorted[0]))) | |
assert(all(map(lambda x: len(x) == 1, p_s_sorted[1]))) | |
assert(all(map(lambda x: len(x) == 2, p_s_sorted[2]))) | |
assert(all(map(lambda x: len(x) == 3, p_s_sorted[3]))) | |
def test_total_area(): | |
# Null test | |
assert(total_area([]) == 0) | |
# Just 1 | |
r = [Rectangle(-1, -1, 1, 1)] | |
assert(total_area(r) == 4) | |
# No overlap | |
r = [Rectangle(-1, -1, 1, 1), # 4 | |
Rectangle(1, 1, 2, 2), # 1 | |
Rectangle(-2, 0, -3, 3)] # 3 | |
assert(total_area(r) == 8) | |
# Overlap between 2 | |
r = [Rectangle(-1, -1, 1, 1), # 4 | |
Rectangle(0, 0, 2, 2), # 4 (overlaps with first) | |
Rectangle(-2, 0, -3, 3)] # 3 | |
assert total_area(r) == 10 | |
# Overlap between 3 | |
r = [Rectangle(-1, -1, 1, 1), # 4 | |
Rectangle(0, 0, 2, 2), # 4 | |
Rectangle(0, 0, -3, -3)] # 9 | |
assert(total_area(r) == 15) | |
# Overlap 4 | |
r = [Rectangle(-1, -1, 1, 1), # 4 | |
Rectangle(0, 0, 2, 2), # 4 | |
Rectangle(0, 0, -3, -3), # 9 | |
Rectangle(-1, 1, 1, -4)] # 10 (overlaps all; consumes 1st) | |
assert total_area(r) == 19 | |
# Overlap 4 with one dominant rectangle | |
r = [Rectangle(-1, -1, 1, 1), # 4 | |
Rectangle(0, 0, 2, 2), # 4 | |
Rectangle(0, 0, -3, -3), # 9 | |
Rectangle(-4, -4, 4, 4)] # 64 (consumes all) | |
assert(total_area(r) == 64) | |
r = [Rectangle(-2, 1, 0, -1), # 4 | |
Rectangle(-1, 0, 1, 2), # 4 | |
Rectangle(2, 1, 0, -1), # 4 | |
Rectangle(-1, 0, 1, -2)] # 4 | |
assert(total_area(r) == 12) | |
def main(): | |
test_powerset() | |
test_total_area() | |
if __name__ == "__main__": | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment