Sunday, October 24, 2010

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).

Wednesday, October 13, 2010

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++).

Tuesday, August 17, 2010

Search for Numbers

So I am not posting regularly, I suck. Moving on...
Some long while ago, while sharing puzzles with friends on, I posted a mathematical puzzle that I didn't know the answer for.

Writing quiz problems is not easy, especially when there are new concepts to explain.

The explanation I made on the forum was kind of screwed, and I will have to describe it again.
There are n employees. They have numbers on their back from 1 till n. There is a bowl that has n papers, also with numbers from 1 to n. Each employee comes in after the other, to pick a number from bowl. An employee may pick himself.
Starting with any employee, checking the piece of paper and reading the number, and going to the employee whose number appears on that piece of paper and repeating, you will be stuck in a loop of k employees, where k is less than or equal to n. Whenever a bowl is consumed (a paper is picked by each employee), there will be a set of loops, each of different size.
You are required, given n, to determine first the possible loops and their sizes. Next you have to determine the probability of that partitioning of n into loops from a random set of draws from the bowl.

For n = 4, the result is:

1 - A single loop with 4 employees; probability: 3!/4!

2 - A loop with 3 employees, and an employee who drew his own number; probability: 8/4!
The single employee can be anyone of the four employees. For the loop of three, the first employee can pick between two other employees (2 options). The picked employee must pick the one that the first left out (no choice). The last one must pick the first one (no choice). As such, there are 4*2! ways.

3 - A loop with 2 employees, and another with 2 employees; probability: 3/4!
Two employees selected from four. That's 4!/2!/2!. Two employees can only be ordered in one way to make a loop of two. The left two employees have only one way to become a loop of two. It would appear that the probability should be 6/4!. You'd have to remember that the loops are symmetric, so a divide by two is in order.

4 - A loop with 2 employees, and two cases of an employee picking his own number; probability: 6/4!

5 - 4 cases of an employee picking his own number; probability: 1/4!

The probabilities sum up to 4!/4! = 1. (This was at first a pointer that there was a problem with my calculations for case 2).

So how did I learn that my calculations are not fubar? Taking this series we just calculated: 6, 8, 3, 6, 1. Searching on google for the phrase: "search for number series". I found this place. Plugging the series into it gave this result. Scrolling a little bit down, inside the "Triangle of multinomial coefficients read by rows", I found a link that read something relevant to what I was solving: Cycle classes of permutation. And there was it, I was reassured I wasn't doing this alone, and that my math is not fubar. I liked the brevity of the explanation, and the mathematical rigor, though I couldn't have used it to explain the problem to the layman, or at least make it more relevant to them.

Sunday, June 27, 2010

Write Once, run anywhere.. Or is it?

While reading this blog post I couldn't help but have a lot of ideas I needed to express. I will be formatting this post however in a way that the reader doesn't have to read both posts if they're short on time (though I would like it if you actually do read my friend's blog).

Should a product be tightly controlled to so that its quality is ensured? Could additional features and flexibilities be an obstacle for a product to fulfill its true value?

The issue here is with Java. Java is supposed to be the silver bullet of operating system-programming language decoupling.

Java is bytecode compiled. When on the actual target machine, it is probable that the JVM will do a JIT compilati0n. JIT is common among code that is bytecode compiled and is generally a reply to being less on performance on average than natively compiled code (C++ to x86 machine code for example). In some situations, JIT will produce machine code that is actually faster than code that had been remotely compiled and linked to encompass a vast array of machines.

So far so good. Java looks like a C++ killer, even on performance! A lot of people believed so as well. I am not sure however where things went wrong and Java scaled back to becoming yet another solution in the programmer's arsenal (or an additional item to the poor programmers confusion).

Almost with any program that has to do things that are not quite standard, the OS will allow you to do things that the general high level language doesn't have semantics for. Comes in JNI. A native interface for Java. It allows you to use Java to access OS specifics. Mind you, I didn't say use OS specifics from Java since once you're in that land, you've went out the boundaries of the design guidelines of Java. The write once, run anywhere gets broken.

Does this mean that Java is less or more portable. Is this flexibility akin to worsen Java's reputation?

I believe not. A tool must be open for use as the user wishes. While giving guidelines of recommended use for a tool, you should also think about it as such, not as a rule book.

