Simultaneous equations and algorithms: Finding the “best fit” of cells in a grid

I got pinged by my colleague @j_f_green this morning with the following message: “Hey Clare. Hope all is well. Was wondering if I could be cheeky and get your input on a (small) thing I’m trying to solve? I am searching for an elegant solution and I’m starting to suspect the answer may involve maths.”

…and of course I was instantly interested.

The problem

It turned out to be a relatively simple problem, depending on your point of view. If I say “GCSE-level simultaneous equations” your reaction will tell you whether that’s simple for you or not (for people not in theUK, GCSEs are the exams our pupils take when they are 16 years old).

Here is the problem: We want to discover two whole numbers (aka positive integers) that will give us the height and width of a grid in cells, given the following constraints:

We have a number, let’s call it capacity, which represents the minimum number of cells to fill the grid. We want at least that many cells. We’re happy if we have more, but not if we have fewer.
We also have another number, we’ll call it aspectRatio, which is the aspect ratio of the grid. This is the relationship between height and width. So for instance, if the aspect ratio is 2:1, that means the width is twice the height (it’s twice as wide as it is high). To reduce that to a single number, aspectRatio is 2.

width = 2 * height = aspectRatio * height

(aspectRatio will often be a decimal or a fraction, so for instance if width is half height, aspectRatio is 0.5, or if the ratio is 2:3 then aspectRatio = 2/3 = 0.66, and width = 0.66 * height)

A concrete example

Here is a concrete example: Let’s say we have a grid that is twice as wide as it is high, so aspectRatio = 2. Let’s also say that our capacity is 200: We want to fit at least 200 cells into this space. I’ve deliberately chosen an easy example, and the answer in this case would be a width of 20 and a height of 10:

◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️

Apologies if that’s making your eyes hurt. Is it making your eyes hurt? It’s making my eyes hurt. I’ll try and make a better diagram later. It’s not even got the correct aspect ratio on the page…

If you enjoy attacking maths problems, look away now. Have a go at solving it before you read on. You may come up with a better solution anyway.

So how do we compute the answer?

One way would be a loop. Here is some code that would do the job:

var capacity = 1000;
var aspectRatio = 1000 / 800 = 1.25;

int width = 0;
int height = 0;

while (width * height < capacity)
{
height += 1;
width = RoundToNearestInteger(height * aspectRatio);
}

Assert.AreEqual(height, 29);
Assert.AreEqual(width, 36);

Here we have a grid that has at least 1000 cells:
36 * 29 = 1044

It has roughly the correct aspect ratio:
36 / 29 = 1.24
1000 / 800 = 1.25

The problem with this is that it does not scale well. The higher the numbers, the longer the loop. But fear not – maths to the rescue.

A simple use case

Let’s start with a simple use case: imagine the aspect ratio is 2:1, and the width is twice the height. Also let’s say we’re trying to fit 200 pixels into the space.

Let’s call width and height x and y. So:

x * y = 200

and

x = 2 * y = 2y

If x = 2y then x * y is the same as 2y * y, which is 2y²:

2y² = 200

y² = 100

y = 10

x = 20 (because it’s 2y)

A generalised solution

The first block above gives us our two simultaneous equations.

We can generalise the same approach for all numbers. Let’s call the capacity a, and the ratio b. Using our equations from above :

x * y = a

and

x = b * y

These are our simultaneous equations. Using the same logic as above, we substitute y for x and end up with:

by² = a

Which means that

y² = a/b

and

y = sqrt(a/b)

(where “sqrt” is square root).

Then once you’ve calculated y, you can calculate x:

x = b * y

The only missing piece of the puzzle is that we are dealing with inequality, not equality. So really it’s this:

y >= sqrt(a/b)

This just means that once you get a result, you round it up to the nearest integer. Same applies to the final substitution : if b * y is not a whole number, then round it up.

When you calculate b * y, you should use y BEFORE rounding.

So to finish, let’s stop being mathsy and start being softwarey. Let’s give our variables some meaningful names:

height >= sqrt(capacity / aspectRatio)

width = aspectRatio * height

If we test it with the example we used in the loop above, where aspectRatio = 1.25 and capacity = 1000, we get the same results:

height >= 28.28 [= sqrt(1000 / 1.25)]

width = 36 [= RoundUp(1.25 * height)]

So height = 29, width = 36, aspectRatio = 36 / 29 = 1.24, num cells = 29 * 36 = 1044

Now we can finish with some code:

var heightUnrounded = SquareRoot(capacity / aspectRatio);

var height = RoundUp(heightUnrounded);

var width = RoundUp(heightUnrounded * aspectRatio);

Compared to the loop we started with, this scales brilliantly. It doesn’t matter how big the numbers are, the compute time is basically the same. It has a constant computational complexity, otherwise known as O(1)*. The solution above using a loop gets slower and slower depending on how big the numbers are. It has a computational complexity of O(n), so it’s not as good.

Hopefully that makes sense and I didn’t over-simplify. All feedback welcome.

* I couldn’t remember how to express O(1) so I initially guessed at O(k), because I was thinking of k as a constant. Sadly I was wrong, because I rather like the thumbs-up “Ok” concept.

In Simple Terms