I’d like to recommend a couple of freeware applications I couldn’t do without.

Launchy is a keyboard jockey’s dream. It’s a Start Menu replacement application that can index more than just shortcuts. I like it to know about my documents as well. It has a GUI, normally hidden, that’s launched with a hot key (Win+Space, in my case). I start typing a few letters, and Launchy tries to autocomplete. Hitting Enter launches the application (or the default action for the file type). After using it for a bit, you can get to the vast majority of your most used stuff in two letters. If you use keyboard shortcuts in any of your applications, give it a whirl!

I also need some sort of hierarchical notes manager that I can use at home and work. OneNote is great but not free, and thus not an option at work. I used to use Tranglos’s KeyNote (not to be confused with Mac’s presentation creator), but it’s been abandoned for a few years, and it’s missing key things like RTF 2 support, which means I can’t cut and paste tables into it with any confidence of the layout remaining intact.

My co-worker introduced me to FreeMind, which does the trick. It’s laid out like a mind map, and moving nodes around is a breeze. I ran into an issue storing code snippets in it, because it likes to trim leading space and its automatic formatting is overzealous. However, it does allow composing nodes in HTML, so I’m able to proceed with the <pre> tag. I do like the ease with which you can embed hyperlinks (Ctrl+K, paste, Enter to set up, click on the node to launch). If you are looking for a way to keep your notes organized, give it a try! If you do, I’d recommend the beta (0.9.0 beta 18), as it has some compelling features, like sorting of nodes and a simple HTML editor.

Kata 4 is about data munging. We’re asked to download a couple of text files and extract some data. The first is weather data (Listing 1). The second is soccer data (Listing 2). Listing 3 is the DRY unified version. I combined the programs, but they could just as easily have been two programs. Then, we were asked to answer some questions. I’m going to answer them out of order. The writing of the first program certainly did alter my approach to the second. In fact, as you can see, the second program is almost identical to the first, because I retooled the first program to create the second program. I can’t say whether factoring out code is always a good thing, but I think it certainly was in the case. Premature factoring is a waste of effort, but once the commonality emerges, I think factoring is often the right thing to do. I don’t think the readability or maintainability of this particular program suffered too much, but I agree it can quickly become a concern in larger programs. See also my previous Kata posts: Kata 1, Kata 2 and Kata 3.

Listing 1: Weather data

using System;
using System.IO;
using System.Text.RegularExpressions;

namespace Kata_4
{
    public class Kata4Part1
    {
        static void Main()
        {
            PrintSmallestDaySpread();
            Console.ReadLine();
        }

        static void PrintSmallestDaySpread() {
            string dayWithSmallestSpread = "(none)";
            int smallestSpread = int.MaxValue;
            using (FileStream f = File.Open(@"....weather.dat", FileMode.Open)) {
                using (StreamReader sr = new StreamReader(f)) {
                    while (! sr.EndOfStream) {
                        string s = sr.ReadLine();
                        Match m = Regex.Match(s, @"^s+(d+)s+(d+)s+(d+)");
                        if (m.Groups.Count > 1) {
                            string day = m.Groups[1].ToString();
                            int maxTemp = Convert.ToInt32(m.Groups[2].ToString());
                            int minTemp = Convert.ToInt32(m.Groups[3].ToString());
                            int spread = Math.Abs(maxTemp - minTemp);
                            if (spread < smallestSpread) {
                                smallestSpread = spread;
                                dayWithSmallestSpread = day;
                            }
                        }
                    }
                }
            }
            Console.WriteLine("The day with the smallest spread is day {0}", dayWithSmallestSpread);
        }
    }
}

Listing 2: Soccer data

using System;
using System.IO;
using System.Text.RegularExpressions;

namespace Kata_4
{
    public class Kata4Part2
    {
        static void Main()
        {
            PrintSmallestGoalSpread();
            Console.ReadLine();
        }

