Monday, April 02, 2018 Eric Richards

A birthday, crunch time at work, Easter, experiments with MonoGame, and some other life things have gotten in the way of me continuing this series as frequently as I had planned, but never fear, back into the breach I go. Last time around, we started things off with Insertion Sort, which is the focus of Chapter 2.1 in my copy of the 3rd Edition. The natural next step to continue on to would be other sorting algorithms: selection sort, merge sort, quicksort, etc, etc. And we'll get there. But first I wanted to make a little diversion into one of the exercises for this chapter; writing a linear search.

I'm going to reproduce the problem definition from the exercise here, just to get us started:

Input: A sequence of n numbers such that A = {a1, a2, ..., an} and a value v.

Output: An index i such that v = A[ i ] or the special value NIL if v does not appear in A.

There's a bit more about writing loop invariants and proving that the algorithm is correct, if you were going to do this as a homework assignment. But that's incredibly dull, especially for something as self-evident as this. Let's get right to writing some code (github); this will be a short one.

Linear Search

There's not a whole lot to get fancy with with a linear search.

  • We have the value we're searching for, and an array of values.
  • We start at the beginning and compare the first item in the array with our search value, if it matches, we return that index.
  • If not, we move on to the second item, and repeat
  • If we get to the end and haven't found the value, then it isn't present, and we return our NIL sentinel value.
Since C# has 0-based arrays, and doesn't allow (yet) for any trickery like using negative indices to slice from the end, -1 is a reasonable sentinel value (and matches with the convention of the CLR Array.IndexOf function). So that leads pretty naturally to this, where we just use a for-loop:

