Want to show your appreciation?
Please a cup of tea.

Monday, May 30, 2011

Solve Outset Media Puzzle

I was playing with my kids during the long weekend and we were trying to solve a puzzle, 36 piece Tropical Fish, made by Outset Media.  I have to admit that it was indeed “extremely difficult”, which are the words printed on the box. We gave up in the end. But in order to turn this activity into some positive result, I decided to show my kids how one can write a problem and get the computer to do the job for us. And here we start…

Basic Elements

Working with my kids we quickly identified that we need express each piece by its face and four sides. So let’s start with the definition of a piece and its face and sides.

Face enum

With extremely limited knowledge of tropical marine fish. We worked together to came up with below names.

   1:      public enum Face
   2:      {
   3:          Puffer,
   4:          Tang,
   5:          Rainbow,
   6:          Clown,
   7:          Zebra,
   8:          Stars,
   9:      }

Side enum

These names are even more farcical. But our goal was to have something that easy to remember, and each has a different first character so only one letter is needed in the printed out.

   1:      public enum Side
   2:      {
   3:          Red,
   4:          Angel,
   5:          WhiteHorse,
   6:          GreenHorse,
   7:          Strips
   8:      }

Piece class

   1:      public class Piece
   2:      {
   3:          public int Id { get; set; } // we assign a unique sequential id to search piece
   4:          public Face Face { get; set; }
   5:          public Side Top { get; set; }
   6:          public Side Bottom { get; set; }
   7:          public Side Left { get; set; }
   8:          public Side Right { get; set; }
   9:   
  10:          public override string ToString()
  11:          {
  12:              return Face + "-" + Id;
  13:          }
  14:      }

An Organized Box

Just like when we were doing the puzzle manually, we need a place to store and organize the pieces before they gets put into the puzzle. We let the Box do this job, and we also define all the pieces in the box just as what we got when the box was opened.

   1:  public class Box
   2:  {
   3:      readonly int _count;
   4:      readonly List<Piece> _pieces =
   5:          new List<Piece>
   6:              {
   7:                  new Piece {Face = Face.Clown, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Angel, Left = Side.WhiteHorse,}, //0
   8:                  new Piece {Face = Face.Clown, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.WhiteHorse, Left = Side.Red,},
   9:                  new Piece {Face = Face.Clown, Top = Side.Angel, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.Red,},
  10:                  new Piece {Face = Face.Clown, Top = Side.WhiteHorse, Right = Side.Red, Bottom = Side.Angel, Left = Side.GreenHorse,},
  11:                  new Piece {Face = Face.Clown, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.WhiteHorse, Left = Side.Red,},
  12:                  new Piece {Face = Face.Clown, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.WhiteHorse,},
  13:   
  14:                  new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.WhiteHorse,}, //6
  15:                  new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.Red, Bottom = Side.GreenHorse, Left = Side.WhiteHorse,},
  16:                  new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.WhiteHorse,},
  17:                  new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.Angel, Left = Side.WhiteHorse,},
  18:                  new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.Red, Left = Side.Strips,},
  19:                  new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Strips, Left = Side.WhiteHorse,},
  20:   
  21:                  new Piece {Face = Face.Tang, Top = Side.WhiteHorse, Right = Side.Angel, Bottom = Side.Red, Left = Side.GreenHorse,}, //12
  22:                  new Piece {Face = Face.Tang, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.WhiteHorse,},
  23:                  new Piece {Face = Face.Tang, Top = Side.Angel, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Red,},
  24:                  new Piece {Face = Face.Tang, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.WhiteHorse, Left = Side.Red,},
  25:                  new Piece {Face = Face.Tang, Top = Side.Strips, Right = Side.WhiteHorse, Bottom = Side.Angel, Left = Side.GreenHorse,},
  26:                  new Piece {Face = Face.Tang, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.Angel,},
  27:   
  28:                  new Piece {Face = Face.Stars, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Red, Left = Side.Strips,}, //18
  29:                  new Piece {Face = Face.Stars, Top = Side.Red, Right = Side.WhiteHorse, Bottom = Side.Angel, Left = Side.GreenHorse,},
  30:                  new Piece {Face = Face.Stars, Top = Side.Strips, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Angel,},
  31:                  new Piece {Face = Face.Stars, Top = Side.Angel, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Strips,},
  32:                  new Piece {Face = Face.Stars, Top = Side.Strips, Right = Side.Red, Bottom = Side.WhiteHorse, Left = Side.GreenHorse,},
  33:                  new Piece {Face = Face.Stars, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.WhiteHorse, Left = Side.Strips,},
  34:   
  35:                  new Piece {Face = Face.Zebra, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.Red, Left = Side.GreenHorse,}, //24
  36:                  new Piece {Face = Face.Zebra, Top = Side.Angel, Right = Side.Red, Bottom = Side.GreenHorse, Left = Side.Strips,},
  37:                  new Piece {Face = Face.Zebra, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.WhiteHorse, Left = Side.Red,},
  38:                  new Piece {Face = Face.Zebra, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.Strips, Left = Side.Red,},
  39:                  new Piece {Face = Face.Zebra, Top = Side.Red, Right = Side.Angel, Bottom = Side.Strips, Left = Side.GreenHorse,},
  40:                  new Piece {Face = Face.Zebra, Top = Side.Red, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Angel,},
  41:   
  42:                  new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.Strips,}, //30
  43:                  new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.Angel,},
  44:                  new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.Angel, Left = Side.GreenHorse,},
  45:                  new Piece {Face = Face.Rainbow, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Strips, Left = Side.Red,},
  46:                  new Piece {Face = Face.Rainbow, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.Red,},
  47:                  new Piece {Face = Face.Rainbow, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.WhiteHorse, Left = Side.Angel,},
  48:              };
  49:   
  50:   
  51:      public Box()
  52:      {
  53:          _count = _pieces.Count;
  54:   
  55:          for (int i = 0; i < _count; i++)
  56:          {
  57:              _pieces[i].Id = i;
  58:          }
  59:      }
  60:   
  61:      public Piece Take(int index, Predicate<Piece> condition)
  62:      {
  63:          for (int i = index; i < _count; i++)
  64:          {
  65:              var piece = _pieces[i];
  66:              if (piece == null) continue;
  67:              if (condition(piece))
  68:              {
  69:                  _pieces[i] = null;
  70:                  return piece;
  71:              }
  72:          }
  73:          return null;
  74:      }
  75:   
  76:      public void Return(Piece piece)
  77:      {
  78:          _pieces[piece.Id] = piece;
  79:      }
  80:  }

In the Box class, we first defined all 36 pieces in a list. Then in the constructor Box(), we gave each piece a unique ID, which is same as its position in the list. We then defined two methods to control the taking and returning of the pieces.

When a piece is taken from the box by using the Take() method, we need to specify a starting index and the condition to search for a matching piece. The starting index is important so that we don’t retry pieces that we already did. The condition is passed in according to the rules of the puzzle and the pieces already put on the puzzle.

When we are stuck, we need to be able to return the piece back and try next. The Box’s Return() method does this job by putting the piece back to its original position in the list.

The Solver

The solver has a box and a table to solve the puzzle, they are defined and initialized in line 4 and 5. The Main method is the C#’s entry point. It simply calls FindSolution() method to find the solutions, when no solution is found, it displays an error message.

The core logic resides in two methods, FindSolution() and CheckPiece().

CheckPiece verifies if a new piece fits with pieces were already put on the puzzle. It checks:

  • The top edge of the piece matches the bottom of the piece above it, unless the new piece will be put on the first row.
  • The left edge of the piece matches the right side of the piece on its left, unless the new piece will be put on the first column.
  • There is no piece already on the puzzle in the same row has same face as the one being checked. (Sudoku)
  • There is no piece already on the puzzle in the same column has same face as the one being checked. (Sudoku)

FindSolution goes through each spot of the puzzle from left to right and top to bottom. It tires each piece one by one until the last spot is filled. When it is stuck, it returns the last piece back to the box and try next one.

When a solution is found, PrintSolution() method is called to print out the layout of the pieces in the solved puzzle.

   1:  public class Solver
   2:  {
   3:      private const int _size = 6;
   4:      static Piece[,] _puzzle = new Piece[_size,_size];
   5:      static Box _box = new Box();
   6:   
   7:      public static void Main()
   8:      {
   9:          if (FindSoution() == 0)
  10:          {
  11:              Console.WriteLine("No Answer :(");
  12:          }
  13:      }
  14:   
  15:      private static int FindSoution()
  16:      {
  17:          var count = 0;
  18:          var i = 0;
  19:          for (; ; )
  20:          {
  21:              var col = i % _size;
  22:              var row = i / _size;
  23:   
  24:              var index = 0;
  25:              var piece = _puzzle[row, col];
  26:              if (piece != null) // if we already tried one or more pieces
  27:              {
  28:                  _puzzle[row, col] = null; // clear
  29:                  _box.Return(piece); // return it back to box
  30:                  index = piece.Id + 1; // and start search for one after it.
  31:              }
  32:   
  33:              piece = _box.Take(index, x => CheckPiece(row, col, x));
  34:              if (piece == null)
  35:              {
  36:                  if (i == 0) return count;
  37:                  i--;
  38:                  continue;
  39:              }
  40:              _puzzle[row, col] = piece;
  41:              if (i != _size * _size - 1)
  42:              {
  43:                  i++;
  44:                  continue;
  45:              }
  46:              ++count;
  47:              Console.WriteLine("Answer " + count);
  48:              PrintSolution(Console.Out, _puzzle);
  49:          }
  50:      }
  51:   
  52:      private static bool CheckPiece(int row, int col, Piece x)
  53:      {
  54:          if (row != 0 && _puzzle[row - 1, col].Bottom != x.Top ||
  55:              col != 0 && _puzzle[row, col - 1].Right != x.Left)
  56:          {
  57:              return false;
  58:          }
  59:          // comment below two for loop to find all non-sudoku answers
  60:          for (int i = 0; i < row; i++)
  61:          {
  62:              if (_puzzle[i, col].Face == x.Face) return false;
  63:          }
  64:          for (int i = 0; i < col; i++)
  65:          {
  66:              if (_puzzle[row, i].Face == x.Face) return false;
  67:          }
  68:          return true;
  69:      }
  70:   
  71:      private static void PrintSolution(TextWriter writer, Piece[,] pieces)
  72:      {
  73:          var rows = pieces.GetLength(0);
  74:          var cols = pieces.GetLength(1);
  75:          for (var row = 0; row < rows; row++)
  76:          {
  77:              for (var col = 0; col < cols; col++)
  78:              {
  79:                  writer.Write(string.Format("   {0}     ", 
  80:                      pieces[row, col].Top.ToString()[0]));
  81:              }
  82:              writer.WriteLine();
  83:              for (var col = 0; col < cols; col++)
  84:              {
  85:                  var piece = pieces[row, col];
  86:                  writer.Write(string.Format("{0} {1} {2} ", 
  87:                      piece.Left.ToString()[0], 
  88:                      piece.Face.ToString().Substring(0, 4), 
  89:                      piece.Right.ToString()[0]));
  90:              }
  91:              writer.WriteLine();
  92:              for (var col = 0; col < cols; col++)
  93:              {
  94:                  writer.Write(string.Format("   {0}     ", 
  95:                      pieces[row, col].Bottom.ToString()[0]));
  96:              }
  97:              writer.WriteLine();
  98:          }
  99:      }
 100:  }

Solution

There is only one solution if the Sudoku rules is considered. The program quickly finds the solution below:

   R        G        A        W        A        G     
G Zebr A A Rain S S Star G G Clow R R Tang W W Puff S 
   S        W        R        A        G        A     
   S        W        R        A        G        A     
W Clow G G Tang A A Zebr W W Puff S S Star R R Rain G 
   A        R        G        G        W        S     
   A        R        G        G        W        S     
W Puff G G Star W W Clow R R Zebr S S Rain G G Tang W 
   S        A        A        W        A        A     
   S        A        A        W        A        A     
A Star W W Puff R R Tang G G Rain S S Zebr R R Clow S 
   G        G        W        A        G        G     
   G        G        W        A        G        G     
W Tang R R Clow A A Rain S S Star W W Puff R R Zebr A 
   S        W        G        G        S        S     
   S        W        G        G        S        S     
R Rain G G Zebr S S Puff A A Tang R R Clow G G Star R 
   A        R        R        S        W        W     

If the Sudoku rules is not considered, there are total 608 solutions. It took the program a few hours to find all of those.

