Coding Challenge — Rectangle Rotation

Here’s a cool coding challenge I came across last week. When I first encountered it, I was stumped. It took me a few days of thinking about the problem, approaching it in different ways, and recognizing patterns to come up with a solution.

The Problem Statement

A rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes.

How many points with integer coordinates are located inside the given rectangle (including on its sides)?

Example

For a = 6 and b = 4, the output should be
rectangleRotation(a, b) = 23.

The following picture illustrates the example, and the 23 points are marked green:

image and problem from codefights.com

My Solution

I’ll show you my code first and then explain the approach.

def rectangleRotation(a, b)
    aHalfBisect = (a/Math.sqrt(2))/2
    bHalfBisect = (b/Math.sqrt(2))/2
    rect1 = [aHalfBisect.floor*2 + 1, bHalfBisect.floor*2 + 1]
    rect2 = []
    
    if aHalfBisect - aHalfBisect.floor < 0.5 
        rect2[0] = rect1[0] - 1
    else 
        rect2[0] = rect1[0] + 1
    end 
    
    
    if bHalfBisect - bHalfBisect.floor < 0.5 
        rect2[1] = rect1[1] - 1
    else 
        rect2[1] = rect1[1] + 1
    end 
    
    rect1.inject(:*) + rect2.inject(:*)
end

note: remember the inverse square root that appears in the first two lines, there will be a post about that coming in the future ;)

Pattern Recognition
The key to my solution was recognizing a pattern in the number of dots in each ‘row’ and ‘column’. A dot is a coordinate point that lies within the boundaries of the rectangle. The rows can be thought of as the dots connected by the lines extending from the left to the right side of the rectangle which are parallel to the top and bottom of the rectangle. Using the example rectangle above, there are 5 rows of dots and 9 columns of dots. There are actually two different types of rows and two types of columns. There are rows of 5 dots and rows of 4 dots. There are columns of 3 dots and columns of 2 dots. These two sets of rows and columns can be thought of as two separate rectangles. There is one rectangle with sides of 5 dots and 3 dots and one rectangle with sides of 4 dots and 2 dots.

The number of dots within both of these rectangles is essentially the sum of the rectangles ‘areas’. 5x3 + 4x2 = 23. This is the answer we seek! The trick is defining how to find these two rectangles for any input.

Rectangle of Dots — One
I devised a strange algorithm to define the two rectangles of dots that lie within the given rectangle. The development of this algorithm began by recognizing that there is a line segment that bisects the given rectangle that lies on the line y=x, and therefore passes through coordinate points. Relative to the rectangle, this line segment can be thought of as a horizontal bisect. Similarly, a vertical bisect exists that lies on the line y=-x. Finding the number of points that each of these bisects passes through would provide a way to define the first rectangle of dots. The number of points each bisect passes through is found by:
1. Finding the length of half the bisect
2. Rounding this length down to a whole number
3. Doubling the result and adding one (essentially to include the dot at the origin)

These calculations yield the number of dots in the rows and columns of the first rectangle. Translated into Ruby, these steps look like this:

aHalfBisect = (a/Math.sqrt(2))/2
bHalfBisect = (b/Math.sqrt(2))/2
rect1 = [aHalfBisect.floor*2 + 1, bHalfBisect.floor*2 + 1]

Rectangle of Dots — Two
The next step is to define the second rectangle of dots. The solution lies in the relationship between the diagonals of two coordinate points, hereby referred to as a coordinate diagonal. Note that the length of such a diagonal is the square root of 2. The intersection of the horizontal bisect and a side of the given rectangle always lies on the line y=x between two coordinate points. Since the bisect and rectangle side are orthogonal, it follows that if their intersection occurs at a point whose distance is at least half the length of a coordinate diagonal, then the rows of dots in the second rectangle have one more dot than the rows in the first rectangle. If the intersection occurs at a point whose distance is less than half the length of a coordinate diagonal, then the rows of dots in the second rectangle have one less dot than the rows in first rectangle.

The distance along the coordinate diagonal at which the bisect and rectangle side intersect can be found by:
1. Finding the length of half of the bisect
2. Selecting only the decimal portion of this length
Then by checking if this decimal is less than 0.5, the number of dots in the rows of the second rectangle can be determined. Similarly the vertical bisect can be used to find the number of dots in the columns of the second rectangle. Translated into Ruby, these steps (for the horizontal bisect) look like this:

if aHalfBisect - aHalfBisect.floor < 0.5 
    rect2[0] = rect1[0] - 1
else 
    rect2[0] = rect1[0] + 1
end 

Finally, the number of dots in each rectangle is computed and added together to find the total number of dots.

rect1.inject(:*) + rect2.inject(:*)

Here is the full code again:

def rectangleRotation(a, b)
    aHalfBisect = (a/Math.sqrt(2))/2
    bHalfBisect = (b/Math.sqrt(2))/2
    rect1 = [aHalfBisect.floor*2 + 1, bHalfBisect.floor*2 + 1]
    rect2 = []
    
    if aHalfBisect - aHalfBisect.floor < 0.5 
        rect2[0] = rect1[0] - 1
    else 
        rect2[0] = rect1[0] + 1
    end 
    
    
    if bHalfBisect - bHalfBisect.floor < 0.5 
        rect2[1] = rect1[1] - 1
    else 
        rect2[1] = rect1[1] + 1
    end 
    
    rect1.inject(:*) + rect2.inject(:*)
end

If you have made it this far then you are no doubt a nerd, and you are my type of people! Welcome to my blog and thanks for reading.