I've said it before; my favourite tech blog is Eric Lippert's Fabulous Adventures In Coding. There's simply no-one else out there bringing such regular, reliably lucid exposition of matters algorithmic, to the community of C# developers.
Today, however, Eric surpasses even himself, with the fifth and final piece in his (prerecorded) series ostensibly about functional techniques, and the mathematical process of graph colouring. Before going in to detail about it, let me just point to some of Eric's previous "greatest hits", as listed in this post from Jeff Atwood's Coding Horror, including the highly authoritative four-part series on security and encryption: You Want Salt With That? Eric is also probably the best person in the world to explain concepts like Idempotence and Orthogonality for you, whenever you need that done.
Drawing and Colouring In
Okay, back to today's adventure. Part One starts out innocuously enough, with the stated aim of using "a fairly straightforward problem" - map colouring - to investigate the applicability and the utility of certain techniques from the field of functional programming. Specifically, the interplay between imperative loops and declarative LINQ queries, and possible roles for immutable data structures. Here, Eric sticks to the stated program: weighing up the pros and cons of each design decision; enumerating, explaining and evaluating the many trade offs encountered. Ending with a well-considered data structure design, this opening article already marks the series as a classic, with the sheer width of his design considerations, and depth of their exposition. For example:
The class is internal, not public. I want this to be an implementation detail of my application, not a part of a general-purpose library. As we'll see, this decision has an effect on other implementation choices. (Tradeoff: again, potential code reuse by others vs increased design and maintenance costs)(Eric always uses the purple crayon.) Part Two continues by applying the same highly detailed approach to complete the data structure design. Part Three, also continuing with the same cost-benefit analysis approach at each stage, presents the basic backtracking algorithm; weighs the expository power of recursion, against the performance benefits of eliminating it; and best of all, shows clearly the benefits of going with immutability in the data structure design, given that backtracking algorithm.
Just a Minute... Just a Minute...
Part Four tests the resultant solution on a map of South America. But then it takes an unexpected turn into a thinly disguised topological realm, where non-planar and non-global maps are considered. What's happening now? The solution turns out to be equally applicable to a toroidal world (think: Asteroids!) where seven regions are each connected to every other. Eric leaves us with the threat of more "particularly interesting graphs" with "lots of fully connected subsets" next time.
But next time, we'll find we're not in Kansas any more. We're on neither plane, nor sphere, nor torus. We're in a world of 16 countries. No wait, 81 countries. All fully edge-connected in little uniform alliances. We're in ... some kind of ... puzzle. Has anybody seen Part Five?
No comments:
Post a Comment