James Michael Hare

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

Article Categories

Archives

Image Galleries

Tuesday, May 5, 2015

Little Puzzlers–Positive Integer to Roman Numerals

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.

Posted On Tuesday, May 5, 2015 2:48 AM | Comments (9) |

Thursday, April 30, 2015

No new Little Wonders of C# 6 this week

Sorry folks, I totally intended to write a new Little Wonders of C# 6 post this week, but have been ill.  I fully intend to continue next week with a new puzzler and a new Little Wonder.

Until then, check out my previous post on The Little Wonders of C# 6 - a Presentation.

Thanks!

-Jim

Posted On Thursday, April 30, 2015 7:58 PM | Comments (2) |

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 (4) |

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

Powered by: