Korn Shell

So I was looking at the Facebook programming puzzles the other day. For those of you who haven't stumbled upon them, the puzzles are meant to be completed by would-be applicants in one or more of the suggested languages (those used by Facebook, according another article). In most puzzles, additional solutions in other languages are encouraged, and in some puzzles partial or probabilistic solutions are also accepted.

One problem I thought was interesting was the Korn Shell problem. Go ahead and read it now, otherwise this post is pretty pointless :-P


When I first read the puzzle, I don't think I quite understood it, so here's a quick example. Say we're working in a six letter alphabet (A-F). The keyboard could've been swapped in many ways, but I'll give 2 of them:

Keyboard 1

A->F
B->E
C->B
D->D
E->C
F->A

Keyboard 2

A->F
B->E
C->D
D->C
E->B
F->A

A -> F means that typing A on the keyboard yields F on the screen, as you would expect. So if we take the word "FACE", we get these iterations

Keyboard 1	Keyboard 2
AFBC	AFDB
FAEB	FACE
AFCE
FABC
AFEB
FACE

So the first keyboard yields many more iterations than the second, with a total of 6. In fact, in an alphabet of 6, the maximum number of iterations you can have for any word is 6, but I'm getting ahead of myself.

The first thing you may notice is that a keyboard is really just a permutation. One thing you might quickly notice after that is, for any given keyboard, repeats of a character are irrelevant. Finally, even thought the characters of a word matter in a given keyboard, there is always another keyboard that will take the same number of steps for a transformed version of the word. For instance, since there are keyboards that transform "FACE" in six and two steps, there are also keyboards that transform "AFCE" and "DBCA" in six and two steps. Thus, for any given word, the only determining factor is the number of unique characters.

Now let's look at the keyboards more carefully. In mathematics, the permutation group S_n is the... group of all permutations of n elements. These elements are often written as disjoint cycles. For instance, (a b c)(d e) is a permutation with two disjoint cycles. The first cycle imposes that a -> b, b -> c, and c -> a, and the second that d -> e and e -> d. If there are other elements are . So, our keyboards can be written as (A F)(B E C) and (A F)(B E)(C D).

For any k-cycle, it takes k iterations to get back to the starting point. Of course, we also restart after 2k iterations, or 3k, or j*k for that matter. So, if we have a permutation made up of m cycles, of sizes k₁ .. k_m, then the permutation will take L = lcm(k₁, .., k_m) iterations to restart, where lcm is the least common multiple.

So, our keyboard problem is strictly a number theory problem! For a given number of unique characters C, we need to find m, and k₁, ..., k_m > 0 so that L_C is maximized, subject to some constraints. Specifically, we can't have more cycles than we have unique letters, but multiple letters can belong to the same cycle, so m <= C. Also, if our keyboard only has K letters, k₁ + .. + k_m <= K.

(Equivalently, we could specify that k₁, .., k_m >= 0, and that m = C. The previous way seems more intuitive, but this way might be more tractable).

For small values of K, this problem is pretty easy. Like I said before (and you can verify this pretty easily), for K = 6, L₄ = 6. As a matter of fact, L_C = 6 for all valid C. (C = 1 can use a full 6-cycle, and C > 1 can use 2-cycle and a 3-cycle). Of course, the Korn Shell problem is for K = 26. I've yet to come up with any insightful (read: non-brute force) way of computing it, though.

Game Project Update

Lots of progress on the game front, sort of. We have a name for the project, finally: Y.M.F.A.S. Or Ymfas, or ymfas... not sure of the format, but that's definitely what it's called.

About two days after the last post on the subject, we scrapped the "roll your own" route and decided to go with Irrlicht for rendering and ODE for graphics. Both are C/C++ native, so we used IrrlichtNETCP and Tao.Ode, respectively, as .NET wrappers. IrrlichtNETCP is pretty solid, but Tao.Ode had some issues.

For one, ODE is fairly low-level. This isn't all that bad for C/C++, but Tao.Ode is (I believe) one big PInvoke, so you end up with something fairly unusable in C#. For instance, the math types do not have overloaded operators in C# (though they do with C++). Furthermore, all of the ODE resources are translated into IntPtr's, which screams of type safety for any large-scale use. I even started building a wrapper on top of all this to cover up the gritty non-managed details, but that'll have to wait a little bit.

I later learned that MonoDevelop also sucks. Well, that's not quite true. Mono is great, and MonoDevelop is decent. However, it's a long way from SharpDevelop, the IDE that it was orignally a port of. OTOH, SharpDevelop is a long way from VS 2005, which I also get for free. So, with this in mind, I decided to scrap the lofty goal of cross-platform goodness.

So now that development is officially Windows-only, our options open a little bit (not as much as they would if we were using C++, but still...). So, after looking at the other side of the fence, we're tentatively using MOGRE and MogreNewt, .NET wrappers for Ogre3D and Newton Game Dynamics. This has the unfortunate downside that most of the code that I've already written pretty much goes to waste. Oh well. Let's see where it goes.

The 'Next Big Language' sucks

So there's lots of talk about how Steve Yegge considers Javascript to be the "Next Big Language". God I hope not.

For one, has you ever seen a nice-looking piece of JS code? Seriously, maybe it's just because so many non-programmers use it, but a lot of Javascript code out that is utter garbage (even compared to other languages IMHO). With enough discipline, you can make as structured as other languages, I suppose. Well, almost. There is no module or packaging system, for instance.

Javascript is an absolute pain to develop for, moreover. As great as Firebug is, it is nowhere near Eclipse , VS 2005, or emacs even.

I don't even think Javascript satisfies Steve's bare minimum for the NBL. For instance, it doesn't have operator overloading (yet). It doesn't have quantifiers either, and those seem much less likely to be added.

Of course, nit-picking aside, it probably is. Or at least, it probably is according to Steve Yegge. And, given how many people are paying attention to his predictions, it may end up that whether it was going to before or not. So it goes.

plans for summer

So this summer I'm working as an intern at TechEmpower. It's a fairly small software company, but it seems like a pretty cool place to work. At the very least, I'll learn a lot about webdev.

I'm also working on a game for the summer with a fellow Techer. We're trying to make not too ambitious so we can actually get something playable in three months. Details are a little skimpy, but for now, suffice it to say that it's a 3d fast-paced multiplayer space shooter. We're building it with OpenGL + SDL (my idea) in C# (his idea). We'll probably use as much pre-built stuff as possible (including but not limited to DevIL, lidgren, OpenAL, and ODE) since it has such a short schedule. I should actually propose the idea of using Ogre3D, but we can try reinventing the wheel a little bit ourselves :-P. Seriously though, I imagine Ogre3D would have a steeper learning curve, since I already know some OGL.

Who's to say for now how it's going to turn out, but I have high hopes.

So with those to, as well as learning Erlang and Chinese, I have a pretty busy summer. sigh. (Yes, I know one's a foreign language and the other's a computer language. So it goes.)

Test post

Not sure while I always do one of these. I don't really expect blogger.com to shut down unexpectedly or anything. On an unrelated note, I didn't know that it was bought by Google. They have their hands in a bit everything now, don't they?