Breaking it down with algoritms I: the round table

Breaking it down with algoritms I:

This series is about looking at a problem and solutions in javascript. We will have a look at which algorithms offer a solution and how we can arrive at them or at least understand how they work. I'll be showing code and will try to break down the code to a mental model of how it works. I have met a few people who have trouble coming to a correct algorithm and this is almost always because they can't break down the solution in to steps - they just don't know how to think about the problem. Hopefully this will help those who need it and give a little more insight in to the wonderful world of algorithms for the rest of us.

This will not be your algorithms 101 course where we look at well known algorithms, instead we will be trying to build new ones from scratch (and if we arrive at well proven algorithms that can be found in a textbook then we've done our job!)

The circular table

The problem goes like this:

There are 100 people sat at a circular table. You go around the table asking every second person to leave (starting by asking the guy at seat 1 to leave) until there is one person left. Which seat is left?

You can see the solutions at: http://jsperf.com/chair-ring/7

Solution 1: using an array

Usually when I hear a problem like this I try to put everyone in an array. I can see that I'm removing every second person so I can do a filter on the array to remove every second person (I'm starting at 1 which is index 0 so I can just remove all the even indexes). Using a filter like this makes things easier for us because we can forget about all the operations in the middle. What we care about now is when we start the second pass through which chair do we start at? In this case we'll ask 99 to leave keep 100 and then start again at 2.

If we think about the end we can see there are two cases, one where we remove the last guy and one where we remove the second last guy and this will tell us whether to start filtering at the first chair or the second chair. This all depends on whether the length of the array is even or odd. We can see that when we get an odd length we will start removing from the second chair in the array.

If we think about this a bit more though it's not as simple as whether the previous length was even or odd, if we have 4 chairs (it often helps to think of simple cases) and we start at the second chair then wil will still be on the second chair in the next round, so odd numbers change which chair we start at.

Now we can start coding:

// setup array
var chairArr = [];
for (var i = 1; i <= 100; i++)
     chairArr.push(i);

// whether to remove odd or even chairs
var odd = 0;

// while there are still chairs
while (chairArr.length > 1) {

     // remember the initial length
     var last = chairArr.length;

     // filter odd or even chairs
     chairArr = chairArr.filter(function (val, ind) {
          return (ind + odd) % 2
     });

     // used to decide odd or even chairs next round
     odd += last;
}

// return the answer
chairArr[0];

First thing is first - we need an array of 100 chairs which is easily done.
We also know that we're either starting at the first or second chair on each pass through so we'll want to remember that.
We then need to keep making passes until we are left with our final chair.
The next is perhaps the most important line although it looks really easy - we need to remember whether the last length of the array was even or odd so we'll save this.
Then comes the filtering, this is easier than it looks, I just need to modify the index by adding on an odd number if the previous length was odd and then see if it is divisible by 2.

Last thing I need to do is keep whether I'm starting at the first or second chair for the next pass. Since I'm using a modulus to check later I don't need this as a 0 or 1, and odd or even number will do so I just have to add on the length. Adding on an odd number will make that number odd and keep it there until the next odd number is added which will represent the switch of starting on the first or second chair when an odd length is found. Don't worry if you think you won't write it exactly this way the first time - I certainly didn't. It took a couple of iterations to realize I could just do this instead. Originally I was using a boolean for true or false about whether to start at the first chair. It might make more sense if you write something like this instead:

if(last%2==1)
    odd = !odd;

so if the last length was odd then change whether to start at the odd or even chair.

This solution is fine and works but it's not the best way to go. Trying to keep in mind whether we change the next start chair slows us down but the biggest slow down is the filter method. Filtering an array is slow and may not be native on older browsers (for those you can use a shim https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/filter).

Let's try something a little different:

Solution 2: use a custom data structure

We're talking about a ring of seats right? so why not just build one. All we need is 100 objects which hold their seat number and a reference to the next seat. Then all we have to do is go around and remove each seat in between.

A quick way to remove a seat is to just change the reference to the next seat to point to the seat past that. It's like if we had everyone pointing to the person next to them then went around telling each person to point to the person past the next person and moving along to the person they're now pointing at and then doing the same thing again until it was just one person pointing at themselves. There isn't any filtering of arrays so it should be faster as we're only updating references and moving along them.

// setup chair ring
var start = {num:1};
var one = start;
for(var i = 2; i <= 100; i++) {
        var temp = {num:i};
        start.next = temp;
        start = temp;   
}
start.next = one;
one = null;

