Project Euler 85: Investigating the number of rectangles in a rectangular grid

And now for something completely different.. or maybe as we will see later Problem 85 of Project Euler offers us a new problem where we can use the same ideas as for the solution to a previous problem. To lets start out with the problem text:

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

A nice and short problem text. I have found two possible solutions for the problem, one using brute force and the other applying some combinatorics to find an analytical solution to the number of rectangles that we have for a given size.

Brute force solution

The brute force solution is pretty easy to derive.  If the grid is X long and Y high, we want to find rectangles with sides which are 1≤x≤X and 1≤y≤Y.

In case are looking for rectangles of size MxN there will be (X-M+1)*(Y-N+1)  possible ways to place that rectangles.  You can see that in the drawing. If we are looking for rectangles of size 1×1 we can place it as in the figure in the upper left corner. Then we can move it twice  to the right (giving us three options) or one down (giving us two options). Giving us a total of 6 cases if you want to cover all.

The corresponding code can be made with as this C# implementation.

int closestarearects = 0;
int closestarea = 0;
int target = 2000000;

for (int x = 1; x < 2000; x++) {
    for (int y = x; y < 2000; y++) {
        int rects = rectangles(x,y);
         if (Math.Abs(closestarearects - target)
            > Math.Abs(rects - target)) {
            closestarea = x * y;
            closestarearects = rects;
        }
        if (rects > target) break;
    }
}

where the rectangles are calculated as

int rectangles(int x, int y) {
    int rects = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            rects += (x - i) * (y - j);
        }
    }
    return rects;
}

The reason I run up to 2000 is that a 2000×1 grid yields 2001000 rectangles, so there is no need to search higher values.
The solution gives us.

Grid area  with closest to 2.000.000 rectangles is 2772
Solution took 13960,604 ms

Not a very good solution.

Combinatorics

The alternative I have found to the brute force solution is to use combinatorics. A solutions that was inspired by Problem 15, but only slightly.

When we want to figure out how many rectangles we can make in a grid which is XxY we want to figure out how many ways we can place two lines horizontally and two lines vertically. There are X+1 choices on the width and Y+1 in the height since there are X+1 lines to make the X boxes.

That gives us the formula

Since the binomial coefficient tells us exactly how many ways we can choose the two lines from a total of X+1. We can calculate the binomial coefficient as

Which in our case gives us

In the denominator we have 2! = 2 and then we have a (X-1)!. All these terms cancel out the the corresponding terms of (X+1)! which leaves us with (X+1)X in the numerator. So the formula is

Just finding an analytical solution should already according to my profiling give us a significant speedup. However, let us turn the notch a bit more.

Let us start with a grid of size x=2000 and y=1 and calculate the number of rectangles. If the number of rectangles is above the target value of 2.000.000 we will decrease x until we find a grid area below the target value. And then increase the y value until we are above the target value again. This means we only need to search grids which are in the vicinity of the correct size.  We can stop once y>x since that is the same grid sizes just rotated 90 degrees.

The code I wrote is  as follows

int error = int.MaxValue;
int closestarea = 0;
int target = 2000000;

int x = 2000;
int y = 1;

while (x >= y) {
    int rects = x * (x + 1) * y * (y + 1) / 4;

    if (error > Math.Abs(rects - target)) {
        closestarea = x * y;
        error = Math.Abs(rects - target);
    }

    if (rects > target)
        x--;
    else
        y++;
}

a piece of code that runs in

Grid area with closest to 2.000.000 rectangles is 2772
Solution took 0,0123 ms

Just a tad faster than the brute force approach.

Wrapping up

I just presented you with two solutions, one of them getting the job done, the other being beautiful while doing it. You can download both solutions here.

Björn Utecht shared the photo in this blog post under the creative commons license, which allowed me to borrow it.