        static void PrintSmallestGoalSpread() {
            string teamWithSmallestSpread = "(none)";
            int smallestSpread = int.MaxValue;
            using (FileStream f = File.Open(@"....football.dat", FileMode.Open)) {
                using (StreamReader sr = new StreamReader(f)) {
                    while (! sr.EndOfStream) {
                        string s = sr.ReadLine();
                        Match m = Regex.Match(s, @"^s+d+.s+(w+)s+d+s+d+s+d+s+d+s+(d+)s+-s+(d+)");
                        if (m.Groups.Count > 1) {
                            string team = m.Groups[1].ToString();
                            int goalsFor = Convert.ToInt32(m.Groups[2].ToString());
                            int goalsAgainst = Convert.ToInt32(m.Groups[3].ToString());
                            int spread = Math.Abs(goalsFor - goalsAgainst);
                            if (spread < smallestSpread) {
                                smallestSpread = spread;
                                teamWithSmallestSpread = team;
                            }
                        }
                    }
                }
            }
            Console.WriteLine("The team with the smallest goal spread is {0}", teamWithSmallestSpread);
        }
    }
}

Listing 3: Unified version

using System;
using System.IO;
using System.Text.RegularExpressions;

namespace Kata_4
{
    public class Kata4Munger {
        public static string ExtractSmallestDifference(string fileName, string regex) {
            string itemWithSmallestSpread = "(none)";
            int smallestSpread = int.MaxValue;
            using (FileStream f = File.Open(fileName, FileMode.Open)) {
                using (StreamReader sr = new StreamReader(f)) {
                    while (! sr.EndOfStream) {
                        string s = sr.ReadLine();
                        Match m = Regex.Match(s, regex);
                        if (m.Groups.Count > 1) {
                            string day = m.Groups[1].ToString();
                            int maxTemp = Convert.ToInt32(m.Groups[2].ToString());
                            int minTemp = Convert.ToInt32(m.Groups[3].ToString());
                            int spread = Math.Abs(maxTemp - minTemp);
                            if (spread < smallestSpread) {
                                smallestSpread = spread;
                                itemWithSmallestSpread = day;
                            }
                        }
                    }
                }
            }
            return itemWithSmallestSpread;
        }
    }

    public class Kata4Part3
    {
        static void Main()
        {
            string itemWithSmallestSpread = Kata4Munger.ExtractSmallestDifference(@"....weather.dat", @"^s+(d+)s+(d+)s+(d+)");
            Console.WriteLine("The day with the smallest spread is day {0}", itemWithSmallestSpread);

            itemWithSmallestSpread = Kata4Munger.ExtractSmallestDifference(@"....football.dat", @"^s+d+.s+(w+)s+d+s+d+s+d+s+d+s+(d+)s+-s+(d+)");
            Console.WriteLine("The team with the smallest goal spread is {0}", itemWithSmallestSpread);
            Console.ReadLine();
        }
    }
}

Kata 3 has to do with estimation. The full questions are on Dave’s blog.

How Big?

• Roughly how many binary digits (bit) are required for the unsigned representation of:
  • 1,000 : 10
  • 1,000,000 : 14
  • 1,000,000,000 : 18  
  • 1,000,000,000,000 : 22 
  • 8,000,000,000,000 : 25
• My town has approximately 20,000 residences…. Let’s allow 100 characters for a name, 150 for an address, and 15 characters for a phone number. 165 * 20000 = 310000 characters 
• I’m storing 1,000,000 integers in a binary tree…. I don’t know much about binary trees, but I would expect it to have ln 1,000,000 levels. Based on my answer above, that’d be about 14, yielding 2^14 nodes. As for space, each number could be stored in 14 bytes, which would be 14 MB for a million numbers.

How Fast?

• My copy of Meyer’s Object Oriented Software Construction… I’m going to guess about 120,000 words. Let’s say the average word in a technical text is 5 characters long, so that’s 600,000 letters. With formatting, I’d budget 900kb for plain text. This jives with my recollections of Project Gutenburg novels.
• My binary search algorithm… It should go exponentially, so a hundredfold increase in entries caused a 1.5ms increase. The next one is another hundredfold, so that would be 1.5ms x 1.5 ms, or 2.25mS. So, I say 7.75ms.
• Unix passwords are stored using a one-way hash function… Well, that would be 96! / (96 - 16)!, which is 96 * 95 * … * 80, or about 88^16, or about 7700^8, or about 670000^4, or about 44x10^8 ^2, or about 176x10^16 ms. There’s 1.5x10^9 seconds per year, so it would take millions of years to crack the algorithm. My answer is no. :)