To me, in conclusion as a reply to Tech Thoughts blog: In this contained context I elaborated in, I believe Java fulfills its promise as a cross platform tool (for where a JVM has been written at least) and allows the user to take a decision and break that advantage for the sake of a heartfelt use.

Thursday, June 24, 2010

SQL Trees

Represeting tree structures in SQL is fun.
While direct modeling techniques in object oriented wisdom dictates the use of collections to references of children or references to parents, the story while doing some SQL could be quite different.

A naive implementation would have this shape: {id, parent_id}. parent_id maybe nullable or not. The non nullable approach would designate an id for the root virtual node, probably set as 0.

Another implementation would go the encapsulation route. The principle is extremely simple, but first here's the shape of a record: {id, lft, rgt}, where lft and rgt represent left and right respectively. How this record could represent relationships you may be keen to ask? The rules are very simple:

For all a and b we have the following rules:
* a.lft belongs to the interval ]b.lft, b.rgt[ <=> a is a child of b
* a.lft < b.rgt => a.rgt < b.rgt

The first rule defines the ancestry relationship.
The second rule defines validity of the data.

All operations on this table must respect these propositions.

The operation specification is actually very straightforward and intuitive once you accept the above rules and internalize them.

Insertion into a node is about pushing elements after that node to make space inside the node for the new one.

A data base may start with one single node as follows:
{0, 1, 2} ---remember the tuple representation mentioned above.
Inserting a new node under no other would result with:
{0, 1, 2}
{1, 3, 4}
Inserting another node under 0 would push the right property of node 0, in addition to the properties of all the following nodes (here only one with id=1)
{0, 1, 4}
{1, 5, 6}
{2, 2, 3}

This is of course not my ingenious invention. I read about it somewhere on the web, but ultimately the source I relied on to get the foundation concrete was Joe Celko. Look the name up, I recommend his books - condensed amounts of wisdom.

Wednesday, May 26, 2010


This post is rather on the very short side. Creating water should be easy, and it is. The basic idea is to have a bunch of sine waves moving in the same direction at different frequencies and velocities. Modulating their amplitude will give you all the water goodness you require.

Check out the results:

Tuesday, May 25, 2010

Loading Queue in Actionscript

There comes a time when in an actionscript project you have to load a bunch of assets and have them all be ready before calling the setup function that operates on those loaded assets.
The solution for this recurring problem should be standardized, and separated into its own class rather than polluting classes concerned with GUI events or with server-side interaction.
We are aiming for a highly reusable and hence simple bulk loader. Regular usage is listed in the following:
  • Pass an array of the requests to the bulk loader class
  • Listen for when the list has completed
  • Listen for when an item has been completed
  • Get the number of remaining items
Here's a simple implementation to this problem. Please report any misbehavior using comments.
package {
    import flash.display.Loader;
    public class BulkLoader extends EventDispatcher{
        private var requests:Vector.<URLRequest>;
        private var current:Loader;
        public function BulkLoader(requests:Vector.<URLRequest>) {
            this.requests = requests;
        public function start():void {
            if (requests.length == 0return;
            var req:URLRequest = requests.shift();
            current = new Loader();
            current.contentLoaderInfo.addEventListener(Event.COMPLETE, _currentComplete);
        public function stop():void {
            if (current == nullreturn;
            current = null;
        private function _currentComplete(e:Event):void {
            current.removeEventListener(Event.COMPLETE, _currentComplete);
            dispatchEvent(new Event(Event.CHANGE));
            if (requests.length == 0)
                dispatchEvent(new Event(Event.COMPLETE));

Sunday, April 25, 2010

Space Triangle

Well I got really bored today, and thought I could give back a bit to the community. The end result is a ship (triangle) that floats across a stage. The user controls the ship using keyboard arrow keys. The animation is frame independent. That means I explore a bit about frame time calculations, which in code translate into a variable declaration and three lines of code.

To cut the chase short, here's what you can do with 1 line on top of a hundred in pure Actionscript 3 programming.

Check the source code here.

This triangle is a repeated theme in my experimental work, and has been so since I was back in High School. You can imagine that the math involved is really simple arithmetic. That's the elegance that I appreciate for an introduction.

I will not break the habit of not writing code in this blog, and instead I'll explain the core concepts behind this basic program. For a technical undertaking, the code is extremely self explanatory and is very brief.

The game, as I said before, is simply a little triangle that's controllable using the arrow keys. It slides across the screen.

The states I keep watching are the position and rotation of the triangle (which I get for free after creating a sprite). I also create three variables to keep an eye on velocity on the x-axis (sideways), velocity on y-axis (vertically), and rotation.

Three event listeners are in action, two to watch key strokes (and save them into three additional state variables), and one to be called on each frame (the whole simulation driver).

Beyond that, it's a matter of figuring out how to update velocity and rotational velocity based on the keystrokes, then how to update position and rotation based on the velocity variables. There's a piece of trigonometry on conversion from traingle angle into an acceleration vector.

One more piece is left missing, which is the link between the velocity variables, and the positional ones. This piece is the delta time between frames. To keep the motion frame-independent (as in, the same across all computers regardless of processing power), I calculate the time in milliseconds it takes from each frame to the next one. Although it's quite an extrapolation in terms of numerical precision, it does it's job, and the motion is basically frame independent.

Monday, April 19, 2010


While the other posts have been about the development of arithma, this post is about the development of arithma.

The latest and most prevalent fact about me is simply that I am freelancing as a developer and more so as a solution provider. It has been about 6 months of ups and downs... an emotional, and stressful roller-coaster. A lot of people enjoy these, and a lot of people end up with a yellow face and with lots of goo on the ground (when it comes to roller coasters, am personally more on the goo-side).

Yet in real life, the gut is strong, and to answer the question in my head: "So how was life for you, punk?"... I'd simply have to say: "It was such a ride! Again."... I prefer this answer to "Well it was really safe, I felt comfortable". Hardly "yay".

For a more objective comparison between being employed, and starting up, here's a [hardly exhaustive] list of some things I'd like you to know:
  • Don't expect to become rich right away
  • Don't expect to make more financially than by being employed right away
  • Don't expect to work less than when being employed
  • Expect a lot more to learn than just being pigeon holed into your tasks while employed
  • Expect a lot more freedom in what you're able to work on and explore
  • Expect a lot more satisfaction and attachment to the products you are working on
  • Expect a lot more tense relation with your work
  • Expect a lot more ability to work on the techniques you deliver your own work, and ability to set your schedule experimentally, and being able to actually achieve an improvement (rather than being dictated to a scrawl in updates to higher management and overhead)
  • Expect to have a whole more lot of fun
This is simply a fun game, but not for the faint of heart.
I encourage everyone able to start up, to do so... There's a lot more to life than sitting behind a desk and waiting for a paycheck.

Tuesday, March 30, 2010


Swarms really fascinate me. You see pigeons forming patterns. Fish schools swim in cohesive patterns. There are some types of birds, in massive numbers, that appear like swirling smoke from a distance. Each one of these spectacles is an amazing sight.
The underpinning of the behavior is surprisingly simple.
One of the models is depicted in this boids. It uses three simple rules to create a more wholistic interesting behavior. The rules, in brief, are: Seperation, Cohesion, Alignment.

However this is not the only way swarms can be created. In my model, based on basic particle physics (nothing fancy), I have Attraction, Seperation, Rotation.

The area of effect for attraction is the greatest one, however its maximum amplitude is much less than that of the seperation effect. This creates an interesting interaction pattern that includes soft collision.
The area of effect for rotation has been tweaked (and I have been very lucky with the results) and is in practice half way between the seperation and attraction.

Each of these effects act in a pair wise manner. The end result is that the particles group into clusters and rotate approximately around each center of a cluster that are rotating counter-clockwise. On occasion, the clusters will exchange particles, creating a channel. In other cases, a big cluster will seperate into two clusters while a channel thins down.

Sunday, March 14, 2010

Raymarching - Part 0

raymarching minimum distance - part 0 - wonderfl build flash online

I have been contemplating on the idea of a ray tracing application created within actionscript. My first experiment in this field can be found here.
The first time I have been exposed to such graphics algorithm was about 2 years ago through a post about a GPU technique used in raymarching, geometry representation, and shading a scene - a high performance demo scene entry, if I recall correctly. Needless to say, their results were much more impressive than mine.

The first image to come out of the application is really disturbing as I can't really wrap my head around what is being generated - I can create a simple sphere and totally know what's happening, but put in a few coordinate wrapping transformations and everything goes out of hand.
The camera is animated so that the true 3D nature of the algorithm can be appreciated.
Normal light calculations are next to come.

In the upcoming posts about this technique I will be trying to control the geometry to match the vision I have in my head, and I will explain more about this raymarching if it is the case I am doing something out of the normal.

Thursday, March 11, 2010

Flash Clock

So today was a very bad migraine day yet somehow I managed to fork out my old circular menu and create a nifty little clock that I wish I could be hanging on my wall.

There's nothing really technical about the change from the one code to the other, other than copy-pasting a block of code and changing it two times to cater for minutes and seconds. Then I added the time driven code, and that was it.

Who says cool has to be tiresome!

Tuesday, March 9, 2010

Circular Menu

So part of my actionscript continuous practice routine, this little mind child is born.
The basic idea behind it is that the selected button will take up the space of two items, and get centered in the middle of it. The other items will leave that space and get squeezed against each other.
Inside the code, you'll see a lot of the modulus (%) operators. This is ordinary of code handling such cyclic objects.
As for seeing the magic trick, you should move your pointer in a cyclic manner on the buttons. You'll see the whole circle moving, but in effect after a full cycle, it's still in its place.
You have to see the bigger picture so that it can be explained. It lies in the fact that the average of all rotations will stay constant no matter how you move the mouse.
I posted the code and the flash here again.
Till the next brief blog entry.

Monday, March 8, 2010

Mechanical Gears

As a mechanical engineer, I must have some fetish for gears. And I do.
I wrote up a simple example on how simplistic gears can be drawn in actionscript code and posted it on wonderfl. You can check it out here.
The basic idea is to iterate in a loop around the points in a polar manner and provide values for the distance from the center. Coupled with some array data storing for a single gear tooth, and some sin/cos mapping from polar coordinates into cartesian ones, we drew a gear.

Draw two gears, give them compliant tooth to radius ratios and we simply get two meshing gears (if placed at the correct distance).
This example shows the reason why the gears are shaped a little beveled into the inside; The ones I drew are not beveled and if you look closely, they do have an intersection area that would generate a lot of wear, tear, and clicking (if not roaring) noises in a real life situation. Granted there are many standards into creating gears; none of which I'll explore in this blog.

Monday, February 22, 2010

Dynamic Sound in Actionscript

Sounds in actionscript, especially the dynamically generated are some sort of black art that few get to master. I had to sample dynamically some sounds due to some self-imposed strict file size constraints.
You can check the final product here:

The basic idea is that a sound object, aside from loading the usual mp3 file, uses a call back function to sample the wavelet and fill a buffer of at least 2048 samples. This requires FP10 as far. You can check it out here

In the game
Apart from the reverberating engine before full-thrust takes over, you'll be able to tune in to two sounds, a splash when the ship hits the water and a jet sound when the ship goes super sonic.

Instead of copy pasting less sensible code lines into this blog, I edited the sound generating functions so that they can be sensible to create an intelligible graph.

Waveforms: Click to view details

Noise source on
Splash source on

Sunday, January 31, 2010

Minesweeper Solved

Back in 2006, summer, Lebanon faced a nationwide attack on infrastructure. Life as we knew it was crippled.
We were mostly away from direct fire, but still went away from our house to our aunt's. We played minesweeper to keep entertained. The game became competitive until my finger started exhibiting pain due to the extremely fast clicking. An algorithm was needed.
Over the course of the week, I continuously thought about solving the game automatically and be crowned king of the hill.

The algorithm was a success: it worked and it was such a pleasant experience to create.
I've uploaded a presentation and the project source files up so that you can check it out.

Monday, January 18, 2010

Introduction and Kick Start

Hello there. Thanks for dropping by my new conceived blog.
I am known in the forums as arithma, my real name is Mohammad Skafi.

I have a Mechatronics engineering BSc degree under my belt. After being an employee for a little bit more than a year I decided it was not worth it, and went on to found

My first official product is Jizi Interiors. Things of note about this website is the optimized swf file size (76KB at time of writing). There are many loading issues and file management details pertaining to Actionscript and Flash that we will be sure to share.