James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 154 , comments - 1269 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

.NET

CSharp

Little Wonders

Little Wonders

vNext

Thursday, July 2, 2015

Summer Vacation & 2015 Visual C# MVP Award

image Hey folks, it’s been a busy summer here at work and at home.  I’ve been busy helping to keep the kids entertained as well as working on a major project at work, which has left me with a few weeks hole in my blogging schedule.  Rest assured, I am not gone and will be blogging again in the next week or so.  Probably with a new puzzler on Monday.

In other news, I received word yesterday that I’ve been awarded a Visual C# MVP award for the 5th consecutive year now.  Thank you all so much for reading my blog posts!  It’s much appreciated.

Posted On Thursday, July 2, 2015 1:13 PM | Comments (1) |

Tuesday, June 16, 2015

Solution to Little Puzzlers–Fun With Random Number Generators

This is the way I went about the "Fun With Random Number Generators” problems. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

Problem 1: Rand3() from Rand4()

For many people, the first thought is to simply use the modulus operator and narrow down the range:

   1: public static int Rand3()
   2: {
   3:     // narrow to 0-2 then add 1
   4:     return (Rand4() % 3) + 1;
   5: }

The problem with this approach is that it collapses all “rolls” of a 4 into a 1, thus doubling the chance we’d get a 1.  This makes the distribution of the numbers uneven and makes our random number generator less than useful.

Since we want an even distribution (as per the problem statement), our best option is to simply take those 4s and “re-roll” them until we get a non-4.

   1: public static int Rand3()
   2: {
   3:     int number;
   4:  
   5:     do
   6:     {
   7:         number = GivenGenerators.Rand4();
   8:     }
   9:     while (number > 3);
  10:  
  11:     return number;
  12: }

Is this slightly inefficient?  Yes, there is a chance we will “re-roll” several times over again if we get several 4s in a row, but this is the cost of keeping the even distribution.  Essentially, in random number narrowing like this where the wide number is not a multiple of the narrow number you have two choices: approximate (and thereby lose even distribution), or reject and regenerate (and loose constant-time performance).

Problem 2: Rand7() from Rand5()

Now, widening is another beast altogether.  We can’t simply multiply or add random numbers together willy-nilly or again we’ll risk disturbing the distribution.  For example, if we took Rand5() + Rand5() we’d have a much higher chance of a middle number than the “edges” since there’s only one way to “roll” a 2 and one way to “roll” a 10, but several ways to roll a 5 (1 + 4, 2 + 3, 3 + 2, 4 + 1).

So, the safest way to do it is to generate two random numbers and have one be the “1s” column and one be the “5s” column.  That is, we’ll use our random number generators to create an even distribution of a base 5 number from 01 to 45 (that is, from 1 to 25).  We can then “reject” numbers above 21 (our multiple of 7) and mod by seven to get an even range from 0 to 6.  Then we simply add 1 to shift from 1 to 7.

   1: public static int Rand7()
   2: {
   3:     int number;
   4:  
   5:     do
   6:     {
   7:         number = (GivenGenerators.Rand5() - 1) * 5 + (GivenGenerators.Rand5());
   8:     }
   9:     while (number > 21);
  10:  
  11:     return (number % 7) + 1;
  12: }

Once again, instead of approximating and losing even distribution, we are choosing to “reject” numbers and sacrifice a little efficiency.

If this seems hard conceptually, picture it like this:

   1: // picture the numbers 1-7 filling a 
   2: // 2d 5x5 matrix.
   3: int matrix[5][5] = {
   4:     { 1, 2, 3, 4, 5 },
   5:     { 6, 7, 1, 2, 3 },
   6:     { 4, 5, 6, 7, 1 },
   7:     { 2, 3, 4, 5, 6 },
   8:     { 7, 0, 0, 0, 0 }
   9: };

So instead of using base-5, we could instead use one Rand5()-1 to select our row, and one Rand5()-1 to select our column, then re-roll if we hit a zero.

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Posted On Tuesday, June 16, 2015 12:54 AM | Comments (0) |

Tuesday, June 9, 2015

Little Puzzlers–Fun With Random Number Generators

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

Problem 1

Let’s play with narrowing down a random number generator evenly.

Assume you are given a random-number generation function called Rand4() that generates a random number from 1 to 4 inclusively (i.e. 1, 2, 3, or 4) with equal probability and eventually even distribution.  That is, you may get several 3s in a row, but over the long term the number of 1s, 2s, 3s, and 4s are the same.

Given the Rand4() function, create a Rand3() function that also has equal probability and distribution for numbers from 1 to 3 inclusively.

Problem 2

Now, let’s go the other way and expand!

Given a Rand5() that generates a random number from 1 to 5 inclusively with equal probability and eventually even distribution, create a Rand7() function that also has equal probability and distribution for numbers from 1 to 7 inclusively.

Note

Remember!  The primary focus on both of these we want to preserve the equal probability and even distribution.  That said, we also want to preserve the “randomness” as well.  Of course, efficiency is preferable as well, but not at the cost of these other traits.

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

Posted On Tuesday, June 9, 2015 12:23 AM | Comments (6) |

Friday, June 5, 2015

C#/.NET Little Wonders: Null Conditional Operator in C# 6

Once again, in this series of posts I look at the parts of the .NET Framework that may seem trivial, but can help improve your code by making it easier to write and maintain. The index of all my past little wonders posts can be found here.

Visual Studio 2015 is on the horizon!  In fact, some of you may already have played with the preview and seen some of the many neat new things to come – both in the IDE and in the C# language.

Note: All of the C# 6 features mentioned are current with the latest CTP of VS2015 as of the time of this writing.  The syntax and exact feature behaviors may be subject to change in the final released version.

Too many layers of null checks!

How many times have you had to consume a web service, and that web service has had many layers of nested objects, each of which can potentially be null

Often times, to be safe, this makes us end up having to write logic like this:

   1: var response = someProxy.SomeWebMethod();
   2:  
   3: // so many layers, so many potential nulls...
   4: if (response != null && response.Results != null && response.Results.Status == Status.Success)
   5: {
   6:     Console.WriteLine("We were successful!");
   7: }

And this is just a status buried down two layers, imagine if the model was four, five, or six layers deep!

This happens a lot in C# (and Java) where at any step along the way of a deeply-nested model, you could encounter a null.  Indeed it would be nice to be able to have an option to cascade the null down the chain if there’s a null along the way.

Now, we get this new feature in C# 6, the null conditional operator.  This operator does exactly what we’re talking about: if the left side of the operator is null, it cascades a null of the resulting type to the right. 

In short, if you replace your “.” with the null conditional operator “?. it will cascade the null down the line:

   1: var response = someProxy.SomeWebMethod();
   2:  
   3: // so much better!
   4: if (response?.Results?.Status == Status.Success)
   5: {
   6:     Console.WriteLine("We were successful!");
   7: }

So, if response is null, or if response.Results is null, then the result will be a null matching the return type of Status.  If not, you will get the actual value of Status.

Now, notice that we have “?.” in there twice, this is because we need to use the “?.” everywhere that we want to cascade the null otherwise a null will throw as expected.

For example, consider the following four similar conditionals:

   1: // #1
   2: if (response.Results.Status == Status.Success) { }
   3:  
   4: // #2
   5: if (response?.Results.Status == Status.Success) { }
   6:  
   7: // #3
   8: if (response.Results?.Status == Status.Success) { }
   9:  
  10: // #4
  11: if (response?.Results?.Status == Status.Success) { }

Let’s look at each of these in turn:

  1. The first will throw if either response or response.Results are null 
  2. The second will throw only if response.Results is null, but will cascade if response is null
  3. The third will throw if response is null, but will cascade if response.Results is null
  4. The fourth will cascade if either response or response.Results are null

Most of the time, unless you know an element cannot be null in a chain (like if it’s a struct), you’ll want to continue to cascade down an identifier chain once you start.

What does null-cascading with a value type result do?

Let’s say that Results has a Count field that evaluates to an int, what would happen if we did this?

   1: // what is the type of the LHS?
   2: if (response?.Results?.Count > 0)
   3: {
   4:     Console.WriteLine("We got data!");
   5: }

The above does compile.  This is because C# is smart enough to realize that the end result of the chain is a value type, so it converts it to a Nullable<int> instead.  This means we may be comparing null to zero.  However, if you study the way nullable math works in C# (much like in SQL) you’ll find that null > 0 is false (incidentally so is null < 0).  For more details, see this post on Nullable Math Doesn’t Always Add Up.

