Counting Rectangles

A geometric counting problem based strongly on a single mathematical pattern. My solution ended up needing some arbitrary loop limits, which tends to suggest a lapse in understanding. The completed script finished in 2.1 seconds without optimizations.

As the joys of Project Euler are in the struggle and completion, this post, and others, will intentionally be left with incomplete solutions.

The Problem

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.

The objective here is two-fold. First, we must find the number of rectangles that exist within a rectangle of a given size. Secondly, we must use that method to determine the rectangle that contains as close to 2,000,000 rectangles as possible.

Approach

Initially, we must define an equation or algorithm to calculate interior rectangles given a width-height dimension pair. The problem example uses a 3 x 2 rectangle, and it illustrates the patterns reasonably well.

As with many patterns, it is at times easier to identify trends using abstractions instead of the actual numbers themselves. For this, we will refer to the dimensions of the outer rectangle as rows and cols. We will refer to the dimensions of the interior rectangles as width (w) and height (h).

The example demonstrates that a 3 x 2 rectangle contains the following rectangles:

1 x 1 => 6
2 x 1 => 4
3 x 1 => 2
2 x 1 => 3
2 x 2 => 2
3 x 2 => 1

Now, with any interior rectangle, we start by placing it at the top left point, and shift it right until its right side touches the edge of the outer rectangle. We then multiply by the other dimension to count the total of that interior rectangle.

1 x 1 => 6 => rows * cols
2 x 1 => 4 => rows * 2
3 x 1 => 2 => rows * 1
2 x 1 => 3 => cols * 2
2 x 2 => 2 => 2
3 x 2 => 1 => 1

This works for the rectangles of width = 1 or height = 1, but the others fail such a pattern. The reason is in the prior description:

we start by placing it at the top left point, and shift it right until its right side touches the edge of the outer rectangle

This means the width (and height) will play a roll in our equation. The number of times we can shift a rectangle to the right could be expressed as shifts = cols - rectangle_width. Since we also need to count the initial interior location, we could say rectangles_on_this_row = 1 + cols - width. It stands the exact same could be said for vertical rectangles if we swap the variables.

1 x 1 => 6 => rows * (1 + cols - width)
2 x 1 => 4 => rows * (1 + cols - width)
3 x 1 => 2 => rows * (1 + cols - width)
2 x 1 => 3 => cols * (1 + rows - height)
2 x 2 => 2 => 2
3 x 2 => 1 => 1

We have now shown the relationship works in both directions. All that is left to our method is to put both pieces together, accounting for interior rectangles of arbitrary width or height.

1 x 1 => 6 => (1 + rows - width) * (1 + cols - width)
2 x 1 => 4 => (1 + rows - width) * (1 + cols - width)
3 x 1 => 2 => (1 + rows - width) * (1 + cols - width)
2 x 1 => 3 => (1 + cols - width) * (1 + rows - height)
2 x 2 => 2 => (1 + cols - width) * (1 + rows - height)
3 x 2 => 1 => (1 + cols - width) * (1 + rows - height)

Thus, we are left with rectangles = (1 + cols - width) * (1 + rows - height) for each interior rectangle with sides less than or equal to the original bounding rectangle.

Arbitrary Loop Limits

When working to find the actual problem solution without a reasonable mathematical bounds, i was left to place arbitrary bounds on my row and column loops. Luckily, the equations i use to calculate interior rectangles ran fast enough that brute forcing was sufficient.

There are some short-circuit cases the diligent can place in the loops, should that interest you.