James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 143 , comments - 1207 , 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

Image Galleries

Monday, April 27, 2015

The Little Wonders of C# 6 - A Presentation to the St. Louis .NET User Group

I’ll be speaking tonight at the St. Louis .NET User Group in Creve Coeur about my Little Wonders of C# 6 blog post series.

I’ve also uploaded the presentation to SlideShare for those who want an electronic copy.

Feel free to share it among friends and peers to spread the knowledge.

Posted On Monday, April 27, 2015 11:29 PM | Comments (1) |

Solution to Little Puzzlers–Largest Square of ‘1’s in a Matrix

This is the way I went about the “Largest Square of '1's in a Matrix” 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 is one of the more fun problems I’ve ever had to tackle in an evaluation, and got to a fairly optimal solution with a wee bit of prompting.  It does sacrifice a bit of space for speed (though technically you don’t need the extra space if you’re free to destroy the matrix).

There is, of course, the naïve solution of starting at each location, and seeing if a square exists at that location.  Basically, you would go right until you encounter a zero, and this would be the proposed “size” of the square.  Then you’d try to go down a row and see if you can go that many to the right again.  if at any time you hit a zero faster than that, you’d shorten your “size” to that.  Repeat until you’ve checked “size” number of rows and then you know the size of the square at that point.

Unfortunately, that will get expensive for large matrices, and there’s a much more optimal way that you can solve this with only making one pass through the matrix, which I will describe now.

Basically, what we want to do is find the top-left of the square, so I’ll start at the bottom right of the matrix and look for squares based on the information from previous passes.

Of course, a lone ‘1’ is always at least a square of size ‘1’, so that’s not as interesting and fairly obvious.  The trick is to find squares of size 2 and above.

So consider a 2x2 grid of ‘1’s starting at (r,c):

2by2We know that the square at (r,c) must be at least size ‘2’ if it has a ‘1’ and there are squares of size ‘1’ at (r+1, c), (r, c+1), and (r+1,c+1).  This only makes sense, if (r,c) is one and there are squares of size ‘1’ bellow, to the right, and below and to the right, then we know we have a square of at least size ‘2’.

So what about size ‘3’?  Consider a 3x3 square of ‘1’s at (r,c):

3by3

Again, we know that there must be a square of size ‘3’ at (r,c) if there are squares of size ‘2’ at (r+1, c), (r, c+1), and (r+1, c+1).  In fact, you can extend this to the generic logic:

size of square at (r,c) = min (size of squares at (r,c+1), (r+1, c), (r+1, c+1)) + 1

Why min?  The min covers the holes.  For example, if you were missing the bottom right ‘1’ above, you’d have this:

irregularShape

Our logic still holds.  Notice that now, the middle square is only a square of size 1, because the minimum of it’s 3 squares to consider is 0 and 0 + 1 = 1.  This still makes a square of 2 at (r+1, c) and (r, c+1) since their 3 squares of consideration are all ‘1’s, and that ultimately makes (r,c) a ‘2’ since the minimum of it’s three squares under consideration is ‘1’ and 1 + 1 = 2.

Armed with this general knowledge, I can create a scratchpad of the same size as my matrix, and build up the size of the squares (as we did above) whenever I find a 1.  We’ll need to do a little ‘magic’ when we consider squares outside the matrix (on the lower row and rightmost column), but as long as we consider those to be zeros, our logic works.

When we complete one pass of this algorithm, we should know the largest square in our matrix!

The Code

   1: // class to analyze a matrix and find its largest square
   2: public class MatrixAnalyzer
   3: {
   4:     // gets the matrix to analyze
   5:     public int[,] Matrix { get; private set; }
   6:  
   7:     // gets the row count
   8:     public int Rows
   9:     {
  10:         get
  11:         {
  12:             return Matrix.GetLength(0);
  13:         }
  14:     }
  15:  
  16:     // gets the column count
  17:     public int Columns
  18:     {
  19:         get
  20:         {
  21:             return Matrix.GetLength(1);
  22:         }
  23:     }
  24:  
  25:     // initializes a new analyzer given a matrix
  26:     public MatrixAnalyzer(int[,] matrix)
  27:     {
  28:         if (matrix == null) throw new ArgumentNullException("matrix");
  29:  
  30:         Matrix = matrix;
  31:     }
  32:  
  33:     // walk through finding the largest square from the back of the matrix
  34:     // forward, using the scratchpad to build up our current sizes
  35:     public Tuple<Point, int> FindLargestSquare()
  36:     {
  37:         int maxRow = 0;
  38:         int maxCol = 0;
  39:  
  40:         var scratchPad = new int[Rows, Columns];
  41:  
  42:         for (int row = Rows - 1; row >= 0; --row)
  43:         {
  44:             for (int col = Columns - 1; col >= 0; --col)
  45:             {
  46:                 scratchPad[row, col] = (Matrix[row, col] == 1) ? GetRank(scratchPad, row, col) + 1 : 0;
  47:  
  48:                 if (scratchPad[row, col] > scratchPad[maxRow, maxCol])
  49:                 {
  50:                     maxRow = row;
  51:                     maxCol = col;
  52:                 }
  53:             }
  54:         }
  55:  
  56:         return Tuple.Create(new Point { X = maxRow, Y = maxCol }, scratchPad[maxRow, maxCol]);
  57:     }
  58:  
  59:     // helper method to get the rank of the scratchpad square considering the squares
  60:     // to the right, below, and right & below.
  61:     private int GetRank(int[,] scratchPad, int row, int col)
  62:     {
  63:         return Math.Min(
  64:             Math.Min(GetValue(scratchPad, row, col + 1), GetValue(scratchPad, row + 1, col)),
  65:             GetValue(scratchPad, row + 1, col + 1));
  66:     }
  67:  
  68:     // helper method to get value of scratch pad considering limits
  69:     private int GetValue(int[,] scratchPad, int row, int col)
  70:     {
  71:         return row < Rows && col < Columns ? scratchPad[row, col] : 0;
  72:     }
  73: }

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 Monday, April 27, 2015 10:24 PM | Comments (1) |

Thursday, April 23, 2015

St. Louis .NET User Group

Hey folks, I won’t be posting a new Little Wonders of C# 6 post (you can see my previous posts here) this week.  I’ve been preparing a presentation for the St. Louis .NET User Group about all the new C# 6 goodness.  If you’ve enjoyed these posts and are in the St. Louis area on April 27th, feel free to pop in and have a listen!  I’ll be covering some new wonders I haven’t had a chance to blog about yet.

For more information, go to the St. Louis .NET User Group site here.

Hope to see you there! 

Stay tuned monday for my solution to this week’s Little Puzzler: Largest Square in a Matrix, and then I’ll be back next Thursday with the next Little Wonder of C# 6 blog entry.

Happy Coding!

Posted On Thursday, April 23, 2015 10:59 AM | Comments (0) |

Monday, April 20, 2015

Little Puzzlers–Largest Square of ‘1’s in a Matrix

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.

Another fun one that I enjoyed solving.  As usual with these problems, there’s a fairly straightforward solution -- and a very efficient but harder to find solution.

The Problem

Given a square 2D array of 1s and 0s, find the starting position (top left row, column) and size of the largest, solid square of 1s in the matrix.  Try to find the most efficient (performance-wise) solution possible.  The solution need not be memory constant, but should not modify the original data.

For example, if the matrix were:


0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0

The answer would be a square of size 3 at (row 5, column 5).

You may assume the following:

  • The matrix is square (i.e. n x n)
  • A lone 1 is a square of size 1.
  • The square must be solid (no holes), but may be embedded in a larger, non-square shape.
  • The rows and columns for the starting position are zero-indexed

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 Monday, April 20, 2015 11:38 AM | Comments (7) |

Thursday, April 16, 2015

C#/.NET Little Wonders: Static Using Statements 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.

For those who haven’t been keeping up with the announcements, I’m taking some blog time for a few Little Wonders posts to talk about some of the neat new things that will be in C# 6. 

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.

Importing a whole namespace with “using”

Of course, we all know that you can import a namespace with using.  This gives us the ability to use a type with just the type’s name in our code.  That is, it allows us to use the type name directly without the need of fully qualifying it with it’s namespace.

For example, if we didn’t import the System namespace, we’d have to say:

public class Driver
{
    public static void Main()
    {
        // without importing a namespace, we'd have to fully qualify the type
        // Console as System.Console
        System.Console.WriteLine("Hello, World!");
    }
}

But, of course, we can import the System namespace, so that allows us to shorten the call to just:

using System;
 
public class Driver
{
    public static void Main()
    {
        Console.WriteLine("Hello, World!");
    }
}

This eliminates a lot of redundant “System.” prefixes in our code.  But this is all old stuff, why bring it up?  Mostly, I wanted to set the stage for what using does today so I can discuss what changes have been made with the new using static directive in C# 6.

Importing a static class with “using static”

Now, in C# 6, we can go one step further and import the static members of a class into our namespace.  This means we can use the static members of a class directly with no need to qualify them with their namespace or type name!

The format is “using static” followed by the type whose static methods you wish to import.  For example, our short example before now becomes:

using static System.Console;
 
public class Driver
{
    public static void Main()
    {
        // Now, the System.Console static class is imported, so we
        // can use WriteLine directly
        WriteLine("Hello, World!");
    }
}

This may seem trivial, but it can eliminate a lot of redundant or superfluous type identifiers in the code and thus help improve readability (if used appropriately). 

Note: In previous previews, the format was simply using without the static keyword, and only worked on static classes.  In the current preview, the format has changed to using static and can import static members of any type (class, struct, enum).

Think, for example, of static classes like Math where it is simply a collection of mathematical functions.  The “Math.” prefix really doesn’t add much to the readability because we know Sqrt() is a math function, so we can drop it with a using static System.Math like this:

using static System.Console;
using static System.Math;
 
public class Driver
{
    public static void Main()
    {
        // Now we can access Sqrt directly since we imported System.Math
        WriteLine("Hello, World: the square root of 4 is " + Sqrt(4));
    }
}

Or consider static classes like Enumerable that have a lot of nice static methods like Range() and Repeat().  Again the “Enumerable.” prefix doesn’t add much to the readability, so why not drop it with a static import?

using static System.Linq.Enumerable;
 
public class Driver
{
    public static void Main()
    {
        // Now, Enumerable.Range() can just become Range()
        var nums = Range(1, 10).ToArray();
 
        ...
    }
}

As you can see, this shortens the body of our code and eliminates unnecessary identifiers.  Obviously, you’ll want to use this with care.  There are probably some instances where including the type name improves readability (that is, if you can’t easily tell the original of the method without it from the context).  As such, make sure you use good judgment on when it improves readability and when it doesn’t.

Limiting Extension Method visibility with “using static”

Here’s one very big reason I’m excited about using static: I love extension methods.  I do not love abusing them, but I do love well designed extension methods and think they can really improve your code if used judiciously.  The problem with extension methods is that even the well-written ones can pollute your namespace (and IntelliSense) if you have a lot of them extending some of the more common types (like string or object).

One way to limit this impact would be to put your extension methods into very compartmentalized namespaces and only import the namespace you want.

For example, let’s say I have a namespace called Utilities.Extensions and under it I have extensions for:

  • Preconditions – extensions to allow me to create test preconditions much like Google Guava in Java
  • Strings – extensions to allow me to check strings for certain formats
  • Typeextensions for querying properties of types
  • etc.

If all of these static classes with their extensions were in the same namespace, and I did an import such as:

// imports the whole namespace including all extension methods
using Utilities.Extensions;

Then all of the extension methods becomes implicitly visible whether I want them or not.  It would be nice to isolate them.  So I could put each of the static classes in their own namespace, but then I’d have namespaces for Utilities.Extensions.Preconditions just to hold a Preconditions static class, which seems a bit redundant.

Instead, I can now take advantage of using static and just include the extension methods from the class that I want, which will only make those extension methods visible without an explicit reference:

// only Preconditions and it's extension methods will be visible
using static Utilities.Extensions.Preconditions;

Now, only the extension methods in Preconditions will be visible without an explicit reference, and all the other extension methods in Utilities.Extensions will not be imported.

Importing enum constants with “using static”

As I alluded to before, in the current preview you can also import the static members of any type, not just static classes.  This means you can import the constants of an enum (static by definition) so you do not need to explicitly qualify them.

Consider if you wanted to do a lot of console output with multiple colors.  You’d make use of the System.Console class and the System.ConsoleColor enum.  This would mean that you’d have to use a lot of code like:

Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("This is my output in red");
 
Console.ForegroundColor = ConsoleColor.White;
Console.WriteLine("This is my output in white");
 
Console.ForegroundColor = ConsoleColor.Blue;
Console.WriteLine("This is my output in blue");

Now, we know we can eliminate the “Console.” with a using static System.Console, but we can also eliminate the need to qualify the constants of the enum by performing a using static System.ConsoleColor as well, this would shorten it to:

ForegroundColor = Red;
WriteLine("This is my output in red");
 
ForegroundColor = White;
WriteLine("This is my output in white");
 
ForegroundColor = Blue;
WriteLine("This is my output in blue");

This eliminates a lot of very redundant qualifiers that don’t really improve the quality of the code.

Summary

The new using static directive allows us to import the static members of a type without needing to qualify them with their type name.  This can help improve readability and maintainability in your code.  Of course, as with any syntactical sugar, you should be careful not to abuse this power.  If the addition of the qualifying type name actually improves the readability of the code, then by all means keep it.  But for cases where the qualifying type name becomes redundant or superfluous, feel free to utilize the new using static to eliminate the need to explicitly state it.

Thanks for reading and stay tuned for more features of C# 6!

Posted On Thursday, April 16, 2015 8:14 PM | Comments (7) |

Powered by: