Sparse Matrix Multiplication

I want the Math.NET Numerics developers to know their work is great, they put together an easy to use, astoundingly well documented numerical library for .NET. Please know this little criticism comes from a place of respect. It could even be that the code has been updated since your last release and what I'm going to point out is no longer a problem.

I really don't know much about calculus and mathematics at that level. I barely passed A-level maths, and the only time I've used any of the knowledge gained therein was when I had to calculate the first derivative of 1-e^-x at university. My mathematics skills are weak (sadly). So, when, in mid-April, I was asked at work to implement some maths heavy algorithms, I felt suitably challenged. Thankfully the scientist who was feeding me the algorithms understood them really well and was on hand to explain things to me over and over again until we finally got things working yesterday. Yay!

Some of what we did relied on sparse matrices, something I had heard of, but never used. So my first thought was that I needed a third party library to do these calculations. The library we are currently using is the bluebit .NET matrix library, it's not perfect and we'll have to replace it with something faster, but for the moment it makes the code testable. This matrix was not my first choice, ideally I wanted something we didn't have to pay for. My first stop was the Math.NET Numerics library. This, unfortunately proved to be too slow. I also tried out Extreme Optimization, but this library was also too slow. Other libraries I looked at were ILNumerics, IMSL.NET and Center Space NMath. I looked but I did not test these last three because each library's API and help were so bad I couldn't figure out how to do what I needed to do. I don't have time to figure out matrix maths, this is why I'm looking for a library. If you want me to choose yours, make it easy to use.

So that was the bulk of the outcome of my foray in numerical libraries. Bluebit is my current choice, but I will have to change it for something faster. This is not the only thing I learned. I learned something that I hope, if they haven't already, the Math.NET developers will be able to use in their code. I've not time to dive into the project, and patch it myself — as I've said, my understanding of the maths is not great — so feel free to take the code here and fix it to work in the library.

At work I'm dealing with quite large matrices. The stuff I've been testing with is 8K x 8K points, and the real data will probably be up to 32K x 32K. But these are sparse matrices, so working with them should not be too processor and memory intensive. The major things I need to do are transposition, multiplication and inversion. Inversion is the killer, and understanding it is currently over my head. It's the place where Extreme Optimization fell down, and where bluebit struggles. I need the algorithms to run in a few seconds. Currently, with 16K x 16K points and bluebit, it's taking 2 minutes. The algorithm did not complete with the other two libraries. I waited for over half an hour, and still nothing, and that was with 8K data.

The first problem that Math.NET encountered was with the multiplication of the matrices. This is what I hope I've optimised. All I've done is profile their code and change the bit that took forever - assigning data to a point in the matrix

My first step was to write these two tests, to make sure I was multiplying the matrices correctly:

[Test]
public void MatrixMultiplication()
{
    var leftM = new double[,] {{4, 5, 6, 7, 8, 1, 2}, {3, 9, 6, 7, 3, 3, 1}, {2, 2, 8, 4, 1, 8, 1}, {1, 9, 9, 4, 3, 1, 2}};
    var rightM = new double[,] {{1, 8, 1}, {2, 6, 2}, {3, 4, 1}, {4, 2, 2}, {5, 1, 1}, {6, 3, 2}, {7, 5, 1}};
    var expectedM = new double[,] {{120, 121, 46}, {107, 133, 51}, {106, 98, 40}, {97, 122, 43}};

    var sm = new SparseMatrix();

    var resultM = sm.MultiplyMatrices(leftM, rightM);

    Assert.AreEqual(expectedM.Rank, resultM.Rank);
    Assert.AreEqual(expectedM.GetLength(0), resultM.GetLength(0));
    Assert.AreEqual(expectedM.GetLength(1), resultM.GetLength(1));

    for(int row = 0; row < 4; row++)
    {
        for(int col = 0; col < 3; col++)
        {
            Assert.AreEqual(expectedM[row, col], resultM[row, col]);
        }
    }
}

