Circular Rotation

I was toying with the apparently innocent problem of rotating an array (shifting and wrapping around) through a given parameter. Coming up with an efficient algorithm is fairly elusive. On our journey, we will unravel some interesting connections to fields that will surprise you.

To shift an array a single cell to the right, we start at the last element, swap with the element before it, repeat at the previous element. The last element that we started with will continuously be moved, while each swap places another element into its correct place. To finish rotating an array of n elements, the algorithm needs n-1 swaps. This algorithm works for both directions (shifting left or right) since it always places one of the elements into its correct position (for positive and negative directions).

A naive approach to rotating an array through a distance entails repeating the corresponding "directional single-step rotate" k times. However, we're talking about shifting a million elements a thousand times. Hardly does a billion (which is just above the number of swaps needed) sound efficient (it's not).

Let's take the following array and shift its elements to the right. We got to try to fit the preceding single step solution to it:

0 1 2 3 4 5

We notice that 5 must swap with 1 first.

0 5 2 3 4 1

Then, 1 must swap with 3.

0 5 2 1 4 3

Starting again at 4, it must swap with 0.

4 5 2 1 0 3

Then, 2 must swap with 0.

4 5 0 1 2 3

Magically we have the array we have been seeking.

Let's look at it in another way:

Swapping at k-elements apart grouped the array into two sub arrays:

0 2 4 and 1 3 5

Doing a single rotate on each of these arrays:

4 0 2 and 5 1 3

Merging back these arrays into their respective places,

4 5 0 1 2 3,

gets us the resulting array that we desire.

The sub array subdivision should only be conceptual, not an actual memory operation. The resulting algorithm needs to swap only as many elements as there are in the initial array.

The remaining question is:

How do we count the sub arrays that result from this subdivision by the parameter k.

The simple solution would be to start at 0, move k elements at a time, and count how many times you need to move to return to 0. This count is the number of elements in each sub array. Divide the total number of elements in the array by that, and you have the number of groups. This solution however lacks performance. A million elements with a single step will require a million moves.

What we know is (given the size of array is n, and the step size is k)

- (rule1) if k is 1, the whole array is a single group (which reverts the rotation into the first single step version)

- (rule2) if k is either 0 or n, then there are n groups (the importance of this is not in 0 rotations but rather to resolve the following point after recursion)

- (rule3) if neither above rule apply, the problem is equivalent to finding the number of subarrays in an array of size k, and a step size that is k less the remainder of the division of n by k = (k - (n%k)).

The reason for that is that after a full movement sequence around the array, the cursor will be at (k-(n%k)). After another full rotation starting from that index (rather than 0) we expect to stop at the next increment of this value. Disregarding the values outside (0..k], we have another rotation grouping problem embedded in the first.

Let's take an example. n = 14, and k = 4.

Let's go through the movement sequence first. [0], 4, 8, 12, [2], 6, 10, [0]. I highlighted my sub problem points. The movement distance is 2, and the sub problem array size is 4. 4 from the previous step size, and 4-(14%4) = 4-2 = 2.

Applying the algorithm on (4, 2) we end with (2, 2). We know from (rule2) that the number of groups is 2. This makes sense as we need to apply the single shift algorithm, 4 steps at a time, once for the even numbers, and once for the odd numbers.

Let's try it with n=10 and k=3. 0, 3, 6, 9, 2, 5, 8, 1, 4, 7, 0. Apparently, all numbers are listed.

Let's apply the subgroup counting algorithm: (n, k) -> (10, 3) -> (3, 2) -> (2, 1) -> (1, 1). We have a single group. 3 steps don't divide 10 elements into unrelated groups.

Note: I also found out that the subgroup counting algorithm is equivalent to the GCD algorithm. Apparently, (n,k)->(k, n%k) is equivalent to the above formulation. The explanation within the above framework would be that, just before we finish a run around our array, our index is n-n%k which is equivalent to -n%k modula n. The sign does not matter for grouping by movement, so we can drop the minus to get our new array size and step size (n, k) -> (k, n%k).

Programming, passion, games, math and graphics - The roots

Here's a topic close to my heart!
There's a new kid on the block, and he was asking what programming language to start with (and he's only 14). I wish I could have tutored my kid self, or got tutored, and for that I own it to other junior citizens.

So here's how I got into game programming and loving it, and what happened along the road for me.

The way I personally did it was: I probably started at your age or a bit older with VB6 to make some kick-ass games. I had some fun with 3dsmax before that thinking that it was the game engine for a little while.
Soon, in everything I read about games, C++ was mentioned, and little was talked about for VB6. Before I knew it, after reading tons without noticing, I knew alot about C++, from a far point of view. (Story of my life.) I got a book, C++ for programmers, and read it painstakingly. It's hard and assumes you have some logical rigor.. a single sentence can sometimes be quite dense and decisive to your understanding. Then I got the Frank D. Luna Introduction to Game Programming using DirectX 9. It only teaches how to create the graphics and some very basic frame animations, but it was enough to keep me busy beside schoolwork for months. I was also getting serious about math, learning all about linear algebra and how it applies to 3D, collisions, physics and so on.
I didn't study CS at university since it was my hobby and I didn't want to ruin it. Started with CCE and ended with a Mechatronics degree instead which deals a lot with mechanical things that may change your way of thinking and perhaps make you more lucrative as a game developer. I got a job and forgot all about game programming dreams as I was having next to no time for it.
When I got a job, my graphics programming shined through and I appeared as a magician to other team members since what I was doing was weird and usually unheard of. The language of choice for games and graphics on the web was/is Actionscript. I started with the third version which has a very low code-to-result delay. Compare with C# or Java for example, and you'll know how far it makes the programmer feel on the edge of the monitor.

Oh, but remember this, yes! the best programming language ever is C++. This should be read as, I am an old hag who loves his old tools, oh and tomorrow is my 23rd birthday! You'll grow into C++, or hopefully when you get to age to get a job, no one will be using C++ when there's a much better and newer blockbuster language that depends on reading your eye blinks to read your mind. (Unfortunately, people would still implement that in C++).