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.

Friday, August 26, 2016 Eric Richards

A little over two years ago, I first saw Amit Patel's article on Polygonal Map Generation, and thought it was incredibly cool. The use of Voronoi regions created a very nice, slightly irregular look, compared to grid-based terrains. At the time, I had just finished up working on my DX11 random terrain code, and it looked like a fun project to try to tackle.

I then proceeded to spend several months messing around with different implementations of Fortune's Algorithm in C# to get started and generate the Voronoi polygons used to generate a terrain along the lines of Amit's example. At this point, I've lost track of all of the different versions that I've sort of melded together to produce the code that I've ended up with in the end, but some of the more influential are:

The original goal was to create a map generator, suitable for a kind of overworld/strategic level map. But, alas, life happened, and I got bogged down before I got that far. I did, however, wind up with a fairly cool tool for generating Voronoi diagrams. Because I had spent so much time trying to iron out bugs in my implementation of the algorithm, I ended up producing a WinForms application that allows you to step through the algorithm one iteration at a time, visualizing the sites that are added to the diagram, the vertices and edges, as well as the position of the beach and sweep lines. Eventually I also worked in options to show the circles through three sites that define where a Voronoi vertex is located, as well as the Delauney triangulation of the sites.

Voronoi regions, with the edges drawn in white, and the sites as the blue points.

Delauney triangulation, with triangle edges in green.

Showing both the Voronoi regions and the Delauney triangles.

I won't pretend that this code is fantastic, but it's kind of interesting, and I worked at it for quite a while, so better to have it out here than moldering on a hard drive somewhere. If you'd like to see the source, it is available on GitHub. You can also download the executable below if you like - I make no promises that it will work everywhere, but it is a pretty standard .Net 4.5 Windows Forms application. I've also got some videos below the fold, if you'd like to see this in action.

 Download Voronoi


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