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.

Posted by Kristian

16 comments

Luis Rivera

Kristian, you can optimise even more your code, by not recomputing the sumatorial eachtime, but doing it successively

#include <stdio.h>
#define abs(x) ((x)<0 ? -(x) : (x))

int main()
{
	const int toplim = 2000000;
	int err=toplim,area=0;
	int sx = 1999000, sy = 1;
	int y = 2, x = 1999;
	while(x>=y)
	{
		int sumsum = sx*sy;
		if(err > abs(sumsum-toplim)){ 
		err = abs(sumsum-toplim);
		area=x*y;
		}
		if(sumsum > toplim)
			sx-=x--;
		else
			sy+=++y;
	}
	printf("\nArea: %d",area);
}

Regards, chubakueno.

Hi Luis

Thanks for pointing that out. I decided to stop when I went below the 1ms level from being far beyond the 1 minute level. But you are right.

/Kristian

Luis Rivera

correction: “int y = 2” should be “int y = 1”, but for some weird reason it worked both ways.
chubakueno.

I don’t understand why the grid 1 x 2 000 000 isn’t “closer” to having 2 000 000 rectangles.

If you take a 1×3 block and name the blocks 1,2 and 3 you will have the following rectangles
1
2
3
1,2
2,3
1,2,3

So that is 6 not 3. The same thing applies for a 1×2000 block, which ends up with a much larger number rectangles than just the 2000 individual rectangles.

Hi, thanks for these nice pages!
I’m wondering how you can be sure that the process of decreasing x and incrementing y brings you to the optimal solution? Thanks

Hi John

Thanks for the compliment. Yes it will do, because every time we end up going through all the possible solutions in this way.

Jean-Marie Hachey

Table 1
Differences with targets for some estimated rectangles inserted in specific rectangular grid areas.
[Re: Project Euler Problem 85:
Project Euler 85: Investigating the number of rectangles in a rectangular grid]

http://img4.hostingpics.net/pics/441997pe85tab1.jpg

___

Comments on results:
Option for the calculation: Algo (1) based on combinatorics.
Function (2): (Application from the above article): Combinatorics method
Number of rectangles in an (b x h) grid: combinatorics formula (2):
[(b+1)*b *(h+1)*h] / 4
The results in Table 1 show that for [int target] between 1 and 2 000 000, the differences between the number of rectangles [int target] (i.e. INPUT) and the number of rectangles estimated via formula (2) for a range of values between 1 and 2 000 000 do not exceed 10. Exceptions: 100 000 and 500 000.
Prime factors for [int target] 100 000 and 500 000 respectively: 588=2x2x3x7x7; 1154=2×577.
(Restrictions on the interpretation of the results of Table 1: limited list of data).

___

Sources:
1) Project Euler 85
Kristian’s algorithm (Combinatorics version)
http://www.mathblog.dk/files/euler/Problem85.cs
2) Combinatorics formula (Project Euler 85)
Number of rectangles in (b x h) grid:
[(b+1)*b *(h+1)*h] / 4
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007

I never tried the brute force for this one, I started with pen & paper, figuring all the math out myself so I would understand it better. Came up with pretty much the same solution as your second one except for one small detail….

When I increment y, I set x to be sqrt(4*target/(y*y+y)). Using this, I get the same answer by only testing only 159 combinations of x & y. Here’s why the shortcut works:
target (t) = x(x+1)y(y+1)/4
4t = (x^2 + x)(y^2 + y)
x^2 + x = 4t/(y^2 + y)
Now assuming x is always a positive integer, we can simplify this:
x^2 < 4t/(y^2 + y)
x < sqrt(4t/(y^2 + y))
Since we're decrementing x as we go, it makes sense to start at a number we know must be higher than the ideal x, but is still pretty close.

To be on the safe side, you should then round x up to the nearest whole. Not sure if this is necessary though, I haven't given it much thought. I think they should have made the target for this problem a lot higher, since most computers these days could just brute force a solution.

You are right as far as I can see. Since we are working with a quadratic equation the solution should be close to a square to maximize the number. However, I could not come up with the argumentation for that. So thank you.

I took a different approach. To me the solutions was to recognize that counting the total number of rectangles was the product of 2 triangle numbers. e.g., for the 2×3 case, T(2) x T(3) => 3 * 6 => 18

Given that I have a height of 1, 2, 3, etc. I can compute the best corresponding length directly using T(x) x T(y) = 2000000 but T(x) is x * (x+1) / 2, thus I have a simply quadratic equation in x

x**2 + x – (2000000 – T(y))

So, I solve for x and then try floor(x) and ceil(x) for the closest possible integral solutions (x) for a given value of y.

I terminate the loop once x < y.

I would post code, but could not figure out how to post Python cleanly last time I tried.

Hi, lets say we have grid 3 x 2 (m x n):

C1 C2 C3
C4 C5 C6

My goal is to write algorithm wchich output me all possibles rectangles in this grid.
C1,C2,C3,C4,C5,C6…C1C2,C2C3,C4C5,C5C6….C1C4…C1C2C4C5.

Please can you post me solution?

There was a similar question in topcoder. I dont understand the math behind , can you explain it clearly step by step plz. I have understood the above problem clearly.

The problem was

Given the width and height of a rectangular grid, return the total number of rectangles (NOT counting squares) that can be found on this grid.

For example, width = 3, height = 3 (see diagram below):

” I dono how to draw image, but i have link to the image”

http://math.stackexchange.com/questions/1280411/a-question-about-2-times-3-rectangles

S Muralidharan

How about counting rectangles whose sides are not aligned horizontally or vertically? For example in 3 x 3 square there are 4 such rectangles.

What I have found is that the closest result would be a grid 3 x 816 or am I wrong?
it results in 2000016.
Can anyone explain this?

Carl J Appellof

Mateo ran into the same solution I first found, and I misinterpreted the problem in the same way at first. This is the solution closest ** GREATER THAN OR EQUAL ** to 2000000. But the problem statement says “closest” and doesn’t specify whether the difference can be negative or positive. The solution for 36 x 77 has a total number of squares of 1999998, which differs from the target by only 2, so it is the winner.
Like others, I used the quadratic formula to calculate the number of columns for a given number of rows in order to be closest to 2000000. Fun.

Leave a Reply