Some additional interesting facts are:

  1. When Sudoku rule is considered, the program made 647,970 calls to Box.Take() and 8,803,132 calls to CheckPiece() to find the solution in 2 seconds.
  2. When Sudoku rule is NOT considered, it took 45 seconds to find the first solution after 30,701,706 calls to Box.Take() and 235,103,280 calls to CheckPiece().

Saturday, May 28, 2011

Replacement of TypeNode.GetTypeNode() in FxCop 1.36 and Above

I encountered a number of custom rules written for FxCop 1.35 in a project. They need to be upgraded to FxCop 1.36. Those custom rules make extensive use of TypeNode.GetTypeNode() method, which does no longer exist in the FxCop 1.36 and above (including Visual Studio build-in Code Analysis).

As Google returned no useful result, I started to explore the new SDK API for an alternative. I found two ways to get a TypeNode instance.

  • TypeNodes predefined FrameworkTypes class, if the type you want is not there than,
  • ModuleNode.GetType() method with a namespace and type name.

Get an instance of ModuleNode is easy by a location string that I can obtain from a type object, so this sounds like a viable solution:

   1:   return AssemblyNode.GetAssembly(type.Module.Assembly.Location)
   2:      .GetType(Identifier.For(type.Namespace), Identifier.For(type.Name));

Code above works great until I encountered nested types. In the case of nested types, the code above just return null. I have used all different combinations of the name, say for a nested type NestedType in MyNamespace.MyType, in below. None of those worked.

Namespace parameter Name parameter
Namespace MyType+NestedType
Namespace MyType.NestedType
Namespace.MyType NestedType

 

Further investigation found me the method TypeNode.GetNestedType. It turned out that you must get the parent type first, then call that method to get the TypeNode for the nested type. Once this is resolved, I have perfectly working alternative to the missing GetTypeNode in FxCop 1.36. Below are the extension methods to achieve this:

   1:  public static TypeNode GetType(this ModuleNode @this, Type type)
   2:  {
   3:      if (@this == null) { throw new ArgumentNullException("this"); }
   4:      if (type == null) { throw new ArgumentNullException("type"); }
   5:      return GetType(@this, type.DeclaringType, type, Identifier.For(type.Namespace));
   6:  }
   7:   
   8:  private static TypeNode GetType(this ModuleNode @this, Type parent, Type type, Identifier @namespace)
   9:  {
  10:      if (parent == null) return @this.GetType(@namespace,Identifier.For(type.Name));
  11:      var parentType = GetType(@this, parent.DeclaringType, parent, @namespace);
  12:      return parentType.GetNestedType(Identifier.For(type.Name));
  13:  }
  14:   
  15:  public static AssemblyNode GetAssemblyNode(this Type @this)
  16:  {
  17:      if (@this == null) throw new ArgumentNullException("this");
  18:   
  19:      return AssemblyNode.GetAssembly(@this.Module.Assembly.Location);
  20:  }
  21:   
  22:  public static TypeNode GetTypeNode(this Type @this)
  23:  {
  24:      if (@this == null) throw new ArgumentNullException("this");
  25:      return @this.GetAssemblyNode().GetType(@this);
  26:  }

As a side note, if you found yourself calling GetTypeNode with a known type, you should define a static field to improve the performance. Just like what was in the FrameworkTypes class. For example, I have below in my project:

   1:  public static readonly TypeNode CompilerGeneratedAttribute = typeof(CompilerGeneratedAttribute).GetTypeNode();
   2:  public static readonly TypeNode DebuggerNonUserCodeAttribute = typeof(DebuggerNonUserCodeAttribute).GetTypeNode();
   3:  public static readonly TypeNode GeneratedCodeAttribute = typeof(GeneratedCodeAttribute).GetTypeNode();
   4:  public static readonly TypeNode IComponent = typeof(IComponent).GetTypeNode();
   5:  public static readonly TypeNode FrameworkElement = typeof(FrameworkElement).GetTypeNode();

Sunday, May 08, 2011

Worrying School Administration in a Reputable School District

Today, I received an email from parents of a six years old primary school girl. I shocked on what a school administration did to the little soul. Adding further concerns to the worrying education system in America. Below is the full letter.


A Terrible Thing Happened at the Dutch Neck School

A terrible thing happened to our daughter few weeks ago. She is six and a half years old and a first grader at the Dutch Neck School in West Windsor. We send this email to you because we don't want the same thing to happen to your kids as well.

On Tuesday, March 29, our daughter took two bottles of water (Poland Spring 8oz) to school. She had been taken water to school since the first day she joined the Dutch Neck school. She used to take a large bottle (16oz). On that Tuesday, we asked her to take two small bottles. One is for snack time at classroom, and one is for lunch time because we did not want her to always drink juice or cold milk during lunch time. On that day, our daughter went into the school cafeteria with one bottle of water, and put it under her arm while holding a tray to pick up her lunch. The cafeteria manager stopped her before she checked out and said she stole the water from school. Our daughter explained that she brought the water from home, but the cafeteria staff did not believe her and insisted that she was lying. As a result, our daughter was brought down to crying and pressured to admit that she was stealing. This is not the end: she was then taken to the Principal’s office and forced to write a confession/I am sorry letter and draw a picture to show the stealing process! When my daughter met the Principal and the Assistant of the Principal, she told them again that she did not steal the water and the water was brought from home, but neither believed her.

They made the decision without any further investigation. They did not check with the parents, and they did not check with our daughter's classmates to see if anyone had seen my daughter with the water bottle on her way from the classroom to the cafeteria. The assistant principal called us two hours later and left a message saying that our daughter stole the water from the school cafeteria and they wanted to talk to us about the consequences.

We found the message at about 9:00pm in the evening. Our daughter was so shocked and scared by the whole experience that she didn’t mention anything after school. We sent two emails to the school immediately and explained that we did ask our daughter to take the water to school since we did not want her drink juice or cold milk during lunch. The next morning (Wednesday), we visited the Principal’s office, explained everything in detail, and requested that the principal check with my daughter's classmates. The principal refused to do so, and insisted that cafeteria manager saw my daughter taking the water from the cafeteria shelf. What the Principal told us was totally different as the cafeteria manager told the superintendent in the following investigation. The cafe manager only saw my daughter putting the water bottle under her arm when she was holding a tray to pick up her lunch. What was more, the Principal told us that they would let my daughter write another sorry letter and there was no recess time for her after lunch at that day.

We left the school with determination to prove our daughter's innocent by ourselves. We emailed to the superintendent and called the Mayor of West Windsor. We checked with the parents of our daughter’s classmates and easily found an eye witness: one of the classmates SAW our daughter taking a water bottle from the classroom to the cafeteria on that day.

On that Thursday afternoon, after the superintendent investigated the issue, we received an email from the principal simply letting us know that this incident was dismissed and the stealing record was withdrawn from our daughter's school report. There is no any word of apology in the email.

We cannot accept this email as the end of the issue. The Principal did not admit to any mistake in the way they had handled the whole thing. They even educated us that our daughter should learn to protect herself at the school! How would we expect a six-year-old girl to clearly articulate her own defense when confronted by the principal and the other figures of authority? Isn’t it fearful to know that the “stealing” report would have followed our daughter’s school record everywhere if we had done nothing? Somebody should say sorry for the wrong-doing.

On the first day of this event, the Principal did not check with either the student’s parents or the classmates, two things that were quite easy to do to find out the truth. On the contrary, they forced a six-year-old girl to admit a false accusation in words, in writing and even in drawing!

On the second day, the Principal took no heed of the parents’ explanation and refused even to do a simple investigation among the students. What was worse, they lied that cafeteria manager saw our daughter taking the water from cafeteria shelf. As mentioned above, the cafeteria manager only saw our daughter putting the water bottle under her arm.

In the whole process of the issue, we did not see the vital responsibility from the Principal to students and parents, we only saw negligence, by which a student’s innocence and future could be easily smeared. It is so easy for them to punish their students, but it is so hard for them to acknowledge their mistakes.

After this event, our daughter kept saying she did not want go to the Dutch Neck School anymore, so we had to transfer her to another school. Isn’t it sad that we cannot even trust the school we are paying tax money for to do the right thing to the kids?

All the parents in our daughter's class feel that the school needs to apologize for what it did to our daughter. We write this email to you and wish to get your support. We did this for our daughter, and for all the Dutch Neck students. Please forward this email to any other parents you know. We truly appreciate all the participation in the attached poll. http://www.surveymonkey.com/s/VPR8BGV