diff options
Diffstat (limited to 'scratch/data_structures_and_algorithms/rectangular-love.py')
| -rw-r--r-- | scratch/data_structures_and_algorithms/rectangular-love.py | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/scratch/data_structures_and_algorithms/rectangular-love.py b/scratch/data_structures_and_algorithms/rectangular-love.py new file mode 100644 index 000000000000..47c0f53979c6 --- /dev/null +++ b/scratch/data_structures_and_algorithms/rectangular-love.py @@ -0,0 +1,246 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# bottom :: Rectangle -> Int +def bottom(x): + return x.get('bottom_y') + + +# top :: Rectangle -> Int +def top(x): + return bottom(x) + x.get('height') + + +# left :: Rectangle -> Int +def left(x): + return x.get('left_x') + + +# right :: Rectangle -> Int +def right(x): + return left(x) + x.get('width') + + +# sort_highest :: Rectangle -> Rectangle -> (Rectangle, Rectangle) +def sort_highest(x, y): + if top(x) >= top(y): + return x, y + else: + return y, x + + +# sort_leftmost :: Rectangle -> Rectangle -> (Rectangle, Rectangle) +def sort_leftmost(x, y): + if left(x) <= left(y): + return x, y + else: + return y, x + + +# rectify :: Int -> Int -> Int -> Int -> Rectify +def rectify(top=None, bottom=None, left=None, right=None): + assert top >= bottom + assert left <= right + return { + 'left_x': left, + 'bottom_y': bottom, + 'width': right - left, + 'height': top - bottom, + } + + +# empty_rect :: Rectangle +def empty_rect(): + return { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + + +# find_rectangular_overlap :: Rectangle -> Rectangle -> Maybe(Rectangle) +def find_rectangular_overlap(x, y): + ha, hb = sort_highest(x, y) + la, lb = sort_leftmost(x, y) + + if bottom(hb) <= top(hb) <= bottom(ha) <= top(ha): + return empty_rect() + + if left(la) <= right(la) <= left(lb) <= right(lb): + return empty_rect() + + # We should have an intersection here. + verts = [bottom(ha), top(ha), bottom(hb), top(hb)] + verts.sort() + horzs = [left(la), right(la), left(lb), right(lb)] + horzs.sort() + return rectify(top=verts[2], + bottom=verts[1], + left=horzs[1], + right=horzs[2]) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_overlap_along_both_axes(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 6, + 'height': 3, + } + rect2 = { + 'left_x': 5, + 'bottom_y': 2, + 'width': 3, + 'height': 6, + } + expected = { + 'left_x': 5, + 'bottom_y': 2, + 'width': 2, + 'height': 2, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_one_rectangle_inside_another(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 6, + 'height': 6, + } + rect2 = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_both_rectangles_the_same(self): + rect1 = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + rect2 = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + expected = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_on_horizontal_edge(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 2, + 'width': 3, + 'height': 4, + } + rect2 = { + 'left_x': 2, + 'bottom_y': 6, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_on_vertical_edge(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 2, + 'width': 3, + 'height': 4, + } + rect2 = { + 'left_x': 4, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_at_a_corner(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 2, + 'height': 2, + } + rect2 = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_no_overlap(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 2, + 'height': 2, + } + rect2 = { + 'left_x': 4, + 'bottom_y': 6, + 'width': 3, + 'height': 6, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |