In my previous post about the subject, I presented one approach to wiring up the BusyIndicator control from the Silverlight Toolkit using some fancy Caliburn.Micro wizardry… Ok, maybe it was not wizardry. It was actually simply diving into the extensibility model that comes with the framework.
I also said I already had my next solution figured out, and I would present that in this post. Well… I lied. I didn’t have it all figured out, and it took some experiments to get it right. I’m not completely satisfied yet, but I think the solution I am about to show you will offer just a little bit more flexibility than the previous one. I do warn you, It’s there’s a good wall of text incoming. I will put the code on Github soon(ish), which I will announce in a future post. The project will contain both approaches (and possibly new ones if I come up with something else). But for now, just read through this ;-).

First, we’ll start off with a stock Caliburn.Micro Silverlight application. Just like last time, we’ll add a button to the view and wire it up to the view model. For completeness sake, here’s the code for the view and the viewmodel:

View:

<UserControl x:Class="Approach2.ShellView"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:toolkit="http://schemas.microsoft.com/winfx/2006/xaml/presentation/toolkit">

    <toolkit:BusyIndicator>
        <Grid Background="White">
            <Button x:Name="DoSomething" Content="Do something" Height="20" Width="100" />
        </Grid>
    </toolkit:BusyIndicator>

</UserControl>

ViewModel:

using System.Collections.Generic;
using System.ComponentModel.Composition;
using Caliburn.Micro;

namespace Approach2 {
    [Export(typeof(IShell))]
    public class ShellViewModel : IShell
    {
        public IEnumerator<IResult> DoSomething()
        {
            yield return new SleepRoutine(1000);
            yield return new SleepRoutine(1000);
            yield return new SleepRoutine2(1000);
            yield return new SleepRoutine2(1000);
            yield return new SleepRoutine(3000);
        }
    }
}

Note that the BusyIndicator control in the view no longer has any bindings. It doesn’t even need a name! The view model contains a method which returns a bunch of co-routines, which are basically the same except for one minor detail:

public class SleepRoutineBase : IResult
{
    private readonly int _milliseconds;

    public SleepRoutineBase(int milliseconds)
    {
        _milliseconds = milliseconds;
    }

    public void Execute(ActionExecutionContext context)
    {
        Task.Factory.StartNew(() => Thread.Sleep(_milliseconds))
            .ContinueWith(x => Completed(this, new ResultCompletionEventArgs()));
    }
    public event EventHandler<ResultCompletionEventArgs> Completed;
}

[BusyMessage("Sleeping...")]
public class SleepRoutine : SleepRoutineBase
{
    public SleepRoutine(int milliseconds) : base(milliseconds)
    {
    }
}  

public class SleepRoutine2 : SleepRoutineBase
{
    public SleepRoutine2(int milliseconds) : base(milliseconds)
    {
    }
}

I’ve extracted the functionality in a base class (just for the example, this is obviously not a REAL scenario). The only difference is that this time, we’ve annotated the co-routine with the BusyMessage attribute instead of the method on the view model. This means that instead of having a single status message for the whole sequence, we can show a message for each step in our action. However, hooking this up is a bit different from the previous approach.

First, a bit of explanation is required. What actually happens when you trigger an action, which fires off a message which returns an IEnumerator of IResult? Well, to put it simply, the framework takes the IEnumerator, passes it into a function called CreateParentEnumerator on the Coroutine class, and executes that. Internally, the SequentialResult class will make sure that all co-routines in the IEnumerator will execute sequentially. Luckily, the Caliburn.Micro framework allows us to easily change or extend this functionality by exposing the function as a field, which allows us to do something like this:

Coroutine.CreateParentEnumerator = e => new BusyIndicatorResult(e);

This means that instead of using a SequentialResult, the framework will now use my own IResult instead. This IResult also simply executes a sequential result, but not before doing some transformations here and there. Every co-routine contained in the IEnumerator will be wrapped in a decorator which will activate the BusyIndicator when needed, and it resets the BusyIndicator at the end. The code is not that complicated, although we do need to do a lot through the Dispatcher because there’s no guarantee that the co-routines will all run on the UI thread:

