A few weeks ago, I remember solving a Project Euler question that particularly intrigued me. I saw problems similar to this when I was in middle school, but never recalled myself successfully solving something them. For reference, the problem was Project Euler 85, counting the number of rectangles in a rectangular grid.

But when I attempted this particular problem? It took me fewer than thirty minutes to think of a solution and code it. So what changed?

I believe it’s been my new algorithmic approach to solving problems.

I fully admit that I’m a brute-force, “try-them-all” kind of person. Whenever I see a problem of the form “How many X satisfy the property Y,” my first instinct is to go through all possible candidates of X and store a count of how many satisfy Y. I first approached this problem by remembering what I did years ago — count rectangles by hand. The questions I experienced back then were much easier in that it was feasible, though time consuming, to actually count all the possible rectangles. Of course, it’s so easy to miss or double-count a few rectangles here and there that I was bound to be off in my final answer.

So I realized I needed a formulaic, or algorithmic, approach to this problem. There had to be some formula out there that could take as input just the dimensions of the largest rectangle, and use that information to compute the total amount of rectangles contained within it.

There was. I started by counting rectangles by hand for rectangles of a small scope (e.g. a 2×3 one), and then testing my conclusions on other small rectangles. This was my algorithm:

total = 0
for i: 1 to n, inclusive
for j: 1 to m, inclusive
total += (n-i+1)*(m-j+1)