public static int LinearSearch(this int[] a, int find) {
    for (var i = 0; i < a.Length; i++) {
        if (a[i] == find) {
            return i;
    return -1;

Wednesday, March 07, 2018 Eric Richards

The other day I was on HackerNews lurking as I do, and there were a number of people praising Introduction to Algorithms, the infamous CLRS book. Almost everybody who has been through a Computer Science degree has had to buy a copy of it and slog along through at some point. It's basically the bible of algorithms and data structures classes, and as most of that kind of book are, it's a weighty tome that costs about a week's work-study wages. Mine has mostly been gathering dust on the shelf for the past ten years...

I've got a little bit of a love-hate relationship with the book. My algorithms and data structures class in college was entirely theoretical - we didn't write a single line of code during the whole semester, we just did page after page of proofs. Moreover, the professor was one of those space-case academic types, who was probably a bang-up researcher, but couldn't teach a lick. My only enduring memories of that course are chalk scratching on the blackboard, as she transcribed the textbook word for word and symbol for symbol, and sitting in the 1902 Room in Baker Library with reams of scratch paper scattered across the table, flailing away doing induction proofs. Oh, and the week we spent going over that median-of-medians algorithm that I've still never seen a point to... I think I scratched out a B-, and it was easily the least enjoyable class of my entire degree.

On the other hand, I could see that there was a lot of really cool information in the text, if it was taught differently. I always thought that a hands-on version of the class, where you had to implement everything in C, rather than pseudocode and pencil, would be really fun, and moreover, really teach people how to program. Alas, we skipped a lot of the interesting material in the book, and overwhelmingly focused on proving run-time complexity bounds. Which I always thought was a little dumb, detached from real-life implementation details - there was very little consideration of trading space for time, or taking into account the capabilities of the hardware, or other real life concerns - but that is neither here nor there.

So this week, I decided to dust off my copy and give it another go. I'm mostly a C# programmer, and probably will remain one for the foreseeable future; it's a really nice language. However, I'm going to try to keep things pretty basic for the most part, to hew as closely to the pseudocode presented in the text.

Tuesday, September 12, 2017 Eric Richards

TLDR; the Microsoft Automatic Graph Layout library is pretty slick at automatically generating state transition diagrams.

One of the products that I work on for my day job is an instant message-based call center/helpdesk application. It's a pretty complicated beast, but at the heart of it, what it does is:

  • Allow users to contact a central endpoint.
  • Process the incoming request
  • Route the request to a member of a predefined group that can assist the end-user
  • Broker the conversation between the end-user and the helpdesk/call center agent.
  • Perform post-processing on the chat session once it has ended.
Internally, each incoming chat session uses a state machine to keep track of the session and its progression through the workflow. For each stage in the pipeline, we've got a State class that handles operations during that particular stage. There is also a table in our state machine which determines what the valid transitions between the states are, so that we can easily assert that the session is following the expected workflow.

This state machine started out fairly simple, with just a few states, but as always happens, we began to accrete features, and so more and more stages were added into the pipeline, and the complexity and number of state transitions grew. The state machine definition that originated as a hastily drawn scrawling on a sheet of printer paper blossomed into a Visio diagram, then eventually wilted into irrelevance as more and more states were added and documentation efforts fell behind. Like most manual processes, it became a pain point, and was neglected.

Things came to a head recently when it was discovered that a state transition had been added as a code path in certain situations, but the state machine transition table had not been updated accordingly, and so it was possible for chats to attempt to make a transition that the state machine would reject as invalid, leaving the chat session in limbo. Not ideal. Ideally, we'd have caught this in some way with compile or build-time static analysis, but getting that implemented is going to have to be an exercise for the future. Failing that, exhaustive unit-tests validating the state transition rules was the easier task, but ran into the difficulty that the hand-written design documentation had fallen out of date, which necessitated a tedious and time-consuming search through the code base to trace out the logic. Once that was complete, there remained the task of updating the Visio docs... which is less than fun to do by hand.

Earlier that week, I had run across a link to the Microsoft Automatic Graph Layout library, a nifty open-source project that makes it stupidly easy to define a graph and then either display it in a Windows Form or render to an image file. While it may not be quite as nice looking as a hand-crafted Visio doc, it's not too unattractive, and better, can be completely automated. So we can just pipe our state transition definitions into it from the source code, and right out comes a legible diagram. We can even run it as a post-build step in our build to automatically keep the documentation up-to-date. Hooray!

Tuesday, May 16, 2017 Eric Richards

Last time, I had started working through Jamis Buck's Mazes for Programmers. I've made quite a lot of progress in the meantime, but haven't managed to keep up with posting about that progress. Today, we're going to work through the meat of Chapter 3, where we'll implement a simplified version of Dijkstra's Algorithm (really a breadth-first search), which we'll use to find paths through our mazes. We will also use this algorithm to help visualize the biases that exist in our two previous maze generation algorithms, by coloring the backgrounds of each cell according to its distance from a starting point.

You can download the code for this post by downloading or cloning the Post_2 branch from my GitHub. Going forward, I'm going to try and tag the code for each post in a new branch - I'm still used to the old SVN model, but I'm trying to figure out how to take advantage of Git a little more.

Below you can see an example of where we'll end up, drawing the longest path through a maze, and coloring each cell according to its distance along the path.

Let's get started!

Sunday, April 09, 2017 Eric Richards

A few weeks back, I picked up a copy of James Buck's Mazes for Programmers: Code Your Own Twisty Little Passages. (The title is, of course, an homage to one of the original text adventure games, Colossal Cave Adventure, or Adventure for short, which featured a maze puzzle where every room was described as "You are in a maze of twisty little passages, all alike"). I read through most of it on my veranda in the mornings, looking out over Long Bay in Antigua while I was on vacation, wishing I had brought my laptop along with me (although my girlfriend is probably happy I did not...). Once I got back, I started diving into implementing some of the ideas from the book - it's been quite a joy, and a much needed break from debugging UCWA applications at the day job.

The code in the book is implemented in Ruby, however, I'm not a Rubyist, so I decided that I'd work through the examples in my language of choice, C#. The code is pretty simple, so porting it over has been pretty straight-forward. I also figured it would be an interesting exercise for trying out some of the newer features in the more recent versions of C# - I've been stuck using C# 5.0 due to some tooling that we haven't had a chance to upgrade yet at work. Today, I'm going to mostly cover the examples from Chapter 2, which lays out the general plumbing of the framework that the rest of the book builds on, and implements two simple maze-building algorithms, the Binary Tree and Sidewinder algorithms. For the full code, you can check out my GitHub repository; things there may change slightly from the version presented here as I work through more of the book, but the general structure should remain similar.


I have way too many programming and programming-related books. Here are some of my favorites.