class BusyIndicatorResult : IResult
{
    private BusyIndicator _busyIndicator;
    private SequentialResult _sequentialResult;

    private static IEnumerator<IResult> Decorate(IEnumerator<IResult> source)
    {
        while (source.MoveNext())
        {
            yield return new BusyIndicatorDecorator(source.Current);
        }
    }

    public BusyIndicatorResult(IEnumerator<IResult> enumerator)
    {
        _sequentialResult = new SequentialResult(Decorate(enumerator));
    }

    public void Execute(ActionExecutionContext context)
    {
        _busyIndicator = context.Source.GetAncestor<BusyIndicator>();
        _sequentialResult.Completed += ResetBusyIndicator;
        _sequentialResult.Execute(context);
    }

    public event EventHandler<ResultCompletionEventArgs> Completed;

    private void ResetBusyIndicator(object sender, ResultCompletionEventArgs e)
    {
        (sender as IResult).Completed -= ResetBusyIndicator;
        if (_busyIndicator != null)
        {
            Deployment.Current.Dispatcher.BeginInvoke(() => _busyIndicator.IsBusy = false);
        }
        Completed(this, e);
    }
}

And the decorator class:

class BusyIndicatorDecorator : IResult
{
private readonly IResult _innerResult;
private BusyIndicator _busyIndicator;

public BusyIndicatorDecorator(IResult innerResult)
{
    _innerResult = innerResult;
}

public void Execute(ActionExecutionContext context)
{
    var statusMessage = _innerResult.GetType().GetAttributes<BusyMessageAttribute>(true).FirstOrDefault();
    SetBusyIndicator(statusMessage, context);
    _innerResult.Completed += OnComplete;
    _innerResult.Execute(context);
}

private void SetBusyIndicator(BusyMessageAttribute statusMessage, ActionExecutionContext context)
{
    Deployment.Current.Dispatcher.BeginInvoke(() =>
    {
        _busyIndicator = context.Source.GetAncestor<BusyIndicator>();
        if (_busyIndicator != null)
        {
            _busyIndicator.IsBusy = statusMessage != null;
            _busyIndicator.BusyContent = statusMessage == null ? "" : statusMessage.Message;
        }
    });

}

And finally, a little helper class I use to find the BusyIndicator control somewhere upstream in the visual tree, starting at the element which triggered the action:

internal static class VisualTreeExtensions
{
    public static T GetAncestor<T>(this FrameworkElement source) where T : class
    {
        var current = source;
        while(current != null)
        {
            if (current is T) return current as T;
            current = current.Parent as FrameworkElement;
        }
        return null;
    }
}

This will now show a BusyIndicator for each co-routine class which is annotated with the BusyMessageAttribute. When that attribute is not present, the BusyIndicator will be hidden. Whenever the SequentialResult completes, regardless of the reason (ran to completion, cancelled, exception), the indicator will be hidden again.

Another neat side-effect from this approach is that it very easily scales to having multiple distinct sets of BusyIndicator containers with their own controls triggering them, because the control triggering the action will only trigger showing the first BusyIndicator upstream in the visual tree.

As stated in the introductory paragraph I will publish the code on Github sometime in the near future. If I forget, and you really, really want to play around with it, just drop me a line here on on twitter, either on @smoothfriction or @erikvanbrakel.

posted @ Monday, May 07, 2012 8:35 PM | comments

When using git, or any source control system for that matter, you want to be very careful that you only submit the files that matter to your repository. The main reasons being that a clean repository is easier to navigate, and if you’re really pushing it it might help you clone a fresh instance to a new development machine just that little bit quicker.

The community at StackOverflow have a very nice thread running with a very good list of suggested ignore rules. I’ve taken the liberty to put the list into a gist, so everyone can easily clone the list and make personal adaptions.

The Gist is available here.

Note: there is also an official repository from the github team with all sorts of gitignore files. The ignore file in my gist is what I use, and it’s only slightly different from the one for CSharp in the repository. Obviously, everyone is free to choose whichever approach they want to take ;-)

posted @ Friday, May 04, 2012 8:00 AM | comments

This article will assume that you’re familiar with Caliburn.Micro and know how to set up a silverlight application using this (awesome) MVVM framework. The steps for doing this will be skipped in the explanation. I am also going to assume that you know and use NuGet for installing packages.

If you’re working with Silverlight, the Silverlight Toolkit offers all sorts of controls to spice up your application. I urge you to check out the demo for a lot of samples to get a good feeling of what’s available.
One of the controls I really like is the BusyIndicator. It offers an easy way to speed up your perceived performance, or to put it differently, it gives your end-users the feeling that the application is responsive and getting the best performance they can get. Obviously this is just a façade, because you’re still doing the same amount of work. You’re just letting your users know what is happening instead of leaving them in the dark while waiting for something to happen.

Anyway, words don’t really convey the essence of the control. However, a picture does. So, this is what your users will see when you use the busy indicator to simply show that you’re doing something:

The challenge is how to use this semantically in your MVVM solution, while not having to litter your code with value assignments to make the control active/inactive. A naïve implementation would more or less put a property on your view model, which you set/unset at the start/end of your action method. However, this has a few disadvantages:

1. It’s error prone. What if your method doesn’t complete? Especially if you’re using the co-routines functionality available in Caliburn Micro (which I think is awesome, and you should really use this), you can assume this will be a common scenario.
2. It means you have at the very least two extra lines of code in your action methods, which clutters your code.
3. You’re repeating a lot of code. This goes against the DRY principle and makes change very difficult.

I’ve come up with several approaches to solve this problem, all valid depending on your preferences and/or use-case within the application. I will showcase the first one here, and (hopefully) follow up later with the other approaches and explanation.

A solution

I am a big fan of the co-routine functionality within Caliburn.Micro. I tend to implement all my action methods as a co-routine, so I can quickly compose my actions from a predefined set of routines I have in my toolkit. Among these routines I have things like a confirmation dialog and a simple IResult implementation which takes an instance of System.Action as a constructor parameter. This allows me to take ANY code I want and stick it in a co-routine, essentially making it part of the execution pipeline of the framework. I’ll use that co-routine to adapt it a little bit to work with a busy indicator.

Starting with a working Caliburn.Micro application, we have to add the busy indicator control to the project. So do this, simply add a package reference to SilverlightToolkit-Core. That’s where the control lives. The control itself works as a container, putting a semi-opaque (or semi-transparent if you like) layer over the contents, and putting a little progress dialog over the top, like you can see in the image at the start of the article. So we’ll take the stock ShellView.xaml and wrap everything in a BusyIndicator control. We should also add a button to activate the busy state:

<UserControl x:Class="BusyIndicatorDemo.ShellView"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:toolkit="http://schemas.microsoft.com/winfx/2006/xaml/presentation/toolkit">

    <toolkit:BusyIndicator IsBusy="{Binding IsBusy}" BusyContent="{Binding BusyMessage}">
        <Grid Background="White">
            <Button x:Name="DoSomething" Content="Do something" Height="20" Width="100" />
        </Grid>
    </toolkit:BusyIndicator>

</UserControl>

The BusyIndicator has a property called IsBusy which toggles the activity/inactivity of the control. simply put, when IsBusy equals true, the containing controls are disabled and the progress dialog is shown. What we’ll want to do is implement a method named ‘DoSomething’ on our view model which returns an IEnumerator<IResult>, which we can use to showcase the behavior. The method will just return a few instances of our co-routine to simulate a few long-running processes. In between each step we will set the status message to be displayed on the dialog.

The view model:

using System.Collections.Generic;
using Caliburn.Micro;

namespace BusyIndicatorDemo {
    using System.ComponentModel.Composition;

    [Export(typeof(IShell))]
    public class ShellViewModel : Screen, IShell, IHasBusyIndicator
    {
        public IEnumerator<IResult> DoSomething()
        {
            BusyMessage = "Step1";
            yield return new SleepRoutine(1000);
            BusyMessage = "Step2";
            yield return new SleepRoutine(4000);
            BusyMessage = "Step3";
            yield return new SleepRoutine(500);
            BusyMessage = "Step4";
            yield return new SleepRoutine(50);
        }

        public string BusyMessage
        {
            get { return _busyMessage; }
            set
            {
                _busyMessage = value;
                NotifyOfPropertyChange(() => BusyMessage);
            }
        }
        private string _busyMessage;
        
        public bool IsBusy
        {
            get { return _isBusy; }
            set
            {
                _isBusy = value;
                NotifyOfPropertyChange(() => IsBusy);
            }
        }
        private bool _isBusy;
    }
}

And the co-routine:

using System;
using System.Threading;
using System.Threading.Tasks;
using Caliburn.Micro;

namespace BusyIndicatorDemo
{
    public class SleepRoutine : IResult
    {
        private readonly int _milliseconds;
        public string BusyMessage { get; set; }

        public SleepRoutine(int milliseconds)
        {
            _milliseconds = milliseconds;
        }

        public void Execute(ActionExecutionContext context)
        {
            Task.Factory.StartNew(() => Thread.Sleep(_milliseconds))
                .ContinueWith(x => Completed(this, new ResultCompletionEventArgs()));
        }

        public event EventHandler<ResultCompletionEventArgs> Completed;
    }
}

You might have noticed the IHasBusyIndicator interface on the view model. This is what we’ll use to determine if we should do something to show the status when invoking an action. In the Caliburn.Micro framework you can basically replace anything you want. We’re going to look at wrapping the code which executes a co-routine with our little busy indicator activator. Using the standard AppBootstrapper implementation, place the following code in your Configure method:

var invokeAction = ActionMessage.InvokeAction;
ActionMessage.InvokeAction = context =>
{
    var target = context.Target as IHasBusyIndicator;
    if (target != null)
    {
        target.IsBusy = true;
        EventHandler<ResultCompletionEventArgs> coroutineOnCompleted = (sender, args) => { };
        coroutineOnCompleted = (sender, args) => { target.IsBusy = false;
                                                     Coroutine.Completed -= coroutineOnCompleted;
        };
        Coroutine.Completed += coroutineOnCompleted;
    }

    invokeAction(context);
};

This code will basically check if the view model on which we are executing the action has a busy indicator property, and if so, set it when starting and unset it when done. If the view model does not implement the interface the code only runs the regular invoke action.

However, this is not the most ideal approach. You still have to set the BusyContent property for every step (unless you simply want a general message), and the InvokeAction implementation seems a bit brittle. I’ve got a few different options to explore, which are a bit more involved. A small hint: the Dispatcher will come into play, and we’ll move the code responsible for showing the busy indicator around a little bit.

Update: I forgot putting in the code for the IHasBusyIndicator interface. Here it is:

public interface IHasBusyIndicator
{
    bool IsBusy { get; set; }
}

posted @ Friday, April 20, 2012 2:33 PM | comments

It’s cliché, but it’s the time of the year again for a good spring cleaning. I’ve updated my template to be sort of metro-ish, as a preparation for Windows 8 coming to us in the summer.

The next few posts I will write will be a continuation of my previous post about the Joel Test. I got a good comment on that, saying that while the test has some valid points, it’s not an absolute measure of the quality of a company. While I agree with that statement, I also feel that there’s no harm in striving for perfection. Obviously the points which either require you to have plenty of human resources (god, I hate that word) or money, there’s a lot you can do with a little bit of creative interpretation and good use of the (free) tools at hand.

I’ve also set out to dive into Windows Phone and WinRT development. I’m getting quite good at XAML based programming, doing Silverlight and WPF programming at my day job and all, so I figured the next step is to dive into the platforms which could use my help to increase the amount of quality apps available, while also making me filthy rich (note: insert sarcasm here). So expect some posts on how to get started in the not-so-near future.

Another note: I changed my reluctantly changed my feedburner ID, because I couldn’t remember my details and honestly, the amount of subscribers was generally below the amount of fingers available on my both hands combined. So if you want to subscribe, use the button on the right, and I will try to keep a steady flow of braindumps coming your way!

