Code Kata: Kata Two

I haven’t been coding much at work recently, so I decided that I need to sharpen the saw a bit and exercise.

I decided to start with some Code Kata. The first one is somewhat an academical problem: implement binary search in five different ways.

Here is my first solution, the iterative way:

        //Classic iterative method
        public int Chop1(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            var lower = 0;
            var upper = collection.Count() - 1;
            int index, candidate;

            while (lower != upper)
            {
                index = lower + ((upper - lower) / 2);
                candidate = collection.ElementAt(index);

                if (candidate == element)
                {
                    return index;
                }
                else if (candidate < element)
                {
                    lower = index + 1;
                }
                else //if (candidate > element)
                {
                    upper = index;
                }
            }

            return (collection.ElementAt(upper) == element) ? upper : -1;
        }

I was actually scared at the time it took me. This is the kind of problem you are expected to solve in 5 minutes flat at university, but the lack of programming puzzles lately soften my brain. On the bright side, I challenged myself to get it right without compiling before being absolutely sure that the code would pass the tests, which it did. This involved some scratching paper to test the different corner cases, but I felt good when the green light of passing tests appeared.

Here is my second solution, recursive and passing slices of the original array:

        //Recursively passing smaller slices of the initial array
        public int Chop2(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            var index = collection.Count() / 2;
            var candidate = collection.ElementAt(index);

            if (candidate == element)
            {
                return index;
            }
            else if (candidate < element)
            {
                var offset = index + 1;
                var position = Chop2(element, collection.Skip(index + 1));
                return position > -1 ? offset + position : -1;
            }
            else //if (candidate > element)
            {
                return Chop2(element, collection.Take(index));
            }
        }

After finishing this one, I started thinking about it and found it very funny that this came more naturally than a recursive function using boundaries inside the array. I tend to use LINQ a lot when I code in C#, and I guess this is where it shows. The good news is that this led me to the third possible solution, which would have been second if I was just out of university.

Third solution, recursive and passing arrays boundaries:

        //Classic recursive method, passing boundaries around
        public int Chop3(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            return SubChop3(element, collection, 0, collection.Count() - 1);
        }
        //...and its sub method required for passing boundaries around
        private int SubChop3(int element, IEnumerable<int> collection, int lower, int upper)
        {
            //End case: lower == upper
            if (lower == upper)
            {
                if (collection.ElementAt(lower) == element) return lower;
                else return -1;
            }

            var index = lower + ((upper - lower) / 2);
            var candidate = collection.ElementAt(index);

            if (candidate == element)
            {
                return index;
            }
            else if (candidate < element)
            {
                return SubChop3(element, collection, index + 1, upper);
            }
            else //if (candidate > element)
            {
                return SubChop3(element, collection, lower, index);
            }
        }

Nothing too fancy here.

I don’t have a 4 and 5 yet, but I already have one idea that is very challenging: continuation passing style. I was also tempted to implement one version using TPL, but it wouldn’t be very different from the recursive methods, so I am not sure… Maybe using a custom partitioner?

A Tale of Code Review…

A few years ago, I was working on a project where our client asked for code review by experts from another company. The idea behind this was to assess that we were doing a good job, fair enough. Since they didn’t have any in-house experts on the matter, the only choice left was to hire experts on the topic to review our work.

I don’t remember all the details of this code review, but I have two remarks that distinctly remember because they shocked me.

No Need to Have a Static Private Object to Lock On, Just Lock the Type

Now when I was told that, I was hit very hard because I was certain that the language specifications specifically mentioned that as a bad practice. Turns out that I remembered well: http://msdn.microsoft.com/en-us/library/c5kehkcz.

The good thing is that this one, I managed to avoid having to change it in the code. I don’t remember very well the why, but it was a small victory.

Don’t Use the “+” Operator on String, Use String.Concat

This one was also a good one. When I was told that I lost all hopes that these experts would be useful, as this comment revealed their ignorance of the C# compiler behavior. Not that I think everyone should know that, but I don’t consider myself as a C# guru, but I believe that any enthusiast that played with reflector a little bit should have noticed that.

Not only the “+” operator is replaced by String.Concat call if the content of both operand is not known at compile time, but if both are known at compile time then it is simply replaced by one single String! So, applying this guideline did reduce performances… Not to a noticeable way, I agree, but having to go in your code and replace good stuff with something not as good is not a pleasant experience.

The “fun” part is that actually we also had the String.Concat comment for the “+=” operator. So, one of my colleague  went through the code and replaced all the

s1 += s2;

by

String.Concat(s1, s2);

which is wrong since the return value is ignored, so original string is not modified. Not only this was a pointless change, but bugs were introduced when doing that mindless task.

Conclusion

I don’t know if there is anything to be concluded from this experience. In my case, the advices provided were mostly useless if not harmful. My personal conclusion is that real experts are a rare breed, and it’s not because someone labeled as an expert and expensive that he is. Even if he comes from a big corporation…

Now there is also a conflict of interest here. When an expert is dispatched on this kind of mission, it would be very difficult to justify his price if he didn’t have anything to comment on. So whatever you have done, the expert will have comments and if quality is good chances are that these comments will be useless. Next time, I’ll put some ducks here and there. Needless to say, if the customer is clueless about the technology, he will take the side of the expert. Which is perfectly understandable, because for that particular manager, not following the expert’s advice can only result in a lot of pain if something happens, even if completely unrelated to the expert’s comments. Another example of C.Y.A.

My third conclusion what that I probably was expecting too much from these experts. To me, the word “expert” means people like those on the top reputation page of StackOverflow.

Diablo III

I have been playing the beta for a while now and maxed out a barbarian.

Diablo002

I have to say that it’s still Diablo, nothing changed much compared to the first two. But that’s why I like it I guess!

Plus the little exclusivity of playing the closed Beta, too!

Version Control by Example

A few weeks ago, I “requested” a free copy of the book Version Control by Example by Eric Sink.

Today, while coming home from work, I found a printed copy in my post box.

Thanks Eric!

Io, Day 3

Final day with Io. It’s been quite a ride, and even if I don’t think I grasp everything that Io is, I consider playing with Io a little bit on my own later because of it’s potential, especially in DSL.

Enhance the XML program to add spaces to show the indentation structure
Builder := Object clone
Builder depth := 0
 
Builder forward := method(
  prefix := "  " repeated(self depth)
  writeln(prefix, "<", call message name, ">")
  self depth = self depth + 1
  call message arguments foreach(arg,
    content := self doMessage(arg)
    if(content type == "Sequence", writeln(prefix, "  ", content))
  )
  self depth := self depth - 1
  writeln(prefix, "</", call message name, ">")
)
 
Builder html(head(title("Programing languages")), body(ul(li("IO"), li("Lua"), li("JavaScript"))))
Create a list syntax that uses brackets
curlyBrackets := method(
  l := List clone
  call message arguments foreach(arg,
    l append(doMessage(arg))
  )
  return l
)

Next Page →