Bill Blogs in C#

I received this question in email from one of my readers, and I thought it would be of general interest:

I find myself with two arrays of the same size and I want to create a third that combines

each element. What I want is something similar to

var S3 = S1.foreach(S2, (s1, s2) => s1 + s2);

this would give S3[i] = S1[i] + S2[i]; for all i

Since this is a common pattern, I was wondering if you know what is a good functional solution.

Thank you for any input you would have

I wrote a couple methods that makes this rather quite simple.  First, I wrote an extension method that merges two sequence:

   1: public static IEnumerable<T> Merge<T>(this IEnumerable<T> leftSequence, 

   2:     IEnumerable<T> rightSequence,

   3:     Func<T, T, T> mergeFunc)

   4: {

   5:     IEnumerator<T> leftEnumerator = leftSequence.GetEnumerator();

   6:     IEnumerator<T> rightEnumerator = rightSequence.GetEnumerator();

   7:     while (leftEnumerator.MoveNext() && rightEnumerator.MoveNext())

   8:     {

   9:         yield return mergeFunc(leftEnumerator.Current, rightEnumerator.Current);

  10:     }

  11: }

Once that's done, it provides almost exactly the syntax you requested:

   1: int[] leftVector = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

   2: int[] rightVector = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

   3:  

   4: var sum = leftVector.Merge(rightVector, (x, y) => x + y).ToArray();

   5:  

   6: foreach (var value in sum)

   7:     Console.WriteLine(value);

There are a few caveats here.  This doesn't test for any errors if the two vectors aren't the same length. That may or may not matter for you. I like this idiom, because you can do other operations on sequences as well.  Here's multiply:

   1: var sum = leftVector.Merge(rightVector, (x, y) => x * y).ToArray();

I hope that helps.

Well, I'm back from the MVP Summit, and it seems that tradition mandates a summary of the trip.

But there is one problem: The best content was all under NDA. Most MVPs spend their time with members of the product team for their award, and other teams that are related. For me, that obviously means the C# language team, and other Developer Tools teams.

The NDA nature of the meetings means that everyone blogs about the parties, the time in the bar, the friends. Those are great fun, but I don't want to give everyone the impression that the MVP summit is one big party.

Really, it's the time when the Microsoft Product groups give us a good look behind the curtain and show us what they are thinking of building and ask for our feedback on each and every one of the ideas they are discussing.

It's my favorite MS based conference.

It's been a while coming, but we finally convinced several of our new and brilliant folks to start blogging.

I've added them all to the blog roll, but here they are, along with some editorial comments from your host:

(Order is alphabetical by blog address and does not signify anything else)

Anne Marsan is a Mechanical Engineer by education, but has been writing software for that market for some time. She has a deep understanding of the darker corners of higher math, and how computers still sometimes don't do it correctly. It's probably significant that she's doing the Euler problems in Matlab.

Marina Fedner is a recent Carnegie-Mellon graduate that is keeping us older folks are learning new stuff everyday.

Mike Woelmer is a farmer turned silverlight developer, by way of several years of game development and medical imaging development. His first blog post discusses that journey. He's had quite the history

Bill Heitzeg is an engineer of all trades and styles. He's also got a great feel for the business issues of software development.

It's a lot of interesting discussions, and a good taste of what kind of culture we have around here.

Now if we can just get Chris, Nate and Alex blogging as well.

Euler Problem six asks you to find the difference between the sum of squares and the square of the sum for the natural numbers 1 through 100.

I took the easy route, and made a brute force implementation in C#. There are a couple new bits of LINQ syntax here. This query creates two different anonymous types. One for the number / square pair, the second is the aggregate answer for the sum and the sum of squares.

The important points are that this is done in a single iteration. It's pulling each value in from the initial sequence and doing all the calculations in one iteration of the sequence:

There you go. Another simple bit of code.

Well, it's time to post another solution and look at how LINQ and C# 3.0 can create elegant code for these problems.

The fifth problem asks you to find the smallest number that is divisible by all the natural numbers from 1 through 20. You can trivially find the answer like this:

    1 private static void BruteForce()

    2 {

    3     var divisible = (from n in Enumerable.Range(1, int.MaxValue)

    4                     where (n % 2 == 0

    5                     && n % 3 == 0

    6                     && n % 4 == 0

    7                     && n % 5 == 0

    8                     && n % 6 == 0

    9                     && n % 7 == 0

   10                     && n % 8 == 0

   11                     && n % 9 == 0

   12                     && n % 10 == 0

   13                     && n % 11 == 0

   14                     && n % 12 == 0

   15                     && n % 13 == 0

   16                     && n % 14 == 0

   17                     && n % 15 == 0

   18                     && n % 16 == 0

   19                     && n % 17 == 0

   20                     && n % 18 == 0

   21                     && n % 19 == 0

   22                     && n % 20 == 0

   23                         )

   24                     select n).First();

   25     Console.WriteLine(divisible);

   26 }

But don't do that. It's very slow. Let's think a bit about the math, and the answer gets much easier. If you remember middle school math, you are being asked to find the greatest common divisor for all numbers 1-20. The unique factorization theorem is what you need here. It states that every number can be written in exactly one way as the product of prime numbers. The greatest common divisor can be found by multiplying the highest powers of each prime factor. In code, it's a little easier to turn the definition around and peel off prime factors from every number in the list. It's faster and simpler than finding all the prime factors.

You start with a list like this: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1 really doesn't do much, so we'll start with 2. Keep the 2, and replace every number greater than 2 that is divisible by 2 with that number divided by 2:

1, 2, 3, 2, 5, 3, 7, 4, 9, 5

Move to the next number (3). Repeat:

1, 2, 3, 2, 5, 1, 7, 4, 3, 5

Move to the next number (another 2). Repeat:

1, 2, 3, 2, 5, 1, 7, 2, 3, 5

Continue until done:

1, 2, 3, 2, 5, 1, 7, 2, 1, 1

Multiply: 2520

That gives us this algorithm:

    1 private static void Better()

    2 {

    3     var numbers = Enumerable.Range(1, 20).ToArray();

    4     // remove common factors:

    5     for (int index = 0; index < numbers.Length; index++)

    6         for (int subIndex = index + 1; subIndex < numbers.Length; subIndex++)

    7             if (numbers[subIndex] % numbers[index] == 0)

    8                 numbers[subIndex] /= numbers[index];

    9 

   10     var answer = numbers.Aggregate(1, (product, number) => product * number);

   11 

   12     Console.WriteLine(answer);

   13 }

But you know what. I don't like those loops. I'd rather write methods that operate on a sequence. It's another rather simple example of tail recursion. For any sequence, peel off the first number. Then, return that number followed by the rest of the sequence divided by that first number, where possible. Pipe the remaining sequence back into the same function:

   11 private static void Best()

   12 {

   13     var numbers = Enumerable.Range(1, 20);

   14 

   15     var answer = numbers.LeastCommonFactor().Aggregate(1,

   16         (product, number) => product * number);

   17 

   18     Console.WriteLine(answer);

   19 }

   20 

   21 private static IEnumerable<int> LeastCommonFactor(this IEnumerable<int> list)

   22 {

   23     // Stop if the list is empty:

   24     if (!list.Any())

   25         yield break;

   26 

   27     int factor = list.First();

   28     yield return factor;

   29 

   30     var remaining = from item in list.Skip(1)

   31                     select (item % factor == 0) ? item / factor : item;

   32     foreach (int item in remaining.LeastCommonFactor())

   33         yield return item;

   34 }

Now that's a simple, elegant algorithm. And, it runs quite a bit faster than the brute force version. Stay tuned for more toward the end of the week.

I've had some comments on the Euler problems, so I'm assuming there is some interest. There's also been interest among other developers in our office.

Darrell Hawley has started solving the problems in Python.

Marina Fedner has started solving the problems in Ruby.

I highly recommend reading.  It will help you grow as a developer to see how other languages support different idioms that make some of these problems easier or harder.

You'll learn more and discover how to add more idioms to your own language.

The fourth Euler problem asks you to find the largest palindrome number that is the product of two three digit numbers. For example, the number 919 is a palindrome: it's the same forward and backwards.

To solve this problem, we need to find the product of all combinations of three digit numbers. Well, if you remember your probability, this is a combinatorial problem. Order doesn't matter. That limits the number of combinations.

Next, we need to find palindromes. A little string conversion makes that simple. You can convert the number to a string, then see if the string is equal to its reverse. Strangely, there isn't a method in System.String that can reverse a string. But, there is a Reverse() extension method that's in scope.

Well, let's look at the code:

    1 static void Main(string[] args)

    2 {

    3     var allProducts = from x in Enumerable.Range(100, 900)

    4                       from y in Enumerable.Range(100, 900)

    5                       where x <= y

    6                       let product = x * y

    7                       orderby product descending

    8                       select new { x, y, product };

    9 

   10     var palindrome = (from n in allProducts

   11                        let chars = n.product.ToString()

   12                        let reverse = new string(chars.Reverse().ToArray())

   13                        where chars == reverse

   14                        select n).First();

   15     Console.WriteLine("{0}, {1} => {2}", palindrome.x, palindrome.y,

   16         palindrome.product);

   17 

   18 }

The first query is to generate all products of three digit numbers. Notice that the where clause removes permutations that are the same as two numbers. For example, 251*126 would have already been computed from 126*251. Next, notice the 'let' clause. That assigns a local variable in the query expression so that you don't have to compute the product more than once. While we're at it, we order the values by the products in descending order.

The next query finds the palindromes from all those products. As I said earlier, I do this by converting the product to a string, then comparing the string to its reverse. As with the earlier query, I use the let clause to cache some local results and avoid recomputing values.

You'll need to run the code yourself to see the answer.

Earlier this week, Open XML won ISO approval.  By any objective measure, it won handily.  86% of the participants voted for the standard.

Does that mean that 16% of the voting countries are run by IBM officials?

One could make the case that it does.  Jan van den Beld's post provides far more evidence more eloquently than I ever could:  http://janvandenbeld.blogspot.com/2008/04/hypocrisy.html.  A few highlights:

 "I can see why IBM opposes more voices (at least those that don’t agree with its commercially motivated views). It has enjoyed unparalleled influence in international standardization for decades and may not now like more voices and decision makers in this process. Its allies could not have been clearer about that commercial agenda– to force the purchase of their products by blocking governments from procuring Microsoft Office, regardless of technical merit or actual demand."

"When IBM talks about independence, it really means that national standards bodies should be independent of anyone who disagrees with IBM’s position.

But, the only way to get the full picture is to read his post, including the evidence to which he provides links.

For my own standpoint, I have to look at this from the technology standpoint. I've looked inside a few Office XML documents. They are not simple, but they are understandable (if you understand XML). Can any company (or individual) create a parser to read or write Office XML documents? Sure. What's stopping you?  Your technical skill might, but legal restrictions and closed formats can't.  And to me, data transparency is more "open" that code transparency. If I can see the data (in XML format, possibly) I can certainly figure it out. Even if I can't see the internal algorithms inside Office, I can work with it's files. That's much more important than being able to see the code. Are you, or your customers, going to re-write your office apps?  Probably not. But, does an open format make changing vendors, or creating more addons easier?  Certainly. Open XML gives us that.

In fact, at this point, I would make the case that it's easier to work with office documents stored in Open XML than it is to work with google docs stored in the cloud. Can you program against google docs? Can you programmatically retrieve your data? If so, can you understand the internal format, and process those documents with your own algorithms? I don't believe so.

When you design your API, make it easy to use and hard to misuse. Brad Abrams quotes Rico Mariani on the Pit of Success here: http://blogs.msdn.com/brada/archive/2003/10/02/50420.aspx 

The key point:

"we want our customers to simply fall into winning practices by using our platform and frameworks.  To the extent that we make it easy to get into trouble we fail." - Rico Mariani

public TcpClient(IPEndPoint addr) { /* ... */ }
public TcpClient(string hostName, int Port) { /* ... */}

Here are my notes on the third Project Euler problem. The problem is "What is the largest prime factor of the number 600,851,475,143?"
Once again, this is a problem that is best solved creating some simple LINQ queries. From the outside, this query generates the list of all prime factors in the very large number:

long largeNumber = 600851475143;
var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber)
                      orderby p descending
                      select p;
foreach (var f in allPrimeFactors)
    Console.WriteLine(f);

As with the other first two problems, the query is fairly simple. Just grab the prime factors, and order them in descending order.
The work is in the Primes class. This class uses tail recursion to find all prime factors. It starts with the smallest prime number (2), and removes all copies of that number as a factor. Once all those are returned, it will look at the next larger factor and remove those.
A couple quick notes:
1. The algorithm, as written, must start with the smallest prime number. Otherwise, it will find non-prime factors.
2. It doesn't matter that MorePrimeFactors looks at possible factors that aren't prime. They won't appear because any smaller prime factors have already been removed. (for example, 6 won't appear because any factors of 2 or 3 have already been removed).
public static class Primes
{
    // Find all prime factors.
    public static IEnumerable<int> PrimeFactors(long number)
    {
        // Start by removing the lowest prime (2)
        return MorePrimeFactors(number, 2);
    }
    // This recursive method finds all prime factors.
    private static IEnumerable<int> MorePrimeFactors(long number, int factor)
    {
        // Find the next prime factor
        while (number % factor != 0)
            factor++;
        // Return it.
        yield return factor;

        // look again...
        if (number > factor)
            // recursively look for this factor again, using Num/factor
            // as the new big number
            foreach (int factors in MorePrimeFactors(number / factor, factor))
                yield return factors;
    }
}
Note that the PrimeFactors algorithm is not linq based, but it does rely heavily on custom enumerators.