[Test]
public void SparseMatrixMultiplication()
{
    var leftM = new double[,] {{1,2,3,0,0,0,0,0,0,0}, {0,0,0,0,0,1,2,0,0,0}, {1,0,4,0,0,5,0,0,0,0}, {0,4,0,5,0,6,0,0,7,0}, {9,0,0,0,0,0,8,0,0,0}};
    var rightM = new double[,] {{0,2,0,4,0}, {1,0,0,1,1}, {3,0,1,3,0}, {4,0,0,0,0}, {0,5,6,0,0}, {0,9,0,6,0}, {0,1,0,3,0}, {0,0,8,0,9}, {0,0,0,0,7}, {0,1,0,0,5}};
    var expectedM = new double[,] {{11,2,3,15,2}, {0,11,0,12,0}, {12,47,4,46,0}, {24,54,0,40,53}, {0,26,0,60,0}};
 
    var sm = new SparseMatrix();

    var resultM = bc.MultiplyMatrices(leftM, rightM);

    for (int row = 0; row < 4; row++)
    {
        for (int col = 0; col < 3; col++)
        {
            Assert.AreEqual(expectedM[row, col], resultM[row, col]);
        }
    }
}

(SparseMatrix isn't really the name of the class, I put the multiplication into the class that was handling the algorithm, but I'm not allowed to talk about that!)

Then I spent ages struggling (because of my ignorance, the code is easy to read) with the Math.NET code to try and understand sparse matrix multiplication - how it could be faster than normal matrix multiplication, and how I could implement it faster. It took a couple of days. I spent a couple of days, rather than giving up and finding a proprietary library right away, because I thought that Math.NET would do the business when it came to inversion. Sadly this isn't the case. Anyway, this is my optimised sparse matrix multiplication method:

private IEnumerable GetNonZeroIndicesForMatrixColumn(double[,] matrix, long col, int rowcount)
{
    for (int row = 0; row < rowcount; row++)
    {
        if (matrix[row, col] != 0)
        {
            yield return row;
        }
    }
}

private IEnumerable GetNonZeroIndicesForMatrixRow(double[,] matrix, int row, int colcount)
{
    for (int col = 0; col < colcount; col++)
    {
        if (matrix[row, col] != 0)
        {
            yield return col;
        }
    }
}
        
/// <summary>
/// Matrix multiplication optimised for sparse matrices
/// </summary>
/// <param name="matrix1">Matrix on the left of the multiplication</param>
/// <param name="matrix2">Matrix on the right of the multiplication</param>
/// <returns>A matrix that is the multiplication of the two passed in</returns>
public double[,] MultiplyMatrices(double[,] matrix1, double[,] matrix2)
{
    int j = matrix1.GetLength(1);
    if (j != matrix2.GetLength(0))
    {
        throw new ArgumentException("matrix1 must have the same number of columns as matrix2 has rows.");
    }

    int m1Rows = matrix1.GetLength(0);
    int m2Cols = matrix2.GetLength(1);
    double[,] result = new double[m1Rows, m2Cols];

    var nonZeroRows = new List[m1Rows];

    Parallel.For(0, m1Rows, row =>
    {
        nonZeroRows[row] = GetNonZeroIndicesForMatrixRow(matrix1, row, j).ToList();
    });

    var nonZeroColumns = new List[m2Cols];

    Parallel.For(0, m2Cols, col =>
    {
        nonZeroColumns[col] = GetNonZeroIndicesForMatrixColumn(matrix2, col, j).ToList();
    });



    Parallel.For(0, m1Rows , row =>
    {
        Parallel.For(0, m2Cols, column =>
        {
            var ns = nonZeroColumns[column].Intersect(nonZeroRows[row]);
            double sum = ns.Sum(n => matrix1[row, n] * matrix2[n, column]);
            result[row, column] = sum;
        });
    });

    return result;
}

As you can see, there is a lot of reliance on the parallel methods that come with .NET 4. That, coupled with the trick of getting the intersection of the non-zeros in the rows of the left matrix with the columns of the right matrix, seems to be the major advantage of my method over Math.NET, because their assignments can't be done in parallel. This could be to do with Silverlight compatibility issues, I don't know. I don't have to worry about Silverlight.

I have run a benchmark for my code. I created a 5000 x 5000 point matrix and filled it at random points with random data (well, pseudo-random). I benchmarked at 5, 50, 150 and 500 non-zero items per row. I ran the test 10 times, to get a mean. The table shows the results:

Number of non-zeros per row	Mean seconds taken to multiply	Standard Deviation
5	6.24465716	0.1037383251
50	51.10972332	0.8521258197
150	93.29733629	77.751344564
500	13.18435411	6.4991175895

I find it strange that the standard deviation for the 150 condition is so high. If anyone can see a problem in my code, I'd be really happy to hear it! The full test is below:

toggle test code

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;

namespace Math.NetBenchmark
{
    class Program
    {
        private static Random _r = new Random();

        static void Main(string[] args)
        {
            const int rows = 5000;
            const int cols = 5000;
            var nonzerosPerRow = new [] {5, 50, 150, 500};

            Console.WriteLine("started");
            using (var sw = new StreamWriter("MyMX10.results"))
            {
                sw.WriteLine("Number of non-zeros,Time taken");
                foreach (var nzpr in nonzerosPerRow)
                {
                    Console.Write(nzpr+" - making left");
                    var left = MakeMatrix(rows, cols, nzpr);
                    Console.Write("making right");
                    var right = MakeMatrix(rows, cols, nzpr);
                    Console.Write("multiplying...");
                    var startTime = DateTime.Now;
                    MultiplyMatrices(left, right);
                    var endTime = DateTime.Now;
                    var diff = endTime - startTime;
                    sw.WriteLine(nzpr + "," + diff.TotalSeconds);
                    Console.WriteLine("done");
                }
            }

            Console.WriteLine("done");
        }

        private static double[,] MakeMatrix(int rows, int cols, int nonzerosPerRow)
        {
            var result = new double[rows, cols];
            var colsPoss = Enumerable.Range(0, cols).ToArray();
            Parallel.For(0, rows, iRow =>
            {
                var posleft = colsPoss;
                Console.Write(".");
                for (int i = 0; i < nonzerosPerRow; i++)
                {
                    int posindex = _r.Next(posleft.Length);
                    int index = posleft[posindex];
                    result[iRow, index] = 1+_r.NextDouble();
                    posleft = posleft.Take(index).Concat(posleft.Skip(index+1)).ToArray();
                }
            });
            return result;
        }

        private static IEnumerable GetNonZeroIndicesForMatrixColumn(double[,] matrix, long col, int rowcount)
        {
            for (int row = 0; row < rowcount; row++)
            {
                if (matrix[row, col] != 0)
                {
                    yield return row;
                }
            }
        }

        private static IEnumerable GetNonZeroIndicesForMatrixRow(double[,] matrix, int row, int colcount)
        {
            for (int col = 0; col < colcount; col++)
            {
                if (matrix[row, col] != 0)
                {
                    yield return col;
                }
            }
        }

        public static double[,] MultiplyMatrices(double[,] matrix1, double[,] matrix2)
        {
            int j = matrix1.GetLength(1);
            if (j != matrix2.GetLength(0))
            {
                throw new ArgumentException("matrix1 must have the same number of columns as matrix2 has rows.");
            }

            int m1Rows = matrix1.GetLength(0);
            int m2Cols = matrix2.GetLength(1);
            double[,] result = new double[m1Rows, m2Cols];

            var nonZeroRows = new List[m1Rows];

            Parallel.For(0, m1Rows, row =>
            {
                nonZeroRows[row] = GetNonZeroIndicesForMatrixRow(matrix1, row, j).ToList();
            });

            var nonZeroColumns = new List[m2Cols];

            Parallel.For(0, m2Cols, col =>
            {
                nonZeroColumns[col] = GetNonZeroIndicesForMatrixColumn(matrix2, col, j).ToList();
            });

            Parallel.For(0, m1Rows, row =>
            {
                Parallel.For(0, m2Cols, column =>
                {
                    var ns = nonZeroColumns[column].Intersect(nonZeroRows[row]);
                    double sum = ns.Sum(n => matrix1[row, n] * matrix2[n, column]);
                    result[row, column] = sum;
                });
            });

            return result;
        }
    }
}

What does #deadbeef; look like?

I've been working with WPF themes a lot this week. My task has been to take a theme from one application and put it into another, otherwise unrelated, application. This is not as easy as it sounds. The themes from the original application do not transplant to other applications without judicious use of a hacksaw.

While going through the theme's various XAML files I noticed things like color="#FF123456", and I looked and I couldn't figure out what colour I was looking at. There are a lot of these hex notation colours and they all seemed opaque to me.

It struck me that it would be nice if I could just hover my mouse over the hex and get the colour to pop up. Sounded like an easy enough task. So I set out to write an extension for Visual Studio to do just that.

My first attempt to write an extension to Firefox met with disappointment - I couldn't figure out how to get started - so I was a little apprehensive about writing an extension for Visual Studio. Luckily extensions for Visual Studio are easy to create (so long as you have Visual Studio).

1. Download the Visual Studio 2010 SDK (or this one for Service Pack 1)
2. Install the SDK
3. Start a new project by selecting from the C#/Extensibility templates - I chose Editor Text Adornment, because I wanted to adorn the editor text with something.

The project comes with code already in place, so you can just hit F5 and you'll be able to see the extension at work right away. Then read the code to see how it works! It's pretty obvious, and with the Intellisense of Visual Studio you can discover all the bits you'll need with ease.

So my task, now that I have the ability to write an extension, was to write an extension that does what I want - i.e. show a colour swatch of the hex notation I'm hovering over.

Step 1: create a regex that picks out the hex. I tried one or two and settled on this one: #(([0-9A-F]{6})|([0-9A-F]{8})|([0-9A-F]{3}))["<;]. There might be ways to write it shorter, and I'm willing to hear them, but I'm not a regex guru, so I'll stick with simple. You'll notice that I've constrained the hex to start with a # and end with ", <, or ;. This way the regex will only pick up hex that is the right length, and not any old length, and is most likely meant to be a colour. All the colour hexes I could see ended in ", < or ;. I could have missed an edge case, but not so far!

Step 2: turn that string into a colour. There might be a library function for doing this, but I couldn't find it (would be glad if someone were to tell me about it!). I wrote my own:

private Tuple<byte, byte, byte, byte> BytesFromColourString(string colour)
{
    string alpha;
    string red;
    string green;
    string blue;

    if (colour.Length == 8)
    {
        alpha = colour.Substring(0, 2);
        red = colour.Substring(2, 2);
        green = colour.Substring(4, 2);
        blue = colour.Substring(6, 2);
    }
    else if (colour.Length == 6)
    {
        red = colour.Substring(0, 2);
        green = colour.Substring(2, 2);
        blue = colour.Substring(4, 2);
        alpha = "FF";
    }
    else if (colour.Length == 3)
    {
        red = colour.Substring(0, 1) + colour.Substring(0, 1);
        green = colour.Substring(1, 1) + colour.Substring(1, 1);
        blue = colour.Substring(2, 1) + colour.Substring(2, 1);
        alpha = "FF";
    }
    else
    {
    throw new ArgumentException(String.Format("The colour string may be 8, 6 or 3 characters long, the one passed in is {0}", colour.Length));
    }
    return new Tuple<byte, byte, byte, byte>( Convert.ToByte(alpha, 16)
                                            , Convert.ToByte(red, 16)
                                            , Convert.ToByte(green, 16)
                                            , Convert.ToByte(blue, 16));
}

OK, so this actually returns a Tuple<byte, byte, byte, byte>. I'm not entirely sure why I chose that over returning an actual colour. I might refactor that later. Anyway, turning the tuple into a System.Windows.Media.Color is a trivial call to the static method Color.FromArgb(byte, byte, byte, byte). Also, the above method is a brute force approach to breaking down the colour string into bytes, there could well be a better way. I'm sticking with what works until I'm shown something better.

My next hurdle was figuring out how to place the colour swatch where I wanted it. I was able to return the position in text the mouse was hovering over, which would give me a single character, but I couldn't think of how to use that position and character to get the hex colour string.

In the end I opted for a two stage approach. Stage one: when the layout updates, find the start and end positions for any colours in the view. Stage two: when the mouse is hovering somewhere, see if it's position is in any of the ranges previously stored.

Stage one looks like this:

private void OnLayoutChanged(object sender, TextViewLayoutChangedEventArgs e)
{
    _colourPositions = new List<Tuple<int, int, Color>>();
    var matches = Regex.Matches(_view.TextSnapshot.GetText(), "#(([0-9A-F]{6})|([0-9A-F]{8})|([0-9A-F]{3}))[\"<;]", RegexOptions.IgnoreCase);
    foreach(var m in matches)
    {
        var match = m as Match;
        var mgrp = match.Groups[1] as Group;
        var colourbytes = BytesFromColourString(mgrp.Value);
        var colour = Color.FromArgb(colourbytes.Item1, colourbytes.Item2, colourbytes.Item3, colourbytes.Item4);
        _colourPositions.Add(new Tuple<int,int,Color>(mgrp.Index, mgrp.Index + mgrp.Length, colour));
    }
}

I went with a list to store the position of the colours because I think it makes cleaner code than a dictionary would.
Stage two's like this:

private void ShowColourSwatch(int position, IMappingPoint textPosition, ITextView textView)
{
    _layer.RemoveAllAdornments();
    SnapshotPoint? snapPoint = textPosition.GetPoint(textPosition.AnchorBuffer, PositionAffinity.Predecessor);
    if (snapPoint.HasValue)
    {
        SnapshotSpan charSpan = textView.GetTextElementSpan(snapPoint.Value);
        var colourPos = _colourPositions.Find(cp => (cp.Item1 <= charSpan.Start) && (cp.Item2 >= charSpan.Start));
        if(colourPos != null)
        {
            Image image = CreateSwatchImage(colourPos, charSpan);

            _layer.AddAdornment(AdornmentPositioningBehavior.TextRelative, charSpan, null, image, null);
            Thread t = new Thread(p =>
            {
                Thread.Sleep(3500);
                lock (lockObject)
                {
                    Application.Current.Dispatcher.Invoke(new Action(() =>
                    {
                        _layer.RemoveAdornmentsByVisualSpan(charSpan);
                    }), new object[]{});
                }
            });
            t.Start();
        }
    }
}

The Thread in there just makes sure that the colour swatch disappears after three and a half seconds. CreateSwatchImage uses a lot of the code from the example project that Visual Studio gives you to start with, and just draws the colour swatch on a black and white background for contrast.

That is pretty much all the important code that I wrote in constructing the extension. There is one last snippet, I had to modify a single line in the auto-generated factory class so that the swatch would be above the text: [Order(After = PredefinedAdornmentLayers.Text, Before = PredefinedAdornmentLayers.Caret)]. Before that the property made the adornment go behind the text, which looked silly for my purposes.

The last thing that tripped me up was installing the extension. Obviously I can't sign my extension because I'm too cheap to pay for a certificate to do that with, so I can't get it put on the online extensions thing. However I was sure I could find a way. My first attempt was to double click on the .vsix file that Visual Studio had generated for me. This looked promising - it ran me through an install process and told me it had been successful, so I loaded up Visual Studio but my extension was no where to be found. I tried rebooting my computer, just in case, but to no avail. So I sought out where the extension had been placed and deleted it - which is how you are meant to uninstall extension, by the way - and went online to find out The Right Way™. A few places told me to put the extension in a folder under %appdata%, but that didn't seem to work. Eventually I found an MSDN page that explained I should be putting it under %localappdata%, which sorted me right out. Essentially the path should go something like %localappdata%Microsoft\VisualStudio\10.0\Extensions\[company]\[extensionName]\[version]\ although you can probably leave out [company] and [version] and it will still work. Once I put the extension there and loaded up Visual Studio, I checked the Extensions Manager in the tools menu and it was there, but needed enabling. After being enabled, and restarting Visual Studio, the extension was working like a charm! No more wondering about what a hex colour string means for me.

To view all the code for my extension, and download it for yourself, visit my Github repository.

Networking client / server example

At work I have been writing a lot of code relating to sending data over a TCP connection.

I have also seen a couple of questions, recently, on Stack Overflow asking about why networking code wasn't working. Unfortunately I didn't have time to answer them, but it did make me think that there must be a dearth of good samples of networking code online.

Allow me to make that dearth one sample fewer! (Does that make sense?)

For the full listing visit my Github repository: https://github.com/Mellen/Networking-Samples

One problem, that sparked my interest, was how to to keep the server running when a client disconnects. Because the server needs to know when a client disconnects, and not just choke and die. A client disconnecting is not an exceptional circumstance.

The first problem is to not let the server die when a client disconnects, the second is to keep the server looking for new connections, so that it can be a server.

Keep it alive!

My solution to the disconnection problem got generalised to both the client and the server classes, because it makes sense to not have the client die if the server disappears. The user might want to try to reconnect.

You'll find this code in the file NetworkSampleLibrary/NetworkStreamHandler.cs

protected void ReadFromStream(object worker, DoWorkEventArgs args)
{
    BackgroundWorker streamWorker = worker as BackgroundWorker;
    NetworkStream stream = args.Argument as NetworkStream;
    try
    {
        HandleStreamInput(stream);
    }
    catch (Exception ex)
    {
        if (ex is IOException || ex is ObjectDisposedException || ex is InvalidOperationException)
        {
            streamWorker.CancelAsync();
        }

        if (ex is IOException || ex is InvalidOperationException)
        {
            stream.Dispose();
        }

        if (StreamError != null)
        {
            StreamError(ex, stream);
        }
    }
}

You might have noticed that the method is an event handler. More on that below.

As you can see, there are three types of exception that can happen if a client disconnects from the server: IOException, ObjectDisposedException and InvalidOperationException. I found this out through trial and error.

The most common exception that gets thrown when a client disconnects is IOException. This is because the server will be trying to read from the client when it leaves.

Because of the threaded nature of the system, ObjectDisposedExceptions gets thrown when another exception gets thrown and the server still tries to read from the stream in the mean time.

I'm not entirely sure why InvalidOperationException gets thrown, and it doesn't happen a lot, but it is always when the client disconnects.

My strategy is to catch all exceptions, deal with the disconnection exceptions by disposing of the stream if necessary and cancelling the process that reads from the stream, then raising an event that contains the exception and the stream that threw it. I could create a custom exception here, but I settled on an event just in case something that wouldn't catch an exception wanted to know about it.

All are welcome

The next part of the puzzle is to make sure that more than one client can connect to your server.

This is achieved in the NetworkServer class. This can be found at NetworkServerSample / NetworkServer.cs

The pertinent parts are listed below:

public NetworkServer(int port)
{
    _listener = new TcpListener(IPAddress.Any, port);
    _listener.Start();
    _listener.BeginAcceptTcpClient(AcceptAClient, _listener);
    DataAvilable += SendDataToAll;

    StreamError += (ex, stream) =>
        {
            if (ex is IOException || ex is InvalidOperationException || ex is ObjectDisposedException)
            {
                _streams.Remove(stream);
                Console.WriteLine("lost connection {0}", ex.GetType().Name);
            }
            else
            {
                throw ex;
            }
        };
}

private void AcceptAClient(IAsyncResult asyncResult)
{
    TcpListener listener = asyncResult.AsyncState as TcpListener;

    try
    {
        TcpClient client = listener.EndAcceptTcpClient(asyncResult);

        Console.WriteLine("Got a connection from {0}.", client.Client.RemoteEndPoint);

        HandleNewStream(client.GetStream());
    }
    catch (ObjectDisposedException)
    {
        Console.WriteLine("Server has shutdown.");
    }

    if (!_disposed)
    {
        listener.BeginAcceptTcpClient(AcceptAClient, listener);
    }
}

private void HandleNewStream(NetworkStream networkStream)
{
    _streams.Add(networkStream);
    BackgroundWorker streamWorker = new BackgroundWorker();
    streamWorker.WorkerSupportsCancellation = true;
    streamWorker.DoWork += ReadFromStream;
    streamWorker.RunWorkerCompleted += (s, a) =>
                                        {
                                            if (_streams.Contains(networkStream) && !a.Cancelled)
                                            {
                                                streamWorker.RunWorkerAsync(networkStream);
                                            }
                                        };
    streamWorker.RunWorkerAsync(networkStream);
}

In the constructor, the server is set up to listen on a particular port for incoming connections and handle the connection requests asynchronously. It also creates an event handler for when the network stream throws an exception, as explained above. This makes sure that the stream is removed from the list of streams, so that it doesn't try to get disposed of when the server is disposed, and that no data gets broadcast down it.

The method that deals with the asynchronous requests for connection (AcceptAClient) has to make sure that the server hasn't been disposed of when the connection attempt is made, hence the try-catch block. Once the connection request has been handled then the method starts listening for another connection attempt. This is all it takes, essentially asynchronous recursion.

The HandleNewStream method also uses asynchronous recursion to read each message from the client. It sets up a BackgroundWorker instance that asynchronously calls the ReadFromStream method in the previous section, and when the work is complete, the worker will call the method again, so long as the stream is in the list of streams on the server and the worker has not been cancelled.

That's the meat of the server. Accepting and handling input from more than one client is achieved with a list and asynchronous recursion. Dealing with clients disconnecting is done with exception handling and events.

Quick idea

I think it should be trivial to make an png/jpeg/gif/bmp -> icon creator

I'm going to work to one.

Solving Sudoku

I was chatting with my manager the other day, just shooting the breeze, and we got on to how he knocked together a python script to prove to his girlfriend that programmatically solving sudoku puzzles is easy.

I disagreed for a moment and then realised I was thinking of generating sudoku puzzles, which we agreed isn't easy.

I had tried to make a sudoku helper app before, to practice MVVM and WPF, but had messed up in some calculation or other. Probably at the point where I was calculating which block a square was in. Anyway I had deleted that one, but my boss had spurred my interest in doing it again.

I'm a better programmer than I was that first time - I understand both WPF and MVVM better now, so this little solver is pretty sweet. (Unless you look at the code.)

It has all the features I need. I can fill in the known numbers, delete mistakes, and click a button to solve the unknowns (once the knowns are in place).
Sometimes you don't even need the button, since the programme eliminates possibilities as you type. One puzzle I tried was solved before I typed in all the known numbers!

So my amazing solver has two simple algorithms doing the solving:

1. Each square has an event that fires when its number of possible values reaches 1, either programmatically or by user intervention. This event is subscribed to by all the squares related to it (row, column, block), and so each related square will remove this value from their possible values list. This can cause a chain reaction of updates, solving the sudoku puzzle when enough knowns are typed in.
2. If elimination alone doesn't do the job then the second algorithm is just a button click away. I might have over thought this one:
1. Create a list of squares that have at least 2 possible values, sorted in ascending order of number of possible values
2. Take the first square and find all the squares in the same block
3. Add theses squares to a checked block list
4. Flatten the lists of potential values into one list
5. Find any unique values in that list
6. If there are any unique values then these represent solved squares so break out of the loop and update the squares related to those values.
7. If there isn't a unique value then repeat 3, 4 and 5 for the row, then the column of the current square.
8. If after that there still isn't a unique value, move onto the next square that hasn't been checked yet.

If at the end of the second algorithm a number hasn't been updated then the programme lets the user know that it needs more knowns, otherwise it starts the second algorithm again until all the squares are filled.

I know what you're thinking. You're thinking that if a user makes a mistake inputting a value, then when they delete it and input a new value the possible values list for the related squares will be wrong. Fear not! Deleting a value fires an event that does the opposite of inserting a value, so things go back to the way they were. Phew!

If you want to look at the code it's on github here: http://github.com/Mellen/SudokuSolver

The code is c#. The project is a Visual Studio 10 project, that runs on the .NET 4.0 framework. It even has a couple of unit tests. Yes, I'm that guy. I unit test toy projects.

The executable is available from github: SudokuSolver1.0.2.zip. It requires .NET version 4.0.

Anyway! This was a fun little diversion. I makes me happy that I got it right the second time.

Pomodoro!

I've been feverishly subscribing to blogs recently after I realised I'm only really reading channel9.

I've got so much reading to do it's unreal. I've got through about 50 .NET posts so far and I've got 50 more to go, before I'm caught up. I've also got about 50 PHP posts to read too.

In my .NET blogs I came across this entry: You say tomato i say pomodoro at the developing for .NET blog. The post outlines a simple way to help manage your time effectively. It has inspired me to create a little timer app and a todo list app.

The timer app is really simple: it's a picture of a tomato with a button on it that minimises the app to the notification area and sets a timeout period. Once the period is reached (the length is set in the config file) then the app pops back up and plays a sound at you. I've put the code over at GitHub: code for Pomodoro timer.

The todo list app is equally simple, just a list view and list item entry controls. On close it writes to a file. The source is also at GitHub: code for To Do List.

update

I've uploaded the binaries for each, so you don't have to compile them!

To Do List executable
Pomodoro executable