// go around removing chairs
while(start.next != start) {
        start.next = start.next.next;
        start = start.next;
}
start.num;

The above should do that for us. This is the answer that you should probably give in an interview and is probably the closest to how we would solve it in real life. But when I did this I couldn't help the feeling it could be done a bit quicker. Changing pointers isn't too slow but there will be some garbage collection when the chairs are removed, also we have to setup Objects for each chair. So let's go back to our array solution and see if we can't make it a bit better.

Solution 3: Return of the array

An array is more like a line of chairs. What if we told every second person to go sit in a new line of chairs, then we go through that line and do the same. By doing this we can copy each number in the array rather than filtering (which is expensive). Now if we run through this we can also see that when we get to the end of the first line we just go straight to the start of the next one. Now here is the mental leap, we can forget about whether the last length was odd or even by just treating the start of the next line of chairs as if it is joined to the current line. All we need to do is keep telling every person to go sit at the end of the line until there is no-one else to skip. Let's see some code:

// setup array
var chairArr = [];
for (var i = 1; i <= 100; i++)
      chairArr.push(i);

// copy every second element to the end of the array
for (i = 1; i < chairArr.length; i+=2)
     chairArr.push(chairArr[i]);

// return the answer
chairArr.pop();

Nice and simple. It's made a lot easier by the fact that you can change the length of arrays - there would be a couple of hoops to jump through if this was Java for instance - but we don't have to worry about that. All we're doing is adding every second element to the end until we reach the end and grabbing that last answer. I would say this is the best solution for flexibility (it's easy to modify for every third or two of every three) code size and ease of understanding. But we want to go FAST. The big thing to see is that it's every second chair which should tell you something being a computer guy. Binary.

*EDIT*

The above will take about 2N space with the array (actually 2N-2). But we can do better. We can re-use the space of the array that we have already gone past. In the above solution we basically have 2 counts, the first is the count that goes every second chair the second is the count for where we copy that seat number in to. Because we were just placing it at the end of the array we didn't really need to keep that number around as a push() will place the number in to the correct chair. Instead we're going to take that push() and change it to overwrite numbers at the start of the array. This shouldn't be a problem because our chair skipping index won't go past the chair placing index.

One thing we need to change though is the for loop end condition. Before we were just going until we hit the chairArr.length, in other words we kept going until we hit our last chair placing index. We could do this, or there are two other options. We could go until we hit the same chair twice in a row (so something like for (...; chairArr[chairSkipIndex] != chairArr[chairSkipIndex - 2]; ...) or we can work out the index to stop at. I'm going to use the latter one, I know that the array will expand to 2N-2 and where we should start at the chairArr.length (N) I'm going to start at the beginning of the array so I only need to keep going until the chair placing index is at N-2. Here is the algorithm:

// setup array
var length = 100;
var chairArr = [];
for (var i = 1; i <= length; i++)
    chairArr.push(i);

// copy every second element to the end of the array
for (i = 0; i < chairArr.length - 2; i++) {
    chairArr[i] = chairArr[(i * 2 + 1) % length];
}

// return the answer
chairArr[i - 1];

We setup the array like normal, and keep going until the chair placing index is at N-2. The important part is the next part. We can work out what our chair skipping index is from the index (it'll be the index * 2 and add one because array indices start at 0). The next thing there is called the modulo operator (or you may think of it as the remainder).

Most people when starting coding with loops over an array will start after a for loop with a condition like:

if(i > arr.length)
    i = i - arr.length;

This allows the index to iterate past the end of the array and come back from the beginning. This is exactly the same as adding on the modulo operator.

And there we have it, instead of push we just copy the chair number back in to the array and iterate until we hit out end condition, we're done! it works exactly the same as above but will re-use the space in the array we were just leaving behind.

Solution 4: Math

First of all thanks to imbcmdth for this solution.

This is going to be the hardest to wrap your head around but bear with me. Instead of actually moving around seats we're just going to keep tabs on which seat we start on because once we get to the length of 1 the seat we start on will be the only seat left. Next we have to realize that on every pass we're going to remove every 2^N chair. So the first round we're moving every 2nd chair, then every 4th then every 8th and so on.

So what we need to do is move the start chair by that amount on every pass. So lets start with the chair at 2. After the first pass we've removed every 2nd chair and we'll remove chair number 2 so we will have the start as being 4 (that's 2^1 chairs along from the previous start chair). The next time it's be 8 (that's 2^2 chairs along from the previous start chair). You'll notice we're actually keeping track of the NEXT start chair rather than the one we were just on.

Now we will remove the start chair if we go through an even number of chairs, else we'll skip that one and remove the second. So it's important to only add on the 2^N when we will remove an even number. We can get whether we're going through an odd or even number of chairs by counting the number of times we can go 2^N from out starting chair.

The last thing we need to know is how many times we have to do this loop. We need to know how high N can go in 2^N until we reach 100. So we do the reverse of 2^N which is a logarithm (who says you don't need math to program?).

// number of chairs
var totalLength = 100;

// number of iterations
var numIterations = Math.round(Math.log(totalLength) / Math.LN2);

// start at the second chair
var startingPoint = 2;
var currentLength = totalLength;

// magic happens
for(var count = 1; count < numIterations; count++) {
     startingPoint += ((currentLength + 1) & 1) << count;
     currentLength = (totalLength - startingPoint) >> count;
}

// answer
startingPoint;

Don't worry if you don't understand this straight away - it contains a lot optimizations using binary calculation. Here is an easier to understand version that was whittled away until you get what you see above.

var totalLength = 10000;
var powerOfTwo = 2;
var startingPoint = 2;
var currentLength = totalLength;

while(currentLength > 1) {
     if(currentLength % 2 === 0) {
          // currentLength was even change starting point
          startingPoint += powerOfTwo;
     }
     currentLength = Math.floor((totalLength - startingPoint) / powerOfTwo);
     powerOfTwo *= 2;
}

// answer
console.log(startingPoint);

In this version you can see that the first thing we do in a loop is change the starting point, which lets you know that it's the previous length of the array that matters. The current length is then calculated as how many times 2^N it takes to get to the end of the array from the starting point.

If we have a look at the optimized version we can see the logic is still there, the &1 is basically the same as %2 which gives us 0 or 1 and << count means times 2^N (powerOfTwo). Because we're doing binary we just use << and >> instead of * and /

Solution 5: the formula

Thanks go to Medieval_Peasant for this one

Up until now we've been running a loop. Usually when solving a problem there will be a loop somewhere, but every once in a while it can be solved with pure mathematics. We already know now that 2^N is special. What happens when the number of chairs are 2^N? well one method I like is to try it out on smaller numbers. Try running through at 4, 8 & 16. You'll notice that the chair that is left is always the last chair. So what happens if we add in a chair, so for 2^N+1 chairs? (try 5 or 9) you'll notice that the start chair is pushed to 2. Try it out for 2^N + 2. You'll see it is pushed to 4. If we keep going we can see that every new chair we push on to the table will move the chair we end up at by 2.

This means we want to calculate the largest 2^N number that can fit in our length, we can then find out how many chairs we have added to that, then multiply that by 2 and we get our answer.

One small adjustment we'll make though is that if 2^N fits exactly in to the number of chairs then we'll actually take the 2^(N-1). This will make the math a little easier as otherwise we'd have 0 left over chairs and a start chair of 0 wouldn't make sense (in fact it means take the chair before the first one which would be the length). Below I did this by taking the log of length - 1, so if the length was 64 we'd actually try for 63 and round down to 32.

Here are the components broken up:

// find the largest 2^N that fits in to length (minus one)
var largest2n = Math.pow( 2, ( Math.floor( Math.log( length - 1 ) / Math.LN2 ) ) )

// get the left over chairs
var leftover = length - largest2n

// multiply to get the answer
var answer = seriesIndex * 2;

and here is the formula in all it's glory:

2 * (length - Math.pow(2, (Math.floor(Math.log(length - 1) / Math.LN2))));

Conclusion

So what we can take from this is that if we visualize how we would solve a problem in real life we can put that in to an algorithm. We can start off with a couple of premises (like start with an array and iterate, or if the number 2 is prominent there is probably a solution using binary) to come to other solutions that may not occur to us naturally. Most important is to iterate on a solution. We might iterate over a couple of solutions in our head and whether they are wrong or right they're all important as thinking about each will help you drill down to the answer

Which solution is the best? Well the math solution is definitely the cleverest and fastest, but it is also the least flexible and hardest to maintain. I'd use it if performance was the key concern and there was no chance of change. Otherwise I would stick with the third solution as it's easier to maintain, less code and fast enough (it may be 30-40x slower but for a small problem it's only milliseconds and the user won't see the difference). If you're in an interview though I'd go for the second solution as it's easiest for the interviewer to understand, is quick to come up with and you won't need to iterate on it much to optimize.

as a bonus if you go to jsperf I've also put in an example with regex, but this should be avoided in practice