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

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

Written by on 25 February 2012

Topics: Project Euler

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.

11 Comments For This Post I'd Love to Hear Yours!

  1. Luis Rivera says:

    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.

  2. Kristian says:

    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

  3. Luis Rivera says:

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

  4. David says:

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

  5. Kristian says:

    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.

  6. John says:

    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

  7. Kristian says:

    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.

  8. Jean-Marie Hachey says:

    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

  9. LouWeed says:

    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.

  10. Kristian says:

    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.

  11. Gary Walker says:

    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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.