Monday, April 27, 2015

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.

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):

We 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):

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:

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**.

Thursday, April 23, 2015

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!

Monday, April 20, 2015

*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.

Thursday, April 16, 2015

*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*
**Type** – *extensions 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!