Tag Archives: c#

Finding the Shortest Path

I’ve known about Dijkstra’s algorithm for a long time, but never took the time to review it and then try to implement it on my own to prove whether I really understood the concept. Until today. I stumbled upon Eoin Bailey’s explanation of Dijkstra’s algorithm, and found it to be quite helpful.

As I was reviewing the algorithm, it struck me that I could probably use a min heap in order to keep track of which node to visit next. Fortunately, a few months ago I wrote a series of C# extension methods to “heapify” a list in exactly the same way that heapq does for Python. It was incomplete (and still is), but enough of the methods were in place that I could make use of it.

I ran into a few bugs, particularly when a longer path was calculated. It turns out the incomplete min heap had a few bugs in it. Once those were ironed out, the algorithm implementation seemed to work flawlessly.

My Dijkstra’s algorithm implementation is contained in my slowly growing DataStructures project on GitHub, if you’re interested in taking a peek.

Advertisements

Boy Meets Python

Last week I needed a quick solution to convert a CSV file to an XML file, and because C# is my primary language, I was able to throw this together in less than 10 minutes:

So what does this have to do with Python? Well, this weekend, I had the sudden urge to learn some Python. I wanted to build something that a.) would force me to learn a few things about the language, and b.) had value. The CSV to XML converter was fresh in my mind, and so I thought it would be a great way to begin my Python journey.

To start, I installed Python on Windows. I downloaded the installer from http://www.python.org/getit/, and was writing Python in just a few minutes. Pretty painless.

Writing Python was slightly awkward at first, but I quickly got the hang of things. Having taken the time to learn LINQ and lambda expressions a few years ago certainly helped.

Command line arguments were a breeze using argparse. Within minutes I had a way to specify the CSV input file and the XML output file. It isn’t absolutely necessary, but argparse makes specifying expected parameters easy, and comes prepackaged with --help. Nice.

Next, I stumbled upon csv, which was certainly helpful. But, again, I’m pretty sure I could have survived without it, treating the input file as a standard text file and reading one line at a time.

A long time ago I got into the habit of encapsulating file I/O with using() in C#. It felt awkward acquiring a file handle and having to call close() on it explicitly, but once I discovered Python’s with keyword, I felt right at home.

The rest of the script, which is really the meat of the conversion, required me to learn a little bit about lists and strings. I’m an avid user of string.Format(...) in C# and was happy to see that I could call format(...) in Python.

I began by reading in the first line, which always contains the headers. I wanted to form a string format something to the effect of <row col0="{0}" col1="{1}"/> that I could use when processing each subsequent line. I discovered the join() method on the string, and thought that might allow me to dynamically assemble the attributes. Calling join() on the string " " and passing to it a collection of strings generated by an iterator that iterates over the headers cleverly assembles the format string — in one line of code! (I felt pretty stupid when I realized that the string in C# also has this feature.)

The last remaining piece was processing each line of the CSV file. This was trivial once I generated a format string, with one exception. For each line, I thought I could call format() on the format string, pass in the list of values from the line, and write the newly constructed string to the file. The problem was, format() is expecting comma-delimited parameters, and I was holding onto a list of values as strings. Simply passing the reference to the list, line, was not sufficient. To my surprise, I discovered that I could essentially dereference the list (as such: *line), satisfying format().

And that completed the exercise! I won’t admit how long it took me to write, but let’s just say it took longer than 10 minutes.

Below is the script:

(Having spent the time to set up the row format in Python, I thought I should go back and use the same approach in C# , complete with using Join(), for a more apples-to-apples comparison.)

The mere fact that I did all of this on Windows felt slightly sacrilegious, so I decided to go back and conduct the same exercise, this time on Linux — Ubuntu 13.04 to be exact.

Ubuntu ships with Python installed, so technically there were even fewer steps to get started. But, it ships with v2.7.4, and the script I wrote on Windows apparently uses language features that didn’t exist until v3.x. So, I grabbed Python 3.3.2 for Linux from http://www.python.org/getit/, and followed these excellent instructions so that I could have both v2.7.4 and v3.3.2 installed simultaneously. Once installed, the script I wrote on Windows ran equally well on Linux.

It was clear during this exercise that I merely scratched the surface with Python. It appears to have quite an exhaustive API, contains many of the same constructs that I’m used to in C#, and I will not hesitate to use it for all of my future scripting needs.


A date with JSON

I don’t work with JSON every day. In fact, I hadn’t used it at all until the beginning of this year, when I made REST calls to Twitter and retrieved gobs of tweets as JSON.

I’m now working on a project that contains collections of immutable C# objects, and those objects need to make their way to ActionScript. Given that ActionScript is based on ECMAScript, it seems appropriate to serialize these objects as JSON so that ActionScript might easily consume them.

During my Twitter tinkering, I was using an older version of the .NET runtime, and I had no other choice but to rely on third party libraries for JSON support, lest I roll my own. This time, I have the latest and greatest at my fingertips, and I decided to take it for a test drive.

JavaScriptSerializer started off well, for the most part. I could easily serialize any object with a single line of code:

var myObj = new MyObject(...);

var jsonText = new JavaScriptSerializer().Serialize(myObj);

It’s simple, and perfectly innocent. Deserializing, however, proved to be slightly more difficult.

var deserializedObj = new JavaScriptSerializer().Deserialize<MyObject>(jsonText);

This would have worked, but the Deserialize() method depends on the existence of a default constructor, and invokes each property setter individually. That’s fine if you’re working with mutable objects, but for concurrency concerns, I insisted my objects be immutable.

The overload of Serialize() produced the same results.

var deserializedObj = new JavaScriptSerializer().Deserialize(jsonText, typeof(MyObject));

There was one last method on the JavaScriptSerializer class that had some potential: DeserializeObject().

var objGraph = new JavaScriptSerializer().DeserializeObject(jsonText);

DeserializeObject() returned a dictionary of objects keyed by string. I added a constructor to MyObject specifically to consume it. This worked, but I wasn’t pleased with having to add a separate constructor, and I wondered what I might do if types didn’t match up properly.

I continued to capture my assumptions as unit tests, and everything seemed to be working decently … until I hit a DateTime object. I would serialize a DateTime, and it would deserialize as a DateTime four hours ahead. Something was clearly awry.

A quick google search landed me at Scott Hanselman’s post from earlier this year in which he exposed JSON’s poor support of dates, and pointed out that Json.NET does a much, much better job.

I’ve used Json.NET in the past, and so with confidence, I fired up NuGet, downloaded Json.NET, and within the span of about five minutes, was able to produce this:

var jsonText = JsonConvert.SerializeObject(myObj);

var deserializedObj = JsonConvert.DeserializeObject<MyObject>(jsonText);

And, voila! Notice how I’m providing the type? Json.NET is intelligent enough to invoke my constructor with the proper values rather than just relying on a default constructor and invoking each property.

The conclusion? I spent the better part of a day trying to work around the shortcomings of JavaScriptSerializer, and Json.NET solved all of my problems in minutes. Microsoft, take note!


Hello, GitHub

I’m a little behind the times. I’ve been committing my code to an SVN repository for the last five years, and the interwebs are all about Git these days. I decided to take it for a test drive. But with what?

Almost a year ago, I started working on a data structures library in C# — not a useful library, just something I whipped up to essentially prove that I could still write a linked list and perform operations on it (such as reversing and sorting). It’s hardly something to brag about, but it’s a perfect test candidate for Git.

I went looking for my project, and boy, does my ignorance know no bounds. When I authored this library, I thought it would be best to test it out using a console app, spitting out values to the console, and inspecting the output by hand. Obviously, I should have just expressed that as a series of unit tests, but I probably felt that doing so would slow my progress with the library. Stupid. So, I converted the console code to a series of unit tests in MSTest. (I’ve only ever used NUnit, but hey, this is an adventure, right?) And besides, I was going to be committing this code to a public repository on Github, and I wanted to spare myself from embarrassment.

From there, I created an account with Github, and set up my first repository. Next, I installed Github for Windows to clone the repository on my local machine.

Everything was in place. But, to make things a little easier, I installed Git Source Control Provider plugin for Visual Studio, which also required the installation of straight-up Git. (By the way, Github’s instructions for setting up Git are very good.) Using this plugin was certainly a welcome change from managing my source from outside the IDE.

Via the Git plugin, I added all of the necessary files to the repository from within Visual Studio. Perfect. At this point, I had my data structures solution in Visual Studio 2012, complete with unit tests, and code fully committed to the local Git repository. The next logical step was to click “sync” in Github for Windows to sync all of my local changes with Github. Right? I did that, and received this gem:

Github for Windows: Unstaged Changes Error

Github for Windows: Unstaged Changes Error

OK, so how do I “stage” my changes? Sure, I could open the shell, but do what, exactly? Well, Github for Windows seemed to offer no solution, so the shell quickly became my only option. I fired up Git Bash (part of Git), and typed git commit to see what happened. The response was that there was nothing to commit. Ah, so git commit is only local. I typed git help to see what other options were available, and git push looked like it had some potential. I tried that out, was prompted for my Github credentials, and bam — all of my local commits have been pushed up to Github.

I’ve only gotten started. I have more code to add to the project, and I will try adding it from multiple machines to get a feel for the experience of team collaboration with Git/Github. Look for those details in a future post.

Update: Github for Windows JUST made a liar out of me. I repeated all of these steps on another machine, made a small change, synced from Github for Windows, and pushed the changes to Github without any problems. Go figure!

Update 2: It wasn’t Github’s fault, it was mine. It helps when you point Visual Studio’s Git plugin to Git running on Windows.

Incorrect Path to Git for Windows

It helps when you provide a valid path to Git for Windows.


Finally Definitely Executes Last

Finally executes last, every time, right? I recently came across a scenario that made me second-guess myself, and I had to throw together a quick sample project to be certain my understanding was correct.

For example:

private readonly object sync = new object();

private int GetSomeValue()
{
	Monitor.Enter(sync);
	try
	{
		return GetTheValue();
	}
	finally
	{
		Monitor.Exit(sync);
	}
}

private int GetTheValue()
{
	return 42;
}

Sure, the code in the finally block will execute no matter what, so I am confident that the lock will be released. But, what about that return statement inside the try? Is there any funny business going on there? If there is, it might defeat the purpose of employing a lock.

So to be sure, I tossed in a breakpoint inside the GetTheValue() method, and another inside the finally. I want to be sure that the GetTheValue() method executes before the lock is released. And, sure enough, it does.


Asynchronous Delegates: Catching Exceptions

Consult any C# reference regarding asynchronous delegates, and you will be assured that you can catch any exception thrown by an asynchronous delegate so long as you call EndInvoke() on the delegate reference.

I assembled a quick test, explicitly throwing an exception within the asynchronously invoked method, and the debugger routinely flagged the exception as unhandled. Convinced I had done something wrong, I stopped the debugger, combed over my code, and checked more C# resources. Everything looked correct.

Suddenly, it occurred to me to try running the application outside the debugger. The clouds parted. The call to EndInvoke() was rethrowing the exception from the asynchronous delegate after all! I then went back to the bugger, continued stepping through the code past the “unhandled exception,” and sure enough, the call to EndInvoke() was delivering the goods all along.

public void MethodAsync()
{
    Action action = Method;
    IAsyncResult result = action.BeginInvoke(MethodComplete, null);
}

private void Method()
{
    throw new Exception("Fail.");
}

private void MethodComplete(IAsyncResult result)
{
    Action action = (Action)((AsyncResult)result).AsyncDelegate;
            
    try
    {
        action.EndInvoke(result);
    }
    catch (Exception ex)
    {
        // ...
    }
}

A Quick Lesson on For Loops in C#

For the longest time, I thought I knew everything there was to know about for loops in C#. Hubris, I know. But, today, I wanted to construct a complex loop in which I needed to keep track of two simultaneous values; namely, an int counter and a current object. I would have bet money that I could write something like this:

for (int count = 0, object x = GetSomeObj(); /* condition */; ++count, x = GetNextObj(x))
{
    ...
}

But alas, the compiler complained.

error CS1044: Cannot use more than one type in a for, using, fixed, or declaration statement

I solved this problem by declaring my variables just above the loop:

int count;
object x;
for (count = 0, x = GetSomeObj(); /* condition */; ++count, x = GetNextObj(x))
{
    ...
}

It turns out that the compiler is fine with the same type, such as when you declare:

int i = 0, j = 1, k = 2;

However, when mixing types, you’re out of luck.

For more information on the subject, see: http://social.msdn.microsoft.com/forums/en-US/csharpgeneral/thread/93dfb7ee-23f7-47d5-8ff9-af7bc5759933