See also my previous Kata posts: Kata 1, Kata 2

Code Kata 2 was harder than Kata 1. Dave is right, it’s hard to come up with five different ways to do something! However, I think I have five sufficiently different approaches to warrant a post. My code, in C#, is below the More tag.

Approach 1 is a simple for loop, starting at the bottom and working its way up. Approach 2 uses a different looping mechanism for variety, but it does its comparisons from both ends of the array, which is faster than Approach 1 for values towards the larger end of the array.

Approach 3 leverages the fact that in C#, the List object has a built-in IndexOf function, and frankly is the way I would normally implement it.

Approach 4 creates a Dictionary with index/value pairs (in other words, a hash table), then determines the result. Lookups after the hash is built should be very quick. However, for a large array, there’s a lot of overhead in creating the hash, and the hash would need to be maintained or recomputed if the array changes.

Approach 5 uses a bifurcation algorithm, basically implementing the Picard Iteration approach of successive approximations. By far, it was the hardest to write. It splits the array in half, checks which half the target value would be in, and repeats until it finds the target value or proves the target’s not in the array. For a small array like this, it’s overkill. For sparse lookups against a large array, it might even prove to be the fastest.

Approaches 2 and 5 were the last ones I came up with. I had to start questioning my assumptions, which is when I hit upon Approach 2. Approach 5 came to me in the shower while I was trying to apply my Math degree to the problem.

I can’t wait for Kata 3!

(I’m going to apologize for the code formatting in advance. I need to do some research about the hosting on Wordpress and what formatting is and isn’t allowed!)

using System;
using System.Collections.Generic;

namespace Kata2
{
    class Program
    {
        delegate int Chopper(int number, int[] array);

        static void Main(string[] args)
        {
            int[] array = new int[] { 1, 2, 3, 5, 8, 13 };
            TestChopper(Chop1, array);
            TestChopper(Chop2, array);
            TestChopper(Chop3, array);
            TestChopper(Chop4, array);
            TestChopper(Chop5, array);

            Console.WriteLine("Test complete");
            Console.ReadLine();
        }

        static void TestChopper(Chopper c, int[] array)
        {
            int highBound = array[array.Length - 1] + 1;
            Console.WriteLine(c.Method.Name);
            for (int i = 0; i < highBound; i++)
            {
                Console.WriteLine(string.Format("{0} has index {1}", i, c(i, array)));
            }
            Console.WriteLine("n");
        }

        ///
        /// Simplest approach: for loop
        ///
        ///
        ///
        ///
        static int Chop1(int number, int[] array)
        {
            for (int i = 0; i  number)
                {
                    break;
                }
            }
            return -1;
        }

        ///
        /// Bi-directional lookup with slightly different looping
        /// mechanism.
        ///
        ///
        ///
        ///
        static int Chop2(int number, int[] array)
        {
            int arraySize = array.Length;
            if (arraySize > 0)
            {
                int i = 0;
                do
                {
                    if (array[i] == number)
                    {
                        return i;
                    }
                    if (array[arraySize - i - 1] == number)
                    {
                        return arraySize - i - 1;
                    }
                    i++;
                } while (array[i-1] < number && i < (arraySize / 2));
            }
            return -1;
        }

        ///
        /// Convert array to List, then use built-in IndexOf method
        ///
        ///
        ///
        ///
        static int Chop3(int number, int[] array)
        {
            List list = new List(array);
            return list.IndexOf(number);
        }

        static Dictionary chop4Hash;
        ///
        /// Pre-populate a Dictionary, then do the lookup
        ///
        ///
        ///
        ///
        static int Chop4(int number, int[] array)
        {
            if (chop4Hash == null)
            {
                chop4Hash = new Dictionary();
                for (int i = 0; i < array.Length; i++)
                {
                    if (!chop4Hash.ContainsKey(array[i]))
                    {
                        chop4Hash.Add(array[i], i);
                    }
                }
            }

            if (chop4Hash.ContainsKey(number))
            {
                return chop4Hash[number];
            }
            else
            {
                return -1;
            }
        }

