Friday, January 30, 2009

Conceptual blocks and programming tasks. Part II.

In the previous post I offered the following problem to solve:
The input data is the graph representation, for example the instance of LinkedList class. The output is Boolean value which is true if the graph has the cycle and false otherwise. The constraints are no additional memory should be used.
Let me publish the solution and the comments.

The solution.
To show the solution, I would like to use C# language. I realized that LinkedList<T> class which I referred in the puzzle definition can't represent the graph that has cycles because the methods of this class don't allow to set the next and previous node to the node which already belongs the list. So, the following class is used to show the solution.

internal class GraphNode<T>
   private T _value;
   private GraphNode<T> _next;
   public GraphNode(T value)
      _value = value;
   public GraphNode<T> Next
      get{ return _next;}
      set{ _next = value;}
   public override string ToString()
      return _value.ToString();

And here is the solution:

static bool HasCycle<T>(List<GraphNode<T>> list)
   if (list == null)
      throw new ArgumentNullException("list");
   if (list.Count == 0)
      throw new ArgumentException("empty list", "list");
   GraphNode<T> current1 = list[0];
   GraphNode<T> current2 = list[0];
      if (current1.Next == null || current2.Next == null || current2.Next.Next == null)
         return false;
      current1 = current1.Next;
      current2 = current2.Next.Next;
      if (ReferenceEquals(current1, current2))
         return true;
   } while (current1 != null && current2 != null);
   return false;

The Analysis.
The idea behind the scene is very simple. The solution is using two pointers to the graph nodes, the first pointer goes through the graph with step 1(current1=current.Next) and the second pointer goes through the graph with step 2(current2=current.Next.Next). If the graph has the cycle, these two pointers will refer to the same node at some point which is obvious.However, I seen a lot of situations when people were not able to solve this puzzle quickly or didn't solve it at all.When I was asked to solve this puzzle several years ago I didn't solve it as well. And the reason of that is the conceptual blocks.
When I studied at the university, we learned the common algorithms and implemented them quite intensively. A lot of the algorithms dealt with the graphs - visiting the graph nodes, finding the shortest way between two graph nodes, etc. I used to use single pointer to the graph nodes for these algorithms. After more than 5 years this habit still persisted. This is some sort of the stereotype which is definitely the conceptual block. The second block is the same as I shown in the previous post - the tendency to delimit the problem area poorly. Sometimes people restrict themselves to using the single pointer. If one would know about the conceptual blocks and control the process of the problem solving, the "finding the cycle in the graph" become the pretty trivial task.

Monday, January 26, 2009

Conceptual blocks and programming tasks.

One of my favorite nonfictional books is “Conceptual Blockbusting” by James L. Adams. The book describes the conceptual blocks which are “mental walls that blocks the problem solver from correctly perceiving a problem or conceiving its solution”. There is the set of puzzles that intended to understand how the conceptual blocks can hamper the problem solving. I believe that reading this book can really help you to become a better thinker. Indeed it’s helpful if you aren’t a genius like Albert Einstein. Every time I read this book I try to figure out how the conceptual blocks can hamper the solving of the problems that I face doing my job every day. And recently I found the interesting issue…

Delimiting the problem area poorly.
One of the perceiving conceptual blocks is tendency to delimit the problem too closely. It is demonstrated using the following puzzle:
Draw no more than four straight lines without lifting the pencil from the paper which will cross through all nine dots:
Work on it a while. One possible solution is shown here
A lot of people don’t exceed the imaginary boundary even though it is not in the definition of the problem at all. The overly strict limits are a block in the mind of the solver.

Find cycle in the graph puzzle
Consider the following puzzle.
The input data is the graph representation, for example the instance of LinkedList class. The output is Boolean value which is true if the graph has the cycle and false otherwise. The constraints are no additional memory should be used.
Try to solve this puzzle. In the next post I will explain the issues that hamper this puzzle solving and why they appear.

Saturday, January 24, 2009

C# 4.0 - the first look at the DYNAMICITY.

This week I looked at C# dynamic features that were added in C# 4.0 CTP and Visual Studio 2010. Tremendous amount of resources have appeared on dynamic features of C# over the web. C# developers provided the description of dynamic features on their blogs, i.e. Sam Ng’s blog and Chris Borrows’ blog have the great posts about the topic. However, not all the dynamic features are available in C# 4.0 2008 CTP. I.e. a lot of samples listed in the mentioned blogs don’t event compile in the current VS.NET 2010 preview. So I didn’t dive in the specific language constructions and tricks. What makes me excited is step forward to “dynamicity” in .NET. I never worked with dynamic languages before but apparently it’s about time to learn more about the dynamic languages facilities. Well, I found MSDN magazine article called CLR Inside out: IronPython and read the beautiful thing:

The most common question I hear about dynamic languages is "why should I use them?" Trying to show a longtime C++ or C# developer that a dynamic language is useful for problems outside the scripting domain is difficult. One concrete benefit of dynamic languages is that they facilitate an iterative development cycle. The interactive capabilities of dynamic languages make them a better match for this type of cycle than compiled languages. Developers can focus on exploring and prototyping functionality, refactoring if necessary, and then repeating with new functionality. This allows for a more exploratory process of development than the code/build/run/debug loop that most other languages constrain the programmer to.

So, the dynamic language, well C# 4.0, will allow transition from code/build/run/debug loop to evaluation/print loop? Yes, in PDC 2008 “Future of C#” talk Anders Hejlsberg shows it in action and it looks amazing. The new language features like dynamic type, IDynamicLanguage interface, optional and named parameters also look very promising. Next week I will try to work with C# 4.0 as with dynamic language, I think the best way to do this is get some problem, solve it using C# 3.0(statically typed language), then solve it using C#4.0(dynamic language). I will write about any interesting stuff.

Tuesday, January 13, 2009

The Error Message - the fresh glance.

December 2008 issue of MSDN magazine introduces the new column called Usability in Practice. January 2009 issue includes the first Usability in Practice article from which I learned something new.
The article itself isn't very worth. Almost entire content of the article is brief description of Error Message guidelines part of Windows Vista Users Experience Guidelines. Error message guideline has the great, comprehensive and straightforward directions of how the application error messages should be constructed. Actually the guideline has two logical parts - what information should be presented by the error message and how the error message should look like. The first part is quite clear and just tells us which points and questions we should consider for good error messages constructing. The second part - how the error message dialog should look like - is the thing which this post about.

Task Dialog
Windows Vista introduces a new standard dialog box called task dialog. According to the error messages guideline the task dialogs should be used to show the error message if the error can't be fixed immediately, if the error isn't contextual user input problem and if the error isn't delayed detected problem. I.e. When Things Go Wrong article demonstrates how the simple error message can be presented by the task dialog. Here is the table that shows the correspondence between the task dialog areas and the simple error message parts.
Task dialog areaError message part
Title barA problem. States that a problem occurred.
Main instructionA cause. Explains why the problem occurred.
Content areaA solution. Provides a solution so that users can fix the problem.
Command areaCommit button(Close).

Using task dialog in .NET application.
The managed code can create and show the task dialog using the corresponding API. The example of wrapping task dialog API in the managed code can be found in CodeProject.
But the task dialog API is supported only by Vista. What about earlier versions of Windows? Which dialog we should use for show the error message if the application is run in Windows XP? What about using MessageBox class? Unfortunately, MessageBox dialog doesn't allow distinguish between the main instruction area and the content area which I referred above. However, I think we definitely should follow the error message guideline and at least simulate the task dialog for non-Vista(and non-Windows 7) OS. At least for the simple error message we should show the dialog which has the parts described above. Here is the very basic sample of error message dialog that can be used in Windows XP:

The sample of task dialog emulator can be found in CodeProject as well. However, if I need to show the simple error messages only, I would implement the simple task dialog emulator like one that is shown in the picture above.

I will definitely follow the error message guideline in the future and revise the existing error messages in the product I actively work on.

Monday, January 12, 2009

My first experience with Windows 7

Recently Microsoft has knocked out Windows 7 beta and published the build for testing purposes. I was not excited about the new version of Windows at all. I remember the experience with the first beta release of Windows Vista - I installed it and then stopped using in 2 or 3 days. The main reasons were - I was not able to install drivers for the sound card, the new interface seemed terrible for me, Windows Vista seemed working slowly than Windows XP and so on. As far as I know, in our days Windows XP is still being chosen over Windows Vista for the majority of business computer sales, so I am sure that I am not only person who stopped using Vista once looked at the first beta release. However, for now I had the new motivation to install Windows 7 - I wanted to see whether the product I work on - Data Dynamics Reports - can be used on Windows 7. This is what I really excited about. In this post I briefly describe the Windows 7 installation experience and the point where I decided to stop using it - yep, again!

The Installation
The installation of Windows 7 is pretty intuitive and requires very few actions from end-user. The thing I loved is my motherboard integrated devices were detected and installed properly. I thought that it would be a problem because the motherboard drivers for Windows XP and Vista are not compatible with the new OS. However, this fact didn't become the problem at all. The only problem with the installation I faced is "applying personal settings hang" during the first run. However, this problem isn't specific for Windows 7 and I managed it by rebooting the machine several times, starting windows 7 in safe mode and then starting it normally. Sounds crazy, but it works:)

The first run.
During the first run I faced the problem with WinMail service. It used 100% CPU during the first run. I managed it by running Windows 7 in safe mode and erasing WinMail.exe file. Sounds crazy but it works.

The end.
Well, I successfully installed and run Windows 7 and I thought that I probably was wrong and Microsoft did the great job this time and probably I can use Windows 7 as the primary OS. The new OS interface looks great and it is very convenient. Various software is being installed just fine. The idyll finished when I tried to install Visual Studio .NET 2008. I was not able to install it. The setup is run, the first window with choices to install VS.NET, install MSDN and check for the new releases appeared. I selected install VS.NET and nothing happened. The main window closed, no new processes were run. I tried to run VS.NET 2008 setup with administrator privileges, this doesn't help. I tried setting the compatibility mode for setup.exe and this doesn't help as well. Visual Studio .NET 2005 can't be installed as well with the same symptoms. This looks as weird fact for me - Microsoft software can't be installed on Microsoft OS. And indeed I don't want using OS that doesn't allow installing Visual Studio. This is how my experience with Windows 7 has finished...

PS. If someone reads this blog and uses Windows 7 beta and was able to install VS.NET 2005(2008) please tell me the secret of the success.