Or, let’s do this instead:

   1: // won't compile, will complain that can't implicitly convert
   2: // Nullable<int> to int
   3: int count = response?.Results?.Count;

You’ll see right away that C# considers the end result of that identifier chain to be Nullalble<int> (also referred to as int?) instead of int.

Want a default other than null? 

What if you want to cascade the null, but want to use another default value instead.  For example, take the Count expression above where it gave us a Nullable<int> that can cause some interesting math comparisons if the value is null, it would be better if we could cascade to something like zero.

Well, you can combine the null conditional operator with the null-coalescing operator (??) to provide a different default on null.

   1: // This will compile, if the expression evaluate to null then 0 will be used.
   2: int count = response?.Results?.Count ?? 0;

Indeed, notice that now we can type the value of count to int since null is no longer an option.

What if we’re dealing with an indexer property?

So, you may have noticed we’ve been dealing directly with members accessed using the dot (“.”) operator, what happens if we want to use an indexer property (“[]”)?

For example, let’s say that Results contained a List<Address> called Addresses. And List<T> has an indexer property.

We don’t want to have to go back to:

   1: // notice the [...] indexer on addresses
   2: if (response != null && response.Results != null && response.Results.Addresses != null
   3:     && response.Results.Addresses[0] != null && response.Results.Addresses[0].Zip == "63368")
   4: {
   5:     Console.WriteLine("Are we neighbors?");
   6: }

Notice the indexer on Addresses, so we can’t use “?.“ because indexers use a different syntax than fields, properties, and methods.  Fortunately, C# provides a null conditional form of the indexer operator “?[]” which works just like the standard member-access null conditional operator, but for indexers instead.

So now, we can write:

   1: // Again, much cleaner...
   2: if (response?.Results?.Addresses?[0]?.Zip == "63368")
   3: {
   4:     Console.WriteLine("Are we neighbors?");
   5: }

With this, if response, response.Results, response.Results.Addresses, or response.Results.Addresses[0] are null, we will coalesce a null as the final result.

But wait, it works for more than just fields and properties…

The null conditional operator is not simply for fields and properties, it can be used for method calls as well.  Once again, if the identifier chain on the left evaluates to null the method will not be called and a null matching the return type (if any) will be cascaded along.

For example, how often do you have code like this:

   1: if (x != null)
   2: {
   3:     x.Dispose();
   4: }

This is a fairly common occurrence, we want to call a function if the instance is not null, but it takes 4 lines of code to write that (assuming we do our full set of curlies).

Now, however, this can be simplified to one line:

   1: // a great one-liner!
   2: x?.Dispose();

Much cleaner!  Especially if you are doing a lot of these kind of statements in a larger cleanup operation; just imagine the lines you will save!

And what about processing events?  Those of you who have done any event raising know that there’s a standard pattern for raising an event where you take a copy of the handler, and then check the copy for null.  This is so that the value of the handler doesn’t change between the time you check and the time you invoke it.  We don’t want to lock the invocation, because that could be a very expensive lock if the subscribers do anything heavy.

   1: // to avoid locking, yet be thread-safe, must make a copy of the delegate
   2: // and then invoke the copy.  
   3: var copy = OnMyEvent;
   4: if (copy != null)
   5: {
   6:     copy(this, new EventArgs());
   7: }

For more details on this pattern, see Safely and Efficiently Raising Events

Now with the null conditional operator, we can do this instead:

   1: // again, reduced to a great one-liner:
   2: OnMyEvent?.Invoke(this, new EventArgs());
So, the ?. will evaluate first and make a copy of the reference (hence satisfying the copy pattern) and then based on whether that is null or not, it will invoke the delegate.

Summary

The null conditional operator is a great code-reducer to eliminate a lot of very verbose null-checking logic where cascading makes sense.  Keep in mind that a null-conditional chain that results in a value type will create a Nullable<T> instead, and particularly pay attention when you try to perform arithmetic or logical comparisons versus null.

Thanks for reading my Little Wonders of C# 6 series, I’ll be back soon with more Little Wonders and Little Puzzlers in the weeks to come.

Posted On Friday, June 5, 2015 12:26 AM | Comments (4) |

Wednesday, June 3, 2015

Solution to Little Puzzlers–Validate a Sudoku Board

This is the way I went about the "Validate a Sudoku Board” problem. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

My Approach

This one is fairly straight-forward, your basic task is to make sure that the value of any given cell isn’t replicated in the cell’s row, column, or “cube”.  The problem is how you go about this.  There is a space-efficient way, but requires more looping, or there is a method that requires only visiting any cell one time, but requires extra space.

Given that the puzzle is fixed in size (9x9 grid), I’ll opt for better algorithmic complexity and use space to hold the set of all numbers seen for each given row, column, and cube.  By using 27 sets to hold these values (9 for the rows, 9 for the columns, 9 for the cubes), we can easily see if we’ve already seen the current number in the given row, column, or cube and immediately declare the puzzle invalid.

Of course, we could get even more space-efficient and use 27 BitArrays (or one large one partitioned, etc.), but then we lose the elegance of set logic.  I like keeping things logically simple and then optimizing for space after determining there is a need, so I’d probably opt to use Sets in my original answer in an evaluation, and then mention that if space were a concern, I would then optimize to BitArray.

So, here’s my solution:

   1: public class SudokuBoard
   2: {
   3:     private readonly char[,] board;
   4:  
   5:     // validate board is a 9x9 array
   6:     public SudokuBoard(char[,] board)
   7:     {
   8:         if (board == null || board.GetLength(0) != 9 || board.GetLength(1) != 9)
   9:         {
  10:             throw new ArgumentException("Board is not valid size for Sudoku");
  11:         }
  12:  
  13:         this.board = board;
  14:     }
  15:  
  16:     public bool Validate()
  17:     {
  18:         // yes, i could use BitArray for space efficiency, but i like the logical feel
  19:         // of the set and how it returns false on Add() if already there.
  20:         var rows = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
  21:         var columns = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
  22:         var cubes = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
  23:  
  24:         // process each cell only once
  25:         for (int row = 0; row < 9; ++row)
  26:         {
  27:             for (int column = 0; column < 9; ++column)
  28:             {
  29:                 var current = board[row, column];
  30:                 if (char.IsDigit(current))
  31:                 {
  32:                     // determine which of the "cubes" the row/col fall in
  33:                     var cube = 3 * (row / 3) + (column / 3);
  34:  
  35:                     // if add to any set returns false, it was already there.
  36:                     if (!rows[row].Add(current) || !columns[column].Add(current) || !cubes[cube].Add(current))
  37:                     {
  38:                         return false;
  39:                     }
  40:                 }
  41:             }
  42:         }
  43:  
  44:         return true;
  45:     }
  46: }

Note that I’m not checking for invalid characters for the sake of brevity, though we could easily do this in the constructor, or in the Validate() method itself:

   1: var current = board[row, column];
   2: if (char.IsDigit(current))
   3: {
   4:     // blah blah blah
   5: }
   6: else if (!char.IsWhiteSpace(current))
   7: {
   8:     return false;
   9: }

Finally, here’s a simple driver to illustrate usage:

   1: public static class Driver
   2: {
   3:     public static void Perform()
   4:     {
   5:         var board = new char[9,9] 
   6:             {
   7:                 {'5', '3', ' ', ' ', '7', ' ', ' ', ' ', ' '},
   8:                 {'6', ' ', ' ', '1', '9', '5', ' ', ' ', ' '},
   9:                 {' ', '9', '8', ' ', ' ', ' ', ' ', '6', ' '},
  10:                 {'8', ' ', '2', ' ', '6', ' ', ' ', ' ', '3'},
  11:                 {'4', ' ', ' ', '8', ' ', '3', ' ', ' ', '1'},
  12:                 {'7', ' ', ' ', ' ', '2', ' ', ' ', ' ', '6'},
  13:                 {' ', '6', ' ', ' ', ' ', ' ', '2', '8', ' '},
  14:                 {' ', ' ', ' ', '4', '1', '9', ' ', ' ', '5'},
  15:                 {' ', ' ', ' ', ' ', '8', ' ', ' ', '7', '9'},
  16:             };
  17:  
  18:         var validator = new SudokuBoard(board);
  19:  
  20:         Console.WriteLine("The Sudoku board is " + (validator.Validate() ? "valid" : "invalid"));
  21:     }
  22: }

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Posted On Wednesday, June 3, 2015 2:52 AM | Comments (4) |

Powered by: