How Bresenham Got Five Programmers Into Two Cars?

Introduction

So I’m 43 and the other night I finally asked myself the all- important question. How to get five programmers into two cars?

Well… you invite three to the first car and two to the second car. That is not so difficult. The formula for calculating how many programmers you can put to one car is:

But what if the objective was optimal performance? What if we wanted the algorithm to work on old 8-bit systems that allowed us only limited tools: (positive) integer numbers, addition, and comparison. There is no floating point, no negative integer numbers, and no division. Now how do you get five programmers into two cars?

Using the Code

I invented a tiny algorithm just for that. I call this trick the weighted iterative division. And it is designed to work when there are more programmers than cars.

int N = 5; // Programmers.
int M = 2; // Cars.

// Weighted sums. 
int sumN = M;
int sumM = N;

int programmer = 1;
int car = 1;
while (programmer <= N)
{
    Console.WriteLine("Put programmer {0} to car {1}.", programmer, car);
    if (sumN >= sumM) { sumM += N; car++; }
    sumN += M;
    programmer++;
}

What we are doing here is very basic math. If floating point was allowed, we would multiply programmer with M/N (i.e. 0.4). Let us write this as an equation:

By multiplying both sides of the equation with N, we get:

Now the job of our algorithm is to iteratively keep this equation in balance. As soon as the left side is smaller, we add a new car (add N to the left side). And every time we add a new programmer, we add M to the right side. Here is how algorithm evolves 5 programmers.

How does it work:

We already discovered that left side of the equation is N * car and right side of the equation is M * programmer. Left side counts cars and right side counts programmers. Hence 5 + 5 on the left side means 2 * car weight (5). And 2 + 2 + 2 on the right side means 3 * programmer weight (2). 

You initially put one programmer 1 in car 1. Next you put programmer 2 into car 1. The right side is now 2 + 2 which is 2 * programmer weight. The equation is still not balanced. So you put programmer 3 into car 1. Right side is now 3 * programmer weight (2 + 2 + 2 = 6). It is now larger then left side. The equation is balanced. So in the next step you add a car on the left side (hence 5 + 5 which is 2 * car weight). You proceed by adding the fourth and the fifth programmer to car 2. Last step has equation in balance. 

Let us optimize this just a bit more to come to an interesting conclusion. If we allow using negative integer numbers, then instead of calculating left and right side of the equation, we can just calculate the difference between them.

int N = 5; // Programmers.
int M = 2; // Cars.
int D = M - N;
int programmer = 1;
int car = 1;
while (programmer <= N)
{
    Console.WriteLine("Put programmer {0} to car {1}.", programmer, car);
    if (D > 0) { D -= N; car++; }
    D += M;
    programmer++;
}

Now the algorithm starts to look familiar. It is, indeed, a close relative of Bresenham line drawing algorithm where D is our error and we’re iteratively correcting it.

Points of Interest

This method was originally developed for mapping line length N pixels to line length M pixels for projective transformations. It was inspired by the Quadrilateral Distortion article. The logic can be used in any situation where a very fast mapping from N items to M items is required. It is equivalent to drawing a bresenham line where dx=N and dy=M.