Pixata Custom Controls
For Lightswitch

Recent Posts

Popular tags (# posts in brackets)

Anonymous types (3) ASP.NET (5) C# (3) C# tricks and tips (2) Computers (6) Design patterns (3) DomainDataSource (3) Dynamic data (4) Entity framework (3) Entity model framework (5) F# (3) LightSwitch (12) Linq (6) Microsoft (2) MVP (2) MVVM (2) Project Euler (2) RIA services (5) Silverlight (2) SQL Server (4) Unit testing (4) Visual Studio (7) WCF (3) WPF (3)

Gratuitous link to StackExchange

Archives


Categories


Disclaimer

The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

Actually, as I'm self-employed, I guess that means that any views I expressed here aren't my own. That's confusing!


Acknowledgments

Theme modified from one by Tom Watts
C#/F# code styling by Manoli (for posts pre-2016) and Google code prettify (for post from Jan 2016 and beyond)


My rambling thoughts on exploring the .NET framework and related technologies

# Tuesday, 16 February 2016

I came across a situation recently in which we needed an object in the client. Due to the cost of creating this object, we didn't want to create it when loading up the window as it might not be needed (if the user didn't click the appropriate button), we didn't want to store it on the window's main object graph, but equally, we wanted to keep hold of it once it had been created.

This situation is not uncommon, where you have to create a class that is expensive (in database or bandwidth terms) to create.

The obvious solution to this was to have a private variable for the instance of Expensive, and a second private bool variable to indicate if the Expensive object had been created. We could check the bool before accessing the Expensive variable. Even better, we could create a property that wrapped this up. Imagine our class is wittily named Expensive...

public class Expensive {
  // For our purposes, this will just be a simple class that writes a message to the output
  // window when it is created (so we can see when that happens)
  public Expensive() {
    Debug.WriteLine("Created new instance of Expensive, hash code is " + GetHashCode());
  }
  // Add a property, so we can reference something
  public int AnInteger { get; set; }
}

Note that in many cases you can't simply rely on checking if _expensive is not null, as null may well be a valid value (or lack thereof) for the object. Therefore, you need two variables.

This works, but has a few drawbacks. Firstly, it's a lot of code for a simple requirement. Imagine you needed to do this for several types, you would end up with a lot of boilerplate code. Secondly, this method involves multiple variables for each expensive object you want. Finally, and most importantly, another developer coming along at some future date might not realise how it's supposed to work, and assume that _expensive will always be available, bypassing the bool and causing a null reference exception. Even worse, when they discover the null reference, they might add extra code to create the object, ignoring the code you previously added to do just the same thing. This is not good.

A more elegant solution

Drum roll please... enter Lazy<T>. This neat little class (introduced in .NET 4.0) allows you to wrap all this up in one variable, and not have to worry about the details.

To illustrate, let's define our Expensive class as follows...

public class Expensive {
  // For our purposes, this will just be a simple class that writes a message to the output
  // window when it is created (so we can see when that happens)
  public Expensive() {
    Debug.WriteLine("Created new instance of Expensive, hash code is " + GetHashCode());
  }
  // Add a property, so we can reference something
  public int AnInteger { get; set; }
}

Instead of having the two private variables mentioned before, you just have one of type Lazy. When declaring it, you add the code that creates the instance as a constructor parameter. As a simple example, you could have something like this...

Lazy<Expensive> exLazy = new Lazy<Expensive>(() => new Expensive());

That's about as simple as it gets, but there's no reason why it couldn't include more code that uses (say) a WCF service, database, EF model or whatever in there.

Now, the clever thing is that the class doesn't get created until you actually want it. For example, see the following (rather over-the-top) code...

Debug.WriteLine("About to declare, but not use our lazy value");
Lazy exLazy = new Lazy(() => new Expensive());
Debug.WriteLine("Created the lazy value, but not used yet");
for (int i = 0; i < 5; i++) {
  Debug.WriteLine("  i: " + i);
  if (i > 1) {
    Debug.WriteLine("  Setting exLazy.Value.AnInteger to " + i);
    exLazy.Value.AnInteger = i;
  }
}
Debug.WriteLine("Ended loop, exLazy.Value.AnInteger is " + exLazy.Value.AnInteger);

Debug.WriteLine("Ended loop, exLazy.Value.AnInteger is " + exLazy.Value.AnInteger);

This uses a liberal amount of writing to the Output window so we can see what's happening. When you run it, you see the following...

About to declare, but not use our lazy value
Created the lazy value, but not used yet
  i: 0
  i: 1
  i: 2
  i: 3
  Setting exLazy.Value.AnInteger to 3
Created new instance of Expensive, hash code is 1707556
  i: 4
  Setting exLazy.Value.AnInteger to 4
  i: 5
  Setting exLazy.Value.AnInteger to 5
  i: 6
  Setting exLazy.Value.AnInteger to 6
  i: 7
  Setting exLazy.Value.AnInteger to 7
  i: 8
  Setting exLazy.Value.AnInteger to 8
  i: 9
  Setting exLazy.Value.AnInteger to 9
Ended loop, exLazy.Value.AnInteger is 9

As you can see, the Expensive class isn't actually created until you want it, and from then on, it exists without needing to check it, or create it again. This means that your code can just refer to exLazy.Value all the way through, and rely on the fact that if it doesn't exists, it will be created for you.

The Lazy<T> class also has also a bool property IsValueCreated, which (oddly enough) allows you to check if the value has been created. Not sure quite how useful that is, but it's there if you need it.

Not the sort of thing you need to use every day, but when you do, it provides a more elegant and low-risk approach than the first method.

C#
Tuesday, 16 February 2016 18:00:00 (GMT Standard Time, UTC+00:00)

As my regular reader will doubtless remember, I recently blogged about the important lesson I learnt while solving problem 8. I prophetically commented there…

"So, am I going to contemplate my problem domain before diving in and coding next time? Probably not, but at least if I don’t, I might have some idea where to look when the bug reports come in!"

Hmm, I thought I was joking! Well, sadly I wasn’t.

Faced with problem 14, I jumped right in and began coding as usual. My first attempt looked like this…

let collatz n =
  Seq.unfold (fun i -> if i % 2 = 0 then Some(i, i / 2) else Some(i, 3 * i + 1)) n
let collatzLength n =
  (collatz n |> Seq.takeWhile (fun n -> n <> 1) |> Seq.length) + 1

I had tested this on a smaller range, and it worked fine. Remembering what I thought I had learnt from problem 8, I did a quick scan of the range of numbers generated, and satisfied that an int would cope with it, set off to solve the problem…

[1..1000000] |> Seq.map (fun n -> n, collatzLength n) |> Seq.maxBy snd

Whereas this had only taken a second or two on small ranges, it churned away for a very long time when given the full range, ie up to one million. Although a million is quite a lot, it shouldn’t have taken that long to solve.

I tried the problem in C#, and had the same issue…

  int maxColl = 0;
  int maxLen = 0;
  for (int i = 2; i < 1000000; i++) {
    int coll = i;
    int len = 1;
    while (coll != 1) {
      if (coll % 2 == 0) {
        coll = coll / 2;
      } else {
        coll = 3 * coll + 1;
      }
      len++;
    }
    if (len > maxLen) {
      maxLen = len;
      maxColl = i;
    }
  }

Somewhat frustrated and baffled, I gave up and started searching around for other people’s code. I came across a C# solution that looked remarkably like the one above, that ran in about 2.4s. This was even more frustrating.

Eventually, it was pointed out to me that when you run it with the full range of starting points, some of the intermediate numbers generated in the sequence grow larger than the limits of an int, which causes the number to overflow. Under normal circumstances, this doesn’t cause an exception, but means that the number goes negative. Once that happens, the Collatz sequence will never go positive again, so will never terminate (assuming we consider the value 1 as the end of the sequence). This was easily confirmed by adding a “checked” block around the C# code, and seeing the exception thrown. Changing the “int” to “long” in the code above allowed it to give the correct answer in about 2.3s.

So what should I have learnt?

Well, I should have taken more care over my number ranges, just like in problem 8. The sad thing is that I thought I had, but I obviously didn’t check carefully enough.

Thinking about it, when the code took so long, I should have put some logging in there to show where it was up to. That would have shown the problem immediately, as I would have seen the negative values in the sequence. Strike One.

The other point is that it raises the issue of validating your input. If my function had done this, I would have found the problem very quickly. For example, changing my collatz function as follows would have raised the issue as soon as I tried to run it…

let collatz n =
  Seq.unfold (fun i -> 
    if i <= 0 then failwith "The input must be at least 1"
    if i % 2 = 0 then Some(i, i / 2) else Some(i, 3 * i + 1)) n

This sort of issue comes up more often than you might think. As developers, we (and I use the plural deliberately, I’ve seen plenty of others make the same mistakes) bravely assume that the values sent into our functions/methods are within acceptable ranges. When they aren’t, we get exceptions that are often very hard to debug.

Microsoft began to address this issue with Code Contracts. In theory, these are an excellent and easy way to address exactly this problem. In practice, I never found them to work, and gave up. Maybe it’s time to revisit them and try again.

Another day, another lesson ignored!

C# | F# | Project Euler
Thursday, 11 February 2016 17:00:00 (GMT Standard Time, UTC+00:00)

The problem

As I briefly mentioned in my rant about the F# fanboy lies, I have been using Project Euler to help me learn F#. I have got as far as problem 8, which was to find the largest product in a series of digits. To save you the bother of clicking the link, here is the description…

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Apart from the fact that this was an interesting problem, I learnt a very important lesson from this one, and thought it worth sharing.

Solving the problem - or not!

My initial stab at this looked like this…

   1:  let chop n (s : string) =
   2:    [ for i in [0..(s.Length - n)] do yield s.[i..(i + n - 1)]]
   3:  let product (s : string) =
   4:    s |> Seq.fold (fun p c -> p * (int (string c))) 1
   5:  let lgstProduct n (s : string) =
   6:    s |> chop n |> Seq.map product |> Seq.max

The chop function chops the string into chunks of length n, the product function calculates the product of the digits (assuming that the string passed in only contains numbers of course), and the lgstProduct function sticks these together to find the maximum product.

I tried this with the 1000 digit number passed as a string, and using 4 for the chunk size, and it produced the right answer, 5832. Wanting to make the code shorter and neater, I included the two helper functions in the main one, and managed to come up with this...

   1:  let largestProductInt64 (n : int64) (s : string) =
   2:    [ for i in [0L..((int64 s.Length) - n)] do yield s.[(int i)..int(i + n - 1L)]]
   3:    |> Seq.map (fun s -> s, s |> Seq.fold (fun p c -> p * (int64 (int (string c)))) 1L)
   4:    |> Seq.maxBy snd

Note that I changed the code to give me a tuple, containing both the highest product, and the n-character chunk that produced it. Chuffed to bits, I threw the number 13 at it, and got the answer ("9781797784617", 2091059712) , which I duly plugged into the answer box on the Project Euler site, only to be told that it was wrong! What a chutzpah! Of course it’s right, my code works!

Or does it?

So what went wrong?

Having spent quite a bit of time testing my code, and convincing myself that it was right, I resorted to searching for other people’s answers to the same problem. Along the way, I came across someone who had had exactly the same problem as me, albeit in C++, and had come up with the same (wrong) answer.

It turns out that the issue was simple. When multiplying 13 digits together, you could potentially end up with 9^13, ie 2,541,865,828,329. Given that the maximum number that can be stored in the .NET int type is 2,147,483,647 the problem becomes apparent.

I changed my code to use int64, which is the F# equivalent of the .NET “long” type, and can hold numbers up to 9,223,372,036,854,775,807. Lo and behold, project Euler acquiesced, and accepted my answer.

In order to make my code even more general, I actually changed it to use bigint, which can hold any size of integer, but the point I want to take away from this remains the same…

What I learnt in school today

I think there is a very important lesson here. Like many of us, I piled in and started coding without really thinking about the problem. What I should have done is take a look at the problem domain, and think it through. It should have been obvious that the eventual product was going to be too large to fit into a 32-bit integer, which is probably why the Project Euler people chose such a large number in the first place. Had I done that, I would probably have got the right answer first time.

Now, I don’t know about you, but I almost never get these sorts of interesting problems in my day job. I usually get “Pull the data from the database, display it on a window, wait for the user to make changes and then save it,” which is significantly less interesting. However, I think the basic point remains valid. Without thinking through the scope of the problem, and the bounds of the domain, it’s very easy to pile and and get coding, whilst introducing all sorts of subtle bugs. My tests worked absolutely fine, simply because I was testing on small numbers. How many times do we developers test our code against a Noddy database, mainly to save development time? No need to put your hands up, we’re all guilty.

Had my largest product function been production code, I would have released a bug that would only have been spotted some time down the line. Depending on how easy/hard it would be to predict the right numbers, it’s possible that it might not have been spotted for a long time. People would just assume that the number produced was correct.

So, am I going to contemplate my problem domain before diving in and coding next time? Probably not, but at least if I don’t, I might have some idea where to look when the bug reports come in!

Improving the code

Having sorted all that out, I asked for a code review, and came across a really useful F# function that I hadn’t seen before. My chop function, included as the first line of my slimline largestProduct function split the input string into a sequence of chunks of length n. It turns out that F# has the Seq.windowed function that does exactly the same thing, but is more readable.

I also got a slightly better understanding of function composition, and saw how to reduce the number of brackets needed to convert the character to a bigint. I ended up with…

   1:  let largestProduct n (s : string) =
   2:    Seq.windowed n s
   3:    |> Seq.map (fun s -> s, s |> Seq.fold (fun p c -> p * (string >> bigint.Parse) c) 1I)
   4:    |> Seq.maxBy snd

I was quite pleased with this. A lot of functionality in four lines.

Solving the problem in C#

I was interested to see if I could solve the problem in C# as well, so I fired up LinqPad and jumped in. My initial version (including the extra bits need to run it in LinqPad, and the line to write out the result) looked like this…

   1:  void Main() {
   2:    string s = "7316...3450"; // NOTE: Snipped for brevity!!
   3:    int n = 13;
   4:   
   5:    var maxProduct = MaxProduct(s, n);
   6:    Console.WriteLine ("1) Max product is " + maxProduct.Item2 + " from " + maxProduct.Item1);
   7:  }
   8:   
   9:  public Tuple<string, long> MaxProduct(string s, int n) {
  10:    return Chop (s, n)
  11:      .Select (s1 => new Tuple<string, long> (s1, Product (s1)))
  12:      .OrderByDescending (t => t.Item2)
  13:      .First();
  14:  }
  15:   
  16:  public long Product (string s) {
  17:    long res = 1;
  18:    for (int i = 0; i < s.Length; i++) {
  19:      res *= Convert.ToInt32 (s [i].ToString());
  20:    }
  21:    return res;
  22:  }
  23:   
  24:  public IEnumerable<string> Chop (string s, int n) {
  25:    for (int i = 0; i < s.Length - n + 1; i++) {
  26:      yield return s.Substring (i, n);
  27:    }
  28:  }

Hmm, quite a lot of code there. Looks like F# really is shorter and cleaner!

There must be a way to improve this. A few moments’ thought made me realise that the Product() method is really doing what the Linq Aggregate() extension method does. Also, the Chop() method could easily be done with Linq if I fed in a range of numbers for the starting positions of the substring (like I did in my original F# code).

After a short bit of fiddling, I came up with this rather improved C# version…

   1:  public long MaxProduct (string s, int n) {
   2:    return Enumerable.Range (0, s.Length - n + 1)
   3:        .Select (i => s.Substring (i, n))
   4:        .Max (s1 => s1.ToCharArray().Aggregate (1, (long a, char c) => a * Convert.ToInt64 (c.ToString())));
   5:  }

That's much better! Once you ignore the extraneous bits, the body of the actual method is only three lines, a mere one line longer than the F# version. The F’'# is definitely cleaner, but as I’ve mentioned before, that’s not always an advantage.

After passing this problem around the team, one of the brighter sparks came up with an even shorter version that runs faster…

   1:  public long MaxProductEC (string s, int n) {
   2:    return Enumerable.Range (0, s.Length - n + 1)
   3:      .Max (i => s.Substring (i, n).Aggregate ((long)1, (a, c) => a * (c - '0')));
   4:  }

I defy anyone to tell me that C# is verbose! Don’t get me wrong, I’m really enjoying F#, but the lies are getting on my nerves!

All in all, an interesting exercise.

C# | F# | Project Euler
Monday, 01 February 2016 02:53:00 (GMT Standard Time, UTC+00:00)