5 kyu

Count Rectangles

26ecolban
Description
Loading description...
Puzzles
Algorithms
View
AllIssues1Questions2SuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • dfhwze Avatar

    This kata makes 0% sense to me

    From sample tests: How can there be points in the results that are not given in the input?

    test.assert_equals(count_rects([
         (1, 0), (4, 0),
         (1, 1), (3, 1), (9, 1),
         (0, 2), (4, 2), (5, 2), (6, 2), (9, 2),
         (2, 3), (5, 3), 
         (1, 4), (2, 4), (4, 4), (5, 4), (9, 4)]), 12)
         # The 12 rectangles are:
         # ((0, 1), (0, 0), (1, 0), (1, 1))
         # ((0, 2), (0, 0), (1, 0), (1, 2))
         ...

    From description: how are these even rectangles?

    The vertices of these rectangles are:

((3, 1), (1, 0), (0, 2), (2, 3))
((0, 2), (1, 0), (5, 2), (4, 4))
...
    • ecolban Avatar

      The 12 rectangles should have been:

      ((3, 1), (1, 0), (0, 2), (2, 3))
((4, 0), (1, 0), (1, 4), (4, 4))
((4, 0), (0, 2), (1, 4), (5, 2))
((1, 0), (0, 2), (4, 4), (5, 2))
((3, 1), (4, 0), (6, 2), (5, 3))
((1, 1), (4, 0), (5, 3), (2, 4))
((1, 1), (9, 1), (9, 4), (1, 4))
((3, 1), (5, 2), (4, 4), (2, 3))
((5, 2), (4, 2), (4, 4), (5, 4))
((9, 2), (4, 2), (4, 4), (9, 4))
((9, 2), (5, 2), (5, 4), (9, 4))
((2, 3), (5, 3), (5, 4), (2, 4))

      I'll update.

      The vertices are given in adjancency order, starting at any vertice and moving in either direction (i.e., clockwise or counter-clockwise). E.g.,

                     (2, 1)
        (0, 2)------->(2, 3)
          |             |
  (1, -2) |             | (1, -2)
          V    (2, 1)   V
        (1, 0)------->(3, 1)

      Using the dot-product, you can verify that the sides are perpendicular.

    • dfhwze Avatar

      ok looks good now

  • FArekkusu Avatar
     
    test.assert_equals(count_rects([
(0, 1), (0, 2), 
(1, 3), 
(2, 1), (2, 3), (2, 4), 
(3, 1), (3, 3), 
(4, 1), (4, 4), 
(5, 0), (5, 3), (5, 4), 
(7, 0), (7, 1), 
(8, 3), 
(9, 0), (9, 3)]), 5)

    Could you list these rectangles? There're definitely 4 with their sides parallel to X/Y axes but I have no idea where the last one is.

    • Blind4Basics Avatar

      (5,0), (3,3), (7,1), (5,4)

      Question marked resolved by Blind4Basics 5 years ago
    • ecolban Avatar

      I agree, it's hard to identify the rectangles. The 5 rectangles are:

      {((2, 1), (2, 4), (4, 4), (4, 1)),
 ((2, 3), (2, 1), (3, 1), (3, 3)),
 ((4, 1), (5, 4), (8, 3), (7, 0)),
 ((2, 3), (2, 4), (5, 4), (5, 3)),
 ((5, 0), (5, 3), (9, 3), (9, 0))}

      Have added this info to the Examples Tests.

  • Blind4Basics Avatar

    out of curiosity, could you tell what is the required time complexity?

  • Unnamed Avatar
     
        bag = defaultdict(int)
NameError: name 'defaultdict' is not defined