I kept looking for an updated version of CopySourceAsHTML (http://www.jtleigh.com/people/colin/software/CopySourceAsHtml/)  that would work with Visual Studio 2008. (which is why some of my recent code snippets don't look the way I want). 

While Colin & J.T. Leigh did not release any updates, Guy Burstein did.  You can get a new version here: http://blogs.microsoft.co.il/blogs/bursteg/archive/2007/11/21/copy-source-as-html-copysourceashtml-for-visual-studio-2008-rtm.aspx

The second Euler problem asks you to find the sum of all even valued terms in the Fibonacci sequence which do not exceed 4,000,000.

Let's look at the solution from the outside in. Here's the query that finds the answer:

var EvenFibNumbers = (from n in Enumerable.Range(1, MAX)
                      let value = FibonacciSequence.Fibonacci(n)
                      where value % 2 == 0
                      select value).TakeWhile(n => n < MAX);

var answer = EvenFibNumbers.Sum();

There are a couple notes on the performance metrics used here:

The TakeWhile() method call does short circuit the query so that it does not continue calculating unneeded numbers. I could optimize this by trying to be very careful about which Fibonacci numbers I calculate, but it really doesn't matter. TakeWhile means I don't calculate them anyway. (Well, to be strictly accurate, I do calculate one more than I need, but that's no big.

Next, note the "let" statement in the query. I use that to avoid calculating the Nth Fibonacci number more than once. It just introduces a new local variable (value) and assigns it to the result of Fibonacci(n).

On this algorithm, there are some other interesting changes you could make. If you examine the Fibonacci sequence carefully, you'd see that every 3^rd Fibonacci number is even. You could, possibly, save some work by using that fact. Because of how the Fibonacci sequence is calculated, I don't think it matters. (Comment if you have a way to optimize it that I'm not seeing).

What's more interesting, to me, is how I wrote the Fibonacci sequence. I used a mix of Functional and Object Oriented techniques. (For a more functional approach, read Dustin Campbell's article on memorization: http://diditwith.net/PermaLink,guid,7191176b-c72a-49db-986e-466845665fa1.aspx)

public static class FibonacciSequence
{
    // Store all Nth Fibonacci numbers that have been calculated.
    private static Dictionary<int, long> FibnocciNumbers = new Dictionary<int, long>();

    // Return the Nth Fibonacci number.
    public static long Fibonacci(int n)
    {
        long answer;
        // If it's already been calculated, just return it.
        if (FibnocciNumbers.TryGetValue(n, out answer))
            return answer;

        // The first and 2nd numbers are 1.
        if (n < 2)
            answer = n;
        else
            // It's the sum of the previous two numbers.
            answer = Fibonacci(n - 1) + Fibonacci(n - 2);
        // Store...
        FibnocciNumbers.Add(n, answer);
        // return
        return answer;
    }
}

			

You'll note that this class uses a recursive method to calculate the Nth Fibonacci number. However, it will only calculate each number in the sequence at most once. Once a calculation has been performed, the answer is stored in a private dictionary for later use. Rather than try and twist your brain around many of the more advanced Functional programming concepts, using C# 3.0, you can mix good old fashioned oo programming with good old fashioned functional programming. Cool!

Stay tuned for more on Friday, when I write up the notes on problem 3.

I am starting a new series. A friend recently pointed me at the Project Euler problems. You can see the project here: http://projecteuler.net/

As I finish them, I'll post an explanation of the problem and the code here. I've also posted the code on MSDN Code Gallery. As I finish a week's worth of code, I'll post a new release of source code there.

A few ground rules:

1. I'm not going for the 'best' or 'most efficient' solution. I'm using this to demonstrate significant C# 3.0 features. If you have a different preferred algorithm, post it yourself. In fact, you can register at Project Euler and post your own code.
2. I will post blog entries more or less at the same time I update the code. You might see the code before I discuss it. If you don't want spoilers, don't do it.
3. I will discuss the algorithms and the answers freely. If you want to figure out the problems yourself, don't read too far before you try it yourself. Or, once again, signup at Project Euler and try yourself before I post my answers.
4. I will do the problems in order, so if you're interested in avoiding spoilers, you can work in order, and stay ahead of where I'm at. (The first three problems took me less than 2 hours from start to finish).

Ok, with that out of the way, here's the code for the first problem. (Really, it's not that hard. I'm not giving much away here). In the first problem, you need to find the sum of all natural numbers below 1000 that are multiple of 3 and 5.

It's one (or two) lines of code in C# 3.0:

var nums = from n in
           Generators.NumberSequence(0, 1000)
           where ((n % 3 == 0) || (n % 5 == 0))
           select n;
var answer = nums.Sum();

I should also show you the code for NumberSequence. I figure I'll need sequences of numbers fairly often in this projecxt, so I pulled that into a library:

public static IEnumerable<int> NumberSequence(int from, int to)
{
    do
    {
        yield return from++;
    } while (from < to);
}

Yes, this method assumes that from is less than to. Seems like a reasonable assumption at this time.

You can download the code for the first three problems here: http://code.msdn.microsoft.com/EulerCSharp

Note that I said 3 problems. I uploaded the code for the first three problems on Project Euler, so you may want to wait if you want to avoid spoilers.

My alma mater, The University of Illinois, just announced a joint venture with Microsoft, Intel, and the University of California at Berkeley which will enable commodity computer systems to make use of parallel computing techniques previously in the exclusive realm of super computers. You can read more here:  http://www.upcrc.illinois.edu/news_031808.html

Wicked cool.

That, combined with reseach by compiler teams to make parallel computing more accessible is going to lead to a wild future.

Dave Donaldson asks "Do you write software at homer like you do at work?"

Dave wonders if we use the same discipline writing software at home (for our own use) that we do at work. I think the question is great, but I'm concerned about those developers that answer yes without thinking. In fact, should you use the same tools at home that you use at work? I'll answer all his questions for my own development, and I'll explain why I make the choices that I make. Here are the questions:

• Do you have a source code repository?
  [BW] Yes. I make mistakes and I want to backup.
• Do you use it?
  [BW] Yes.
• Do you still check-in many times while coding (like hopefully you do at work), or do you wait and do one massive check-in before you go to bed?
  [BW] Somewhere between those. This will become more apparent as you read on, but think about why you checkin often at work. Does someone else need your work? Not integrating (via checkin) often means that different branches (each developer's working copy) get farther away from each other.
• Do you have a task management system?
  [BW] Yes. I use the same notecards we use at work.
• Do you have a bug tracking system?
  [BW] bugs = tasks, therefore they go on cards.
• Do you assign bugs a severity level?
  [BW] Yes. But, it's a simple one. "Fix it now", "Fix it later", "Do this when I have nothing better to do".
• Do you set milestones?
  [BW] That depends. Why am I doing the development? What's the pain? The milestones (if any) depend on why the work is being done.
• Do you hold yourself to them?
  [BW] Related: If I was writing a Bracket Management system now, I've got a real external deadline approaching. It's immovable. However, if I'm just experimenting, no such external pressure applies.
• Do you use the same types of patterns?
  [BW] Sure.
• Do you apply a separation of concerns?
  [BW] As often as I do at work. Decoupling has both benefits and costs. Which is greater in this instance? (The same analysis should apply at work).
• Do you write clean code at home, or is it a mess just to get it done?
  [BW] Habits are permanent. You have to follow the same practices at home, or the bad practices will bleed through.
• Do you write tests?
  [BW] yes.
• Do you run them?
  [BW] yes.
• Do you have a build server?
• Do you use it?
• Do you practice continuous integration?
  [BW] No on all three. There's a reason. Why do you use these tools at work? I'll submit that it is to facilitate collaboration among the team. With a team of one you don't have the same benefits. A separate build server does ensure that I haven't forgotten to add files to the repository. Visual SVN does the same thing. So does delete / update / build (make a backup first). I have multiple development machines, and I use online folders to help me keep them in sync. That means I'm not concerned about a catastrophic failure on my desktop losing work. (See 'check in often' above). Continuous integration is the same. By definition, in a one person-development effort, if it builds on my machine, it builds on the build server. Running my tests on every build gives me the same results.
  Now, I will submit that if I think of the CI server as an automated test server rather than as an automated build server, I start to think about possible benefits. Every checkin runs the test(s) in the background, and I'm continuing to work. But, that changes my habits. At work, I write tests, write code, see tests pass, check in. At the moment, without a CI server, I do the same thing. If I moved to using a CI Server (thinking it is the test server), my workflow might change to write tests -> check in (see CI build fail) -> write code -> Check in -> repeat until CI build passes (meaning all the tests pass). I don't think I want to adopt that process in my work environment. I'd likely break the build repeatedly every day. That's not good

My purpose in answering Dave's question is to get more people thinking. Underlying Dave's post are some values. If you follow bad habits in less structured environments, those same habits will creep into your more structured environments. Practice doesn't make perfect, practice makes permanent. Every time you break your own rules, you'll reinforce bad habits. That's especially true when no one else is watching you. Countering that is an understanding of why you follow certain processes. If the justification for a particular process doesn't apply, neither should the process. This is true at home, at work, and at other work locations. As I said above, I don't have a separate build server at home. I don't see the benefits on a single person project. At home, and at our office (< 15 developers) we use note cards to track tasks and bugs. That's a low-friction and reasonable answer for a small shop that's located in the same office (although folks do telecommute often, that's what phones are for.) I'm fully aware that the notecards don't scale to a large, or more distributed environment. That doesn't mean I'm against other tools, just that I don't believe they would be appropriate for us now.

By way of analogy, I use a basic claw hammer to hang a picture. That's the best tool for the job. When I'm helping to build sets, and we need to build several platforms and flats, I use the air hammer. Both choices are correct. It would take more time to setup the compressor, uncoil the hoses, get the compressor going and so on… I'm done using the hand tool before I even get the air hammer turned on. Of course, I can finish a whole platform in less time (including setup) using the air hammer. It's a matter of evaluating the goals, and picking the write tool for the job. The analogy still works for those practices where I use my normal work structure. Even for hanging the picture, I get the hammer. I don't use the nearest heavy object (like my wife's crystal candlestick). The cost of using the wrong tool (as opposed to the right lightweight tool) is rather high.