        ///
        /// Bifurcation algorithm
        ///
        ///
        ///
        ///
        static int Chop5(int number, int[] array)
        {
            int leftIndex = 0;
            int rightIndex = array.Length - 1;
            int currIndex = 0;
            int nextIndex = int.MinValue;
            do
            {
                nextIndex = (int)((leftIndex + rightIndex) / 2);
                if (nextIndex != currIndex)
                {
                    currIndex = nextIndex;
                }
                else
                {
                    currIndex = Math.Min(nextIndex + 1, array.Length - 1);
                }

                if (array[currIndex] == number)
                {
                    return currIndex;
                }
                else if (array[currIndex] < number)
                {
                    // number's to our right
                    if (leftIndex != currIndex)
                    {
                        leftIndex = currIndex;
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    // number's to our left
                    if (rightIndex != currIndex)
                    {
                        rightIndex = currIndex;
                    }
                    else
                    {
                        break;
                    }
                }
            } while (
                array[leftIndex] <= number
                  && number <= array[rightIndex]);

            return -1;
        }
    }
}

At the CodeKata site, Code Kata 1 deals with supermarket pricing. You should go off and ponder it for a spell, then come back.

I used three patterns in my solution: Composite, Decorator, and the Null Object. Composite allows a collection of objects to be treated like one of the objects itself. A LEGO construct is a group of individual LEGOs, but as far as attaching another LEGO, the construct can be thought of as being a single, giant, complex LEGO.

The Decorator pattern embellishes the behavior of an object. Wrapping paper can decorate a box and turn it into a gift. A silicone mit can decorate a hand and keep it from getting burned when grabbing a hot pizza pan out of the oven.

The Null Object pattern establishes a definition for a “null” or empty object. It allows us to gracefully handle situations where there’s no special behavior needed.

A parenthetical comment. I used ducats (Ð) as a currency, because it was a historical currency and I wanted to be free to think of alternate currency approaches. The Ð is a capital eth from Icelandic. (Thanks to Old Jack’s Guild of Rogues for inspiration.)

I see three key abstractions here: an Item, an ItemGroup (itself a Composite of items), and a PricingRule. Items have a cost, the amount needed to buy the item, and a price, the amount needed to sell the item. Each key abstraction will become a class.

The simple price is easy. For this scenario, we can use the Null Object StandardPricingRule, which says that the SalesPrice of an Item is simply equal to its Price. The customer gives me Item.Price ducats, and I give them the item. We’re both happy.

The next challenge is three oranges for a ducat. What happens if I need four oranges for a recipe? How much is the fourth orange? I’ll handle this with fractional money. Each orange is 1/3 of a ducat, as given by a PricingRule. Because some transactions are handled with physical coins, rounding is allowed, to the nearest cent. It’s up to the grocer to structure their pricing so they don’t lose money.

Next, we have bananas at Ð1.99 a pound. It’s clear that some items need to be weighed to be sold, so I’m going to introduce a new class, the WeightedItem, which is an Item that has Weight and Unit properties. Furthermore, WeightedItems will know how to price themselves by unit according to weight.

The last one, buy two melons, get one free, will require the use of the PricingRule. A customer’s shopping cart is a big ItemGroup. The PricingRule will get applied to the shopping cart, thereby affecting all the melons in the cart. Every third melon will have it’s price set to 0. If we’re allowing prices to change, it will therefore become important to know the SalesPrice of an Item, how much it actually sold for. So, I should have said, the price remains the same, but the SalesPrice is set to 0.

The kata comes with some questions, some of which we’ve already answered. As it turned out, there’s nothing special about ducats. Any modern currency (dollars, euros, RMB) will work as well as a ducat, as long as it supports fractional money and allows rounding. (At least that I know of.) (It might be an interesting exercise to come up with an alternate system that didn’t rely on fractional money.)

An audit trail of pricing decisions could be handled by writing to a log whenever a PricingRule is applied. (With the StandardPricingRule, we can require a PricingRule to always be applied.) Are costs and prices the same class of thing? — yes, since I have no need to make them be different.

The last question, about pricing a shelf of cans, is interesting, though. If a shelf of 100 cans is priced using a “buy 2, get 1 free” PricingRule, what’s the value of the shelf? We can apply the PricingRule to the cost of each Item on the shelf (which is an ItemGroup, of course). That will yield the value of the shelf.

Readers, let me know what you think of my solution. And Dave, thanks for posting this and other katas to your blog!