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

There’s really no “ah-hah!” moment with this problem, but it is still – I find – a good programming problem for seeing how well a candidate’s mind works in structuring logic and finding patterns.

### The Problem

Given a positive integer (i.e. > 0), please return a string representation of that integer using Roman Numerals. You may assume IV for four, though you can optionally use IIII if you prefer the standard clock representation of 4.

*Interesting side note: some say that the reason IIII is used instead of IV on clocks is because IV represented the Roman god Jove, and thus was omitted from the clock face to avoid “blasphemy”.*

If you’re not familiar with Roman Numerals, you can find a good primer nearly anywhere on the internet (such as __here__ on Wikipedia), though the basics are:

- I = 1
- V = 5
- X = 10
- L = 50
- C = 100
- D = 500
- M = 1000

Roman numerals are generally written from highest denominate to lowest denomination, except where the previous “unit” letter is used to create 1 of the previous “unit” less than the next.

- I can be placed before V and X to make 4 (IV) and 9 (IX) respectively
- X can be placed before L and C to make 40 (XL) and 90 (XC) respectively
- C can be placed before D and M to make 400 (CD) and 900 (CM) respectively.

Note that V, L, and D are not used to prefix the next number since this would obviously be redundant (i.e. VX is the same as V, LC is the same as L).

### Spoiler Alert!

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

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

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!