Why Things Go Wrong: A Simple Programming Problem

Much of programming is writing code with an obvious solution, it’s being a code monkey. You lay things out, you move them around, you wire it up, but you don’t really need to stop and think. I’d estimate that everyone is about equally good at this. But some of the work is also spent solving problems you’ve never seen before. This is where bugs are introduced, bad decisions are made, schedules are thrown out, and things go wrong. These problems are the really defining part of being a great programmer.

I think understanding the hidden complexites of seemingly minor problems is important in understanding programmers.  Studies conducted starting as far back as the 60’s have shown that most all developers will complete the same problem in a similar amount of time. In fact the best developers are about 2 to 3 times faster than average and the worst are 2 to 3 times slower.  But the best developers will have about 1/10 as many bugs in their code as their average counterparts. In fact, when a restraint was placed on the allowed number of bugs, the best developers were 20 times faster than the average developer.

But why is that?  Well, it’s hard to explain without giving an example, so I’d like to present a case study of one such problem. I picked a problem that was easy to understand and small in scope. It’s a real problem I came across and I remember it well because I thought it’d make a great interview question, if only it was even smaller in scope.

(On a very interesting tangent, the same studies have shown that the best developers make 30 to 50 percent more money than the average. Keep that in mind when interviewing and hiring, if quality is a concern, you get 20 times the speed for 1.5 times the cost. But the business sense of your typical developer is a topic for another day.)

Trying to solve this problem for yourself is probably the best way to fully understand the thesis of this article. I encourage you to work on it yourself before reading my solution.  If you’re not a programmer, you can solve it with pen and paper, that’s how I did it.

So without further ado, I give you my case study of great programming.

For full disclosure, this problem was solved by another programmer, let’s call him Adam. He’s one of those great programmer types I mentioned above. I actually solved it and then got a merge conflict because Adam had already done the work. I very much enjoyed reading his solution to the problem, as it was very different from mine yet equally good.  So, sadly, the below code never made it to production, as often happens, but I’m glad it can find some use here.

The problem:
You have an unknown number of video streams (we’ll use red boxes instead) that each have the same unknown width and height (aspect ratio). They’re in a rectangular container that also has an unknown width and height. You want to scale the video streams to maximize the surface area they take up in the container.

For instance, here’s a red box in a container:

The Solution:
Let’s dive right in. We’ll be using everyone’s favorite programming language, Javascript.

First off, let’s define the variables we’re working with:

W, H: the width and height of the container
w, h: the starting width and height of a red box
n: the number of red boxes
m: the multiplier (the amount to scale the size of the red box by)

and, to keep the javascript police off my back, to transform my pseudocode into real code, let’s do this:

var floor = Math.floor;

Ok, so our function will have known constants for W, H, w, h, and n. They’re unknown right now, but they will be the input. What we really want to solve for is m, the amount to scale each stream by.

what does m equal?

Well, we know for a given m:

floor(H/(h*m)) * floor(W/(w*m)) is the maximum number of red boxes we can fit inside the container

So we want the largest m that satisfies:

floor(H/(h*m)) * floor(W/(w*m)) >= n

Now we’re getting somewhere. But as you can see, there are an infinite number of m that will satisfy:

floor(H/(h*m)) * floor(W/(w*m)) = x, for any constant x.

For example, let’s say H = W = h = w = 1. And x is 1. Then:

floor(1/m) * floor(1/m) = 1

Which means m has an infinite set of solutions, namely, (1/2, 1], that is, all real numbers from 1/2 to 1, including 1 but not including 1/2.

This seems like a troubling problem. An infinite set of solutions is not what a programmer yielding loops as a tool wants to hear. But if you consider it for a moment, you’ll realize we don’t care what m is exactly. In fact, we just want the value in the set with the largest m, since they produce the same x anyway. In fact we know that:

floor(H/(h*m)) is always an integer, and,
floor(W/(w*m)) is always an integer.

So what we really want to solve is all of the possible x values regardless of m, take the smallest x that’s greater than or equal to n, and then take the largest m for the given range of m that yields the accepted solution.

I’m throwing a lot of math around, so let me break it down a bit. Think of w and h not as sides of a rectangle, but as a grid, or a spreadsheet, starting at the top left corner of the container. Each row is h units tall and each column is w units wide. So as you multiply w and h by m, or scale the size of the columns and rows proportionally, a different number of rectangles in your grid will fit inside the container. If you can fit 9 red boxes inside, then there are an infinite combination of different sizes of w and h that will also result in 9 red boxes. But we don’t have to care about that, we only have to care about about the largest size that can fit 9 red boxes inside. And the largest size of w and h that accomplishes that will always occur when we stretch the grid until a certain number of columns fit perfectly in the container OR a certain number of rows fit perfectly.

So now we have a set of all possible solutions for x. It is the union of solving for when H/(h*m) equals an integer or when W/(w*m) equals an integer. Or, the following union:

k*floor(k*(W*h)/(H*w))   U   k*floor(k*(H*w)/(W*h))

You might notice that the solutions on either side of the union are not mutually exclusive. We will need to find the value for each set that’s the smallest value greater than or equal to n, and then we will need to take the one with the largest m.

That’s it, that’s the solution. We need to solve for both sets and then take the largest of the two m values. I can’t see how to simplify it further. If you can, please write a comment below, and I’ll update the post.

Ok, so let’s code it up.

First, let’s define the structure of a container and stream object that our function will take as input:

var container = {
width: 0,
height: 0
};
var stream = {
count: 1,
width: 0,
height: 0
};

And now let’s solve for m.

var layoutStreams = function(container, stream){
var calculateMultiplier = function(__container, __stream){
// get best solution when grid extends to right side of container
var rowSolution;
var k = 1;
while (!rowSolution) {
var nBoxes = k * Math.floor(( k * __container.width * __stream.height )/( __container.height * __stream.width ));
if (__stream.count <= nBoxes) {
rowSolution = __container.height / (__stream.height * k);
}
++k;
}
return rowSolution;
};
var invertContainer = {
width: container.height,
height: container.width
};
var invertStream = {
count: stream.count,
width: stream.height,
height: stream.width
};
var rowSolution = calculateMultiplier(container, stream);
var colSolution = calculateMultiplier(invertContainer, invertStream);
var m = (colSolution > rowSolution) ? colSolution : rowSolution;
// ------------------------------------------------
// now use m to layout streams
// ------------------------------------------------
};

How will you layout your streams? Well, I’ll leave that as an exercise for you, but I’ll provide the most primitive of solutions, which is to start in the top left and go left to right, top to bottom.

..................
// ------------------------------------------------
// now use m to layout streams
// ------------------------------------------------
var streamDim = {
width: Math.floor(stream.width * m),
height: Math.floor(stream.height * m)
};
var grid = {
cols: Math.floor(container.width / streamDim.width),
rows: Math.floor(container.height / streamDim.height)
};
var eleContainer = <your container>
var streams = [];
for (var i=0; i<stream.count; ++i){
streams[i] = document.createElement("div");
eleContainer.appendChild(streams[i]);
streams[i].style.width = streamDim.width;
streams[i].style.height = streamDim.height;
streams[i].style.position = "absolute";
// primitive layout strategy
streams[i].style.top = (Math.floor(i / grid.cols)) * (streamDim.height) + "px";
streams[i].style.left = (i % grid.cols) * (streamDim.width) + "px";
}
...................................

And that’s it. Here’s a demo you can play with, and you can grab the source code right off of this page if you’d like.  (if the iframe doesn’t load, you can go to page directly).  Or grab the demo code from github.

Please send hate mail to my secretary, ptubig@grio.com. Any other comments can be sent to me, griddle@grio.com.