Unexpected Surprise

Have you ever been surprised by someone who bought you something completely unexpected? Something which they would not normally get for you as it's uncharacteristic of them?

Well during my recent birthday I got a note through the door whilst I was out from the Royal Mail saying that they had tried to deliver a package but of course no-one was home. So later that day I headed down to the delivery office and picked it up and one top of the items in the box was an Amazon note and a message from my Dad wishing me a happy birthday. Now in the box was one book which really took me by surprise, he'd gone and bought me "Beginning Game Development with Python and PyGame"! To say I was bowled over would be an understatement.

My dad was the person who initially got me into programming, he insisted when I got my first computer that I learn to use it properly and it not be used only for gaming. Whilst I'm sure he meant that I should learn how to write documents and edit graphics with it instead of hacking around with code he encouraged me to continue anyway, but never actually as far as buying me a programming book so this is a first. I know he bought it from my Amazon Wish List but there were other books on there along with music and DVD's so the fact he bought this one is incredible. I'm fairly sure he's not following this blog either as usually just turning a computer on is enough to get him fed up with using them so the idea he spends time browsing the web and reading a blog of mine dedicated to programming is slightly more than unlikely.

But anyway I thought I'd mention as the book is likely to drive some further posts to here and I'll write up a review on the book when I get somewhere useful with it.

So as promised I finally got around to putting up the code I spoke about in my last post, unfortunately after an initial attempt to post it here and a noticeable FAIL I decided to post it up to a new Google Code project called monoalgorithm, so now I have a project I can share and build up a collection of algorithms in :)

Anyway, it's under a new style BSD license and compiles and runs under Mono 1.9.1 so feel free to have a look and modify if you want. Of course now I have to learn how to use subversion as well as learning C++, Python etc... Obviously I must really like pain.

http://code.google.com/p/monoalgorithm/source/browse/trunk/Algorithm.cs

Bugger!

I never realised the finished formatting for a simple bit of HTML would look so bad in Blogger! I'll try and do something about that when I publish the full code tomorrow and in future posts.

Back over to .Net for a bit

Never completely happy with sticking to one language for any longer than a month (I get way to distracted) I've been playing around with C# over the last couple of weeks, specifically generics and lambda expressions with use in algorithms. The reason for this is as per usual something I came across on Project Euler, as I've done with all other problems I implemented the solution in Python - and I'm not likely to change that any time soon - but the initial solution came from C++ and the standard template library.

The problem involved determining lexicographical permutations which is a fairly common task when you want to test code. The reason for this is if you want to test a method with a range of values you can produce permutations of an original list and pass in each one, lexicographical simply means they are in order. For example, the list [0, 1, 2] can be arranged in the following permutations:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Initially I struggled to come up with a solution to this spending ages trying to figure out how to determine the next permutation in order. The answer came from the elegantly titled "Algorithm L". To summarise what it does I'll try and show an example in action, so first we start with our initial permutation.

1 2 3 4 5

First we start from the second to last index (in this case index 3 because indexes are zero based and the number there is 4) and work our way backwards until we find an index where it's value is less than the one after it which in this case is the same index we started at.

Index	0	1	2	3	4
Value	1	2	3	4	5
				^

So we assign this index as j (j = 3), next we start from the last index and work backwards to j until we find an index whose value is larger than the one at j, in this case it's nice and easy because it's the last index, and we set that index as m. If we had not found a value for j then there would be no further permutations.

Index	0	1	2	3	4
Value	1	2	3	4	5
					^

After we have found j and m we swap the two values at the indexes and then sort all the values after j, so in this instance we end up with:

1 2 3 5 4

If we repeated the process again from this permutation we would do something like this:

Index	0	1	2	3	4
Value	1	2	3	5	4
			j		m

Index	0	1	2	3	4
Value	1	2	4	5	3

Index	0	1	2	3	4
Value	1	2	4	3	5

Implementing this in Python was easy but I wanted to play with Generics in C# so I decided to implement it in that language.

Generics are a way in which we can write a class to work on different data types without implementing the code with 1 certain type, for instance if we create a method that sorted arrays we could write something like:

public void Sort(int[] arrayOfValues) { ... }

Which would work great but if we then wanted to sort an array of doubles or characters we would have to re-implement the method for different types so we end up with SortInt(), SortDouble() and so forth. Whilst this may be okay for a couple of types if we wanted to sort other types and custom types then re-writing this code becomes a lot of work, makes maintenance harder and introduces a greater chance of error. This is where generics comes in, instead of the method signature used above we can instead write it as follows:

public void Sort(T[] arrayOfValues) { ... }

When we call this method we then define the type of data we are working like so:

int[] myIntArray = new int[] { 1, 2, 3, 4 };
char[] myCharArray = new char[] { 'a', 'b', 'c', 'd' };

Sort(myIntArray);
Sort(myCharArray);

As you can see the method call is identical except that we are specifying the data type we intend to work with, the magic part here is the <T> after the method name, this indicates that we are using a generic type called T and we can use it in the method like we would a normal type.

public void PrintValues(T[] arrayOfValues)
{
   foreach (T value in arrayOfValues)
   {
       Console.WriteLine(value);
   }
}

Now one problem we will encounter with the Sort() method we described above is that we cannot compare generic types as we can't guarantee that they will be comparable, to get around this we add a constraint to the method like so:

public void Sort(T[] arrayOfValues) where T: IComparable { ... }

This instructs the system to only accept types which implement IComparable, with this guarantee in place we can now compare values in the method:

public void Sort(T[] arrayOfValues) where T: IComparable
{
   ...
       if (arrayOfValues[a].CompareTo(arrayOfValues[b]) > 0)
       {
           T holder = arrayOfValues[a];
           arrayOfValues[a] = arrayOfValues[b];
           arrayOfValues[b] = holder;
       }
   ...
}

Using this we can implement our next_permutation algorithm in C# and enable it to work with any types (restricted to comparable types of course) we choose. Unfortunately I don't have the code to hand at the moment so I'll post it up for all to see and criticise (be kind please) tomorrow.

This has taken up quite a lot of space for now so I'll save the post on Linq for another day, but not to long away I promise as I want to post about it before I go for the next big C++ push.

And that's why I love python!

Well for the last few weeks I've been hacking away with C++ whenever I get some free time which although interesting has been tedious, after all having to remember when you're passing pointers, references or values gets to be a pain real quick.

One of the really nice things with something like C++ though is memory management and speed when you get it right, you're working with natively compiled code and not having to wait for a garbage collector to clear up your allocations for you which makes for nice neat code. Of course like I said this is when you get it right, the downside is getting it wrong means memory leaks, stack overflows, variables pointing to garbage and so on which is troublesome to fix.

Today I got a little bored of all this so I figured it was time to put my Python hat back on and do some coding which was a little more interesting. So I took up one of the puzzles over at Project Euler (22 to be exact) which involves reading in a file of over 5000 names, sorting them alphabetically and then adding the numerical value of each name multiplies by it's position to an overall count and deducing what the total value of the names is. So where "COLIN" is at position 938 and it's numerical value is 53 (C=3, O=15 etc...) it's overall value is 49741.

I dread to think how to do this in C++ but in python it's a breeze thanks to it's list comprehension and easy file methods. So reading in the file is simply:

names_file = open("names.txt", "r")
names = names_file.read().replace('"', '').split(',')
names_file.close()

And there we have the file being opened, the contents being read, having any quotes removed and then split by commas to get a list and finally the file being closed. Then to do something like figure out the numerical value of COLIN we do something like this:

alphas = " ABCDEFGHIJKLMNOPQRSTUVWXYZ"
name_value = sum([alphas.index[c] for c in "COLIN"])

so alphas is defining a string (with an intentional first space so that A is now at index 1), the alphas.index[c] part basically returns the index in the alphas string of a character and the "for c in "COLIN"" part is looping through each letter in the name. Surrounded by the square brackets means we are producing a list, so each iteration adds a new value to the list and then the sum() adds them all together. It's just to easy.

If anyone is interested, the finished code (not published here as I shall leave it as an exercise for the reader to complete) takes about 92 milliseconds to run against all 5163 names.

Best laid plans and all that

So I mentioned previously the books I was looking at and I can inform you that I ended up with none of them! Whilst I was looking around we ended up going on holiday and I spent all of that lovely book money on wasteful stuff like having fun, what was I thinking. So to keep me going I started looking at a site run by a guy called Alex called Learn C++ which is not only informative but well written and I reckon is a good place to head over to whether you're an experienced programmer or complete novice.

Anyway in the end I picked up a book from Amazon as a reference by someone called Bjarne Stroustrup who happened to create the C++ language so I figured he must know what he's talking about. The book is called The C++ Programming Language: Third Edition, it was published a few years ago now but not a lot has changed really since. I haven't had a proper look through yet but when I do I'll let you know what it's like, currently I'm still working through the Learn C++ site.

The Python stuff has unfortunately taken a bit of back seat, I still haven't had a chance to work through the latest game in Linux Format as things have been busy and it's taking enough effort to fit in the C++ around it all. But hopefully as we get towards christmas things will quieten down a little and I can get back into it again.

Still ongoing...

Well having recently had a holiday and having made some time to do some odd jobs around the place my pace of development has dropped. I've had some time to look around at a few books for C++ and have downloaded a copy of "How to Think Like a Computer Scientist". I think for the time being I'll be looking through this until I can purchase a book of my choosing, for some reason I still like books in dead tree format although as soon as devices like the BeBook become more affordable I may consider getting one of them instead.

Currently I'm looking at getting a Sam's teach yourself in one hour a day book but I've never used one of their books before normally preferring instead to go for something from O'Reilly or Apress. It's quite amazing how we can grow accustomed to and even develop a preference for a particular publisher.

In the mean time I've just received my next copy of Linux Format and there is another PyGame tutorial in there so I'll probably dive into that at some point in the very near future.