posted @ Tuesday, April 17, 2012 9:44 PM | comments

Tomorrow, I will start my second year at my current employer. The company is fairly small, when I started there were two developers and the managing director. Effectively it was just the two of us though. Additionally, the managing director actually has a technical background, and trusts our judgment. This left us with a lot of room to make our own decisions on what’s important. There’s around 6 of us now, and things are going nice and steady.

As one of my responsibilities I’ve decided on making the whole development process as painless as possible. I could of course try to think of all sorts of things to do myself, but luckily, there’s already a pretty good list out there already. Joel Spolsky, one of the people behind Stack Overflow (the Q&A site for and by software developers) wrote an article about this back in August 2000. Ages ago in software development terms. However, the list is still valid, and my aim was going to be to meet as many of the requirements I could.

1. Do you use source control?
2. Can you make a build in one step?
3. Do you make daily builds?
4. Do you have a bug database?
5. Do you fix bugs before writing new code?
6. Do you have an up-to-date schedule?
7. Do you have a spec?
8. Do programmers have quiet working conditions?
9. Do you use the best tools money can buy?
10. Do you have testers?
11. Do new candidates write code during their interview?
12. Do you do hallway usability testing?

The Joel Test has 12 requirements. According to Joel, a proper software development team should score at least a 10 out of 12. Being a startup company, it’s probably expected that you wouldn’t be there right away. Additionally, doing mainly green-field development, some of these are not directly applicable. However, with some creativity it’s quite possible to find a solution for each one.

For completeness sake, here’s the scoring before we started working on it:

Do you use source control?
Yes. We have a subversion server up and running, and we use it actively.

Can you make build in one step?
No.

Do you make daily builds?
No.

Do you have a bug database?
Yes. We use Mantis for that, and keep it as up-to-date as possible.

Do you fix bugs before writing new code?
No. Not by rule.

Do you have an up-to-date schedule?
No. We only have the main project deadlines to go by.

Do you have a spec?
No. We just wing it.

Do programmers have quiet working conditions?
No. We share an office with a consulting company. Lots of phone calls.

Do you use the best tools money can buy?
Yes. As far as money allows.

Do you have testers?
No. We test our code ourselves.

Do new candidates write code during their interview?
Yes. Or at least show code from pet projects and explain it.

Do you do hallway usability testing?
No. We simply don’t have people to do that between the two of us.

Adding everything up this gives us an appalling 4 out of 12. Plenty of room for improvement I’d say!

For my next posts I will explain how we’ve gone from a 4 out of 12 to somewhere between 8 and 10 out of 12.

posted @ Monday, January 02, 2012 12:13 AM | comments

After writing my previous post, Building your own Reflector with Mono.Cecil and the CodeDom, I decided to find other initiatives to writing a ‘new Reflector’. I’ve now joined the Monoflector effort, working on filling the gaps in the current decompiler. It seems a good fit, because I already knew a few things about it after my small spike.

We’re working with the decompiler which is part of the Cecil project. However, there are quite a few bugs or just lacking features which makes reading the generated code quite frustrating. We’ve forked Cecil and are working on adding the features we need.

If you want to check out the project, I invite you to go to our github page at http://github.com/jcdickinson/Monoflector. Feel free to fork the project and get your changes in, but keep in mind that at the moment of writing, the GUI is under quite heavy construction. It might not be a good idea to work on that, because it will be quite hard to integrate your changes into the main branch.

posted @ Saturday, February 12, 2011 10:04 PM | comments

Sparked by the news that Red Gate’s Reflector will not be available for free anymore starting early March (see announcement on the redgate site), I decided to try how hard it would be to build your own reflector. Turns out, not too hard if you use the tools at hand. There’s actually already a nice effort going on based on the Mono.Cecil.Decompiler, but I only found out after I started my trials.

What I basically did was get Mono.Cecil to read an assembly, hand me the MSIL statements and simply build an AST (Abstract Syntax Tree) out of that using the .NET CodeDom available in System.CodeDom.Compiler. Combined with the CSharp or VB code generators, available in Microsoft.CSharp and Microsoft.VisualBasic respectively, I managed to more or less decompile System.Object into valid C# code.

The code very rough, and not tested more than just reading and converting the MSIL by hand and using that to check. However, I did find that for most things, a decompiler like this is not very hard to build. Just very time consuming. You can check out the code at my github repo, here. Most of the work is in the ILToCSharpConverter.cs file, which simply converts most of the MSIL from the System.Object class into an AST, which then gets fed through the code generator.

Note: I excluded the GetFieldInfo method, because I ran into an infinite loop and didn’t want to try to fix that before publishing. Any other classes are NOT tested, and therefore will probably break. Also, the code generated is hardly complete or optimal, but it should more or less convey the meaning!

If you want, have fun hacking away. Might actually be fun to get this off of the ground, no?

posted @ Monday, February 07, 2011 3:23 AM | comments

Onwards, to Project Euler problem #3. The problem is defined as below:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

So, basically, we need to find out which factors make up a certain number. The easiest way to do this is simply by trial division. A very naïve implementation would be something like this:

function Get-PrimeFactors ([long]$number)
{
    while ($number -gt 1)
    {
        for($i = 2; $i -le $number; $i++)
        {
            if($number % $i -eq 0)
            {
                $number = $number / $i;
                $i;
                break;
            }
        }
    }
}

 

To be honest, for a number of this magnitude even the simplest of solutions will work. I’ve been looking at different integer factorization algorithms (using my trusty pal Wikipedia), but none of them is simple enough to actually fit the problem. Most of them are actually really suitable for the problem, if the number was much, much bigger.

However, there are a few optimizations to be made. For instance, we can assume that we only have to check for divisors up to the square root of the number in question, because anything higher than that has a pairing divisor which is lower than the root. For instance, let’s look at 42. $\sqrt{42} \approx 6.5$, so we only have to check up to (and including) 6. If we look at all possible solutions for $a \times b = 42$, we’ll see that none of them have two factors above 6:

• $2 \times 21$
• $3 \times 14$
• $7 \times 6$
• $6 \times 7$
• $14 \times 3$
• $21 \times 2$

Besides that, we need to only look for prime factors. We know that all primes (except for the first one, being ‘2’) are odd. Adding all of these optimizations in, we’ll get something like this:

function Get-PrimeFactors ([long]$number)
{
        while($number % 2 -eq 0)
        {
            2;
            $number /= 2;
        }
        for($i = 3; $i -le [Math]::Sqrt($number); $i+= 2)
        {
            while($number % $i -eq 0)
            {
                $number /= $i;
                $i;
            }
        }
        $number
}

 

This is more or less a good enough solution for this problem. Using the number from the problem description, it will run take around 50ms to get all factors of that integer.

As I’ve said, I’ve looked into a bunch of factorization algorithms, but they were all pretty much overkill for the problem at hand. As you see, the solution is found in 50ms. Even bigger numbers like 600851475143123, which is the product of two quite substantial primes, takes less than 30 seconds. I think this function might be useful for later Project Euler problems, so I’ll keep it in the library for now.

posted @ Sunday, January 30, 2011 6:52 PM | comments

The first few Project Euler problems are actually pretty trivial to brute force, but sometimes they have a smart solution. All in all, coming up with a semi-smart title for the post is usually harder than the problem itself. But I don’t want to leave anything out, so I’ll just continue on with problem #2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The Fibonacci sequence is a quite classic integer sequence, named after Leonardo of Pisa, aka Fibonacci. Apparently they’re used in the analysis of financial markets and much more, but I have never used it in the wild so far.

Besides that, because this solves so blazingly fast (even for numbers up to 10²⁰). This is simply because the Fibonacci sequence gets quite big, quite fast. So I just solve this using a very simple bit of PowerShell code.

function Get-Fibonacci ($max)
{
    $current = $previous = 1
    $previous;
    while($current -lt $max)
    {
        $current;
        $current, $previous = ($current + $previous), $current
    }
}

$measure = Get-Fibonacci 4000000 | where {$_ % 2 -eq 0} | measure-object -sum
Write-Host $measure.Sum

 

One thing I did find was that a recursive solution doesn’t really work, at least not in PowerShell. The default call depth is set to 100 recursive calls at most, which you will hit eventually. Not in this case though, but when testing for higher numbers it would fail. However, I think that while a calculating a Fibonacci sequence is a nice exercise to learn about recursion, it isn’t a good example of when to use recursion in the first place.

posted @ Tuesday, January 25, 2011 1:37 AM | comments

I am not at all sure how far I will get with this, but I am going to try. So far I have solved the first 7 problems from Project Euler, using PowerShell. I will, whenever I solve a problem, take my time to write about my solution and what I’ve learned about math and PowerShell. It should be a good read for anyone not particularly a wizard at math, because I don’t have a math major either. Everything I write here should be in reasonably understandable terms, because I need to understand it too!

Either way, let’s start with the first problem, defined as below.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is easily solvable using a simple formula, but first, a naïve script to calculate this:

(1..999)
    | where {$_ % 3 -eq 0 -or $_ % 5 -eq 0}
    | measure -sum
    | select Sum

 

So basically, what I do here is create an array ranging from 1 to 999, select all items which are divisible by 3 or 5, and add them together. Then, for good measure, I select the ‘Sum’ property of the measure info object.

What I learned here is basically how to create a range (similar to Enumerable.Range in C#), and how to measure a variable in PowerShell.

This is not the optimal solution. This problem is actually best solved simply by using a simple formula for calculating the sum of a range of numbers:

$$\sum_{i=1}^n i = {n^2 + n \over 2}$$

Basically, for any range of numbers with a regular interval you can find the sum with this formula. Something even more interesting is that it is possible to also find the sum for a sequence of $i^2$, $i^3$, and so on. This will be useful for one of the next problems, so I will elaborate on that when I get there.

It’s easy to prove how this formula works. First, we take the sequence and put the reverse sequence below it, just for visualization. For the example I’ve taken {1,2,3,4,5}, it’s a bit shorter:

1 2 3 4 5
5 4 3 2 1

What’s so special about this? Well, every pair of the top and bottom row is equal to exactly 6, or (n+1). How many pairs are there? Well, that’s easy. In this case, 5, but in a general case, we could say there are ‘n’ pairs. So the sum of these pairs is equal to: $(n+1)n$ which can be reduced to $n^2 + n$. However, because we’ve duplicated the sequence, our sum is now twice the amount we’re looking for. Simply divide by two (= remove the duplicate sequence) and voila: we have our formula!

However, we’re not looking for {1,2,3,..,n}. We’re looking for all terms divisible by 3 or 5, or {3,6,9,..,n} and {5,10,15,..,n}. Luckily, we can just multiply the sequence for {1,2,3,..n} by 3 and 5 to get those. We just need to find the upper bound for both, to make sure the $3n$ and $5n$ won’t be greater than 1000. In other words, less than or equal to 999. It’s not much trouble calculating this:

999/5 = 199.8. Round down to 199.
999/3 = 333. No rounding needed.

But wait! we also need to make sure we’re not adding values twice. Every time a value is divisible by 3 and 5, we’ll add it twice if we simply add the two sequences. So we’ll need to make sure that the values divisible by 15 (= 3 * 5) are removed from the sequence once. Again, let’s find the upper limit:

999 / 15 = 66.6, round down to 66.

Adding all these values gives us the following equations:

$$\sum_{i=1}^{333} 3i + \sum_{i=1}^{199} 5i - \sum_{i=1}^{66} 15i = 3{{333^2 + 333} \over 2} + 5{{199^2 + 199} \over 2} - 15{{66^2 + 66} \over 2}$$

Problem solved, with and without programming! As for the title, I’ll leave it as an exercise for you as a reader to look up the story about little Carl Friedrich Gauss, and how it relates to this problem and it’s solution.

posted @ Sunday, January 23, 2011 11:50 PM | comments