Incongruous alternatives

Overheard when passing a delivery truck parked outside our offices:

"Have you got a lighter, mate? Or a knife?"

Which set my imagination reeling. In what situation could those two implements be possible alternatives?

I can only hope that the courier was wanting, as I guessed, to remove the polythene wrapping from a palette. If he had a trussed up victim hidden in the van whom he wanted to torture then I failed in my civic duty to render aid.

Reporting Progress during LINQ queries

How many times have you had someone use your software, then say to you: "That feature is so much faster now. What did you do?" And in fact all you had done was implement a progress bar, thus harnessing, not the power of the CPU, but the power of psychology!

Reporting progress of an operation is very easy when you have a list of objects that you loop through in a for or foreach block: you just need to know the total number of objects before you start, increment a counter as you process them, and periodically raise an event to notify interested parties (usually your UI) of the percentage progress. But how do you do calculate progress when there are no loops in sight - when you are using LINQ queries to process sequences?

I had a flash of inspiration the other night, followed by an impromptu coding session the next morning when the unusually bright sunlight woke me up early. I thought I'd share the results with you.

LINQ Pipeline Monitors

One way to think of LINQ queries with sequences is as a pipeline, or an oil refinery. You have the data source (often a collection) acting like the oil well, but producing items. Items flow along the pipeline (think of the "."s in the expression as the pipe). Some items are removed from the pipeline by filters - Where clauses; some items are converted to other products - Select clauses; finally, just as oil is cracked, and graded into gasoline and diesel etc. items in LINQ queries are often grouped and sorted. In oil pipelines there are also flow meters, measuring how much oil is going through the pipes. If we can create the equivalent of a flow-meter for LINQ queries, then we've got our means of reporting progress.

What I came up with is an extension method, WithProgressReporting(...), that you can just insert in the appropriate place in your LINQ query. Given an input sequence, it simply passes items through to an output sequence. But as items pass through it counts how many its sees, and calls a lambda expression to report progress against a pre-determined count of the total number of items.

I've created two variants of this.

• The first one ensures that all the items in the sequence have been generated up front, so that it knows how many there are to process; use this if your data source is a collection, or if generating the items takes insignificant time compared with the processing you're going to do.
• The second variant can be used if generating the items in the sequence takes time (so you want to report progress of this part as well), but you know in advance how many there will be: it doesn't attempt to buffer the sequence before passing the items through to the output sequence.

public static class Extensions
{
    public static IEnumerable<T> WithProgressReporting<T>(this IEnumerable<T> sequence, Action<int> reportProgress)
    {
        if (sequence == null) { throw new ArgumentNullException("sequence"); }
    
        // make sure we can find out how many elements are in the sequence
        ICollection<T> collection = sequence as ICollection<T>;
        if (collection == null)
        {
            // buffer the entire sequence
            collection = new List<T>(sequence);
        }

        int total = collection.Count;
        return collection.WithProgressReporting(total, reportProgress);
    }

    public static IEnumerable<T> WithProgressReporting<T>(this IEnumerable<T> sequence, long itemCount, Action<int> reportProgress)
    {
        if (sequence == null) { throw new ArgumentNullException("sequence"); }

        int completed = 0;
        foreach (var item in sequence)
        {
            yield return item;
    
            completed++;
            reportProgress((int)(((double)completed / itemCount) * 100));
        }
    }
}

WithProgressReporting in action

Here's a toy example showing how you might use the first method when you're using a BackgroundWorker to do calculations on a background thread. Focus on line 11, where I'm using WithProgressReporting to report progress to the BackgroundWorker:

public void TestProgressReporting()
{
    BackgroundWorker worker = new BackgroundWorker();
    worker.WorkerReportsProgress = true;
    worker.DoWork += (sender, e) =>
          {
              // pretend we have a collection of 
              // items to process
              var items = 1.To(1000);
              items
                  .WithProgressReporting(progress => worker.ReportProgress(progress))
                  .ForEach(item => Thread.Sleep(10)); // simulate some real work
          };

    worker.ProgressChanged += (sender, e) =>
        {
            // make sure the figure is written to the
            // same point on screen each time
            Console.SetCursorPosition(1, 0);
            Console.Write(e.ProgressPercentage);
        };

    worker.RunWorkerAsync();
    Console.Read();
}

public static class Extensions
{
   public static void ForEach<T>(this IEnumerable<T> sequence, Action<T> action)
   {
       foreach (var item in sequence)
       {
           action(item);
       }
   }
}

Now, stay tuned. I've not exhausted this flash of inspiration yet...

Rating my posts

I've just enabled Blogger's star-rating control on each post of the blog. It would be really helpful if you could let me know what you think of my posts by giving them a mark out of 5. Come on: let your inner teacher out!

I've also enabled Blogger's new inline comment box on each post page, so you've got no excuse for not talking back to me now.

Project Euler Problem 14: Hailstone Numbers

Today we're going to talk about hailstones. No, not the sort that, last week, caused tens of millions of pounds of damage to 30,000 Volkswagen cars in an outside storage area in Germany. Rather the hailstones that are the subject of Project Euler Problem 14: hailstone numbers.

Hailstone numbers are just the kind of thing that fascinate mathematicians. You make them by picking any whole starting number, n, and then repeatedly applying one of the following two rules:

• if n is even, the next number is n/2
• if n is odd, the next number is 3n + 1

Try it; Start with 6. Then you get 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ... . Try it with another number. I bet you find yourself eventually writing 4, 2, 1, 4, 2, 1, ... all over again. If you don't, then, congratulations: you've just solved the Collatz problem, and won yourself at least a £1000 pound reward! You must also have picked a pretty big staring number. Using computers (obviously!) mathematicians have showed that if you kick off the sequence with any number smaller than about 2.7x10¹⁶ you'll eventually get down to the 4,2,1 repeating pattern.

You or I might be inclined to think, based on that evidence, that the sequence will always end in 4,2,1 for any starting number; but no quantity of successful tests would satisfy a pure-blooded mathematician: what if the next generation of computers tested even bigger numbers and found a sequence which didn't terminate like that? Hence the reward, which is being offered for a proof that for every whole number, the sequence generated by these rules eventually reaches 1; or, alternatively, for a demonstration of a number which begins a sequence that doesn't reach 1. This problem has taxed the minds of some of the brightest mathematicians for over 70 years.

But why are they called Hailstone numbers? Have a look at this chart, where I've plotted a few sequences starting with different numbers:

See how the sequences jump up and down? Apparently real hailstones do that when they're growing in the clouds: rising currents of air lift dust particles up into the clouds where they get smothered in ice; this makes them heavy, so they sink. Then the ice melts a little which makes them light enough to be pushed back up again- and so the little hailstones bounce up and down in the clouds getting fatter and fatter, until eventually they get so heavy that they fall to the ground, bouncing there until they come to a complete stop.

Now that you know the what and the why of Hailstone numbers, let's get to Euler's problem, which is to do with the length of sequences of hailstone numbers. We define the length of the sequence as being the number of terms up to the first occurrence of the number 1 (the example above starting with 6 has length 9, for example). Euler asks which starting number under 1 million produces the longest sequence?

A recursive solution

How to solve it? We could do it using an iterator or the Unfold method to generate the sequence, then counting the number of elements in it: but we're not actually interested in the numbers in the sequence, just the length of the sequence.

We can find the length of the sequence which starts at a particular number by finding the next term in the sequence, then adding one to the length of the sequence that starts at that term. In other words we can tackle this using a recursive function; and to make things interesting, we'll make it a recursive lambda function (this isn't gratuitous lambdaisation - you'll see why I've done it in a minute).

Func<long, long> findSequenceLength = null;
findSequenceLength = (long n) =>
{
 if (n == 1) { return 1; }
 var nextTerm = n.IsEven() ? n / 2 : 3* n + 1;
 return findSequenceLength(nextTerm) + 1;
};

The trick to recursive lambda functions, as Eric Lippert pointed out, is to do what I've done in line 1 in the snippet above and assign null to the lambda before giving its actual definition; otherwise the compiler complains that the variable holding the lambda is being used before it is assigned.

Actually I'm misleading you a bit here, because we've not really created a recursive function at all. Thanks to the magic of closures, the lambda that we've assigned to findSequenceLength is really just calling the delegate stored in the variable findSequenceLength -that's why we need to be careful to assign that variable first (Wes Dyer explains more about this, and shows how to do real anonymous recursion in C#). But that very fact creates an opportunity for us: by changing the delegate that is stored in findSequenceLength we can subtly but usefully change the way findSequenceLength works.

Memoization

If you try out a couple of hailstone sequences, you'll soon discover that there are many that start off differently, but converge onto the same (bumpy) glide path down to the (4,2,1) ending. If you start with 24, for example, the third term in the sequence will be 6, and then will continue exactly the same as the sequence starting at 6. This means that once we have encountered one of these 'glide paths' and calculated its length, we really shouldn't need to do the same calculations all over again.

Memoization is a neat trick you can apply to give your lambdas a memory of what they've calculated before (thanks, again, to Wes Dyer for his post on memoization). Have a look at this code:

public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
{
  var cache = new Dictionary<T, TResult>();

  return (T arg) =>
  {
      TResult result;
      if (cache.TryGetValue(arg, out result))
      {
          return result;
      }
      else
      {
          result = function(arg);
          cache.Add(arg, result);
          return result;
      }
  };
}

When you pass a delegate to Memoize, it will return a new delegate that only ever calls your original one if it's called with an argument it has not seen before; otherwise it supplies the answer from its cache of previous results. Obviously you'll only want to use this on delegates whose results are wholly dependent on the input parameters: if you've got a function that uses the current time, for example, caching results will get you stale answers.

So we can do this:

Func<long, long> findSequenceLength = null;
findSequenceLength = (long n) =>
{
 if (n == 1) { return 1; }
 var nextTerm = n.IsEven() ? n / 2 : 3* n + 1;
 return findSequenceLength(nextTerm) + 1;
};
findSequenceLength = findSequenceLength.Memoize();

Now, because the original lambda stored in findSequenceLength is defined to call whatever delegate is stored in the findSequenceLength variable, when we store the memoized version of the lambda back into findSequenceLength the result is a recursive function that can short-cut any calculations for parameters that it has seen before.

I'll let you untwist your brain before I carry on.

Recovered? Now the final answer is just a step away.

Using our findSequenceLength lambda we can calculate the sequence length for any number we like. But to get the final answer to the problem we don't actually want to know the sequence length: we need to know which number generates the longest sequence. So we can't just generate all the sequence lengths and find the maximum over that set. Instead, we'll generate objects containing both the starting number and the sequence length, and use my MaxItem extension method which finds the maximum object in a sequence, using which ever property of the object you grab with a lambda expression to make the comparison. Like so:

return 1.To(1000000)
          .Select(n => new { n, Length = findSequenceLength(n) })
          .MaxItem(info => info.Length)
          .n;

The full code is shown below, together with the code for MaxItem. Or you can download it from my Project Euler page on MSDN Code Gallery.

Oh, and what difference in performance does Memoization make? 0.85 seconds to run the code on my machine compared with 4.4 seconds when I take out the call to Memoize().

[EulerProblem(14, Title = "Find the longest sequence using a starting number under one million.")]
public class Problem14
{
  public long Solve()
  {
      Func<long, long> findSequenceLength = null;
      findSequenceLength = (long n) =>
      {
          if (n == 1) { return 1; }
          var nextTerm = n.IsEven() ? n / 2 : 3 * n + 1;
          return findSequenceLength(nextTerm) + 1;
      };

      findSequenceLength = findSequenceLength.Memoize();

      return 1.To(1000000)
          .Select(n => new { n, Length = findSequenceLength(n) })
          .MaxItem(info => info.Length)
          .n;
  }
}

public static T MaxItem<T, TCompare>(this IEnumerable<T> sequence, Func<T, TCompare> comparatorSelector) where TCompare : IComparable<TCompare>
{
  T max = sequence.First();
  TCompare maxComparator = comparatorSelector(max);

  foreach (var item in sequence)
  {
      var comparator = comparatorSelector(item);

      if (comparator.CompareTo(maxComparator) > 0)
      {
          max = item;
          maxComparator = comparator;
      }
  }

  return max;

}