Saturday, 29 March 2014

Advanced Algorithms #1 - Union/Find on Disjoint-set Data Structures.

Code
https://github.com/angellaa/AdvancedAlgorithms

Webcast (in Italian)


Slides






Tuesday, 25 March 2014

Advanced Algorithms #1 - Union/Find on Disjoint-set Data Structures

Questa serie di WebCast ha l'obiettivo ambizioso di aiutarti a costruire competenze algoritmiche avanzate e farti diventare un Top Coder! In ogni lezione, risolveremo insieme un problema complesso per maturare nel tempo un arsenale di tecniche che potrai riutilizzare nell'affrontare qualunque tipo di problema. Scriveremo algoritmi che spesso non sono neanche affrontati in corsi universitari come Depth First Search, Breath First Search, Convex Hull, Kd-Trees, Max Flow, Radix Sort, Suffix Array ecc. Buon divertimento :)

Registrati alla prima sessione: Union/Find on Disjoint-set Data Structures

Eventbrite - Advanced Algorithms #1 - Union/Find on Disjoint-Set Data Structures

Sunday, 9 March 2014

Kindle Book Summary Creator

I am a proud owner of a Kindle device and I love reading books.

While I am reading a book I always highlight the sentences that I consider more interesting. When I finished a book, I found very useful to copy all the highlights in a notepad to create a summary of the book (usually I save them in workflowy). In same cases, for really interesting books, I often turn the summary to a blog post.

I created a very simple application that helps me to automatically extract highlights from all my kindle books. It is open source and you can find it in this GitHub repository: KindleBookSummaryCreator.

It is straightforward to use:

1. Connect the Kindle to your PC

2. Run the application

The clipping file should be automatically detected. If not, click the Detect button.
Specify the output folder.



3. Click START

The output folder will open automatically. For each book, there will be a text file with all your highlights.


I hope you can find this little application useful as it is for me.




Saturday, 8 March 2014

Book: Working Effectively with Legacy Code

Every professional developer have to deal with legacy code in the course of his career.

The book Working Effectively with Legacy Code written by Michael Feather is considered a must read and I really recommend it. This is a summary of the book.
Michael Feather definition of Legacy Code:
Legacy code is simply code without tests.
The goal of every competent software developer is to create designs that tolerate change! This is why it is critical to learn how to confidently make changes in any code base.

The main problem is to make changes while preserving existing behaviour.
Preserving existing behaviour is one of the largest challenges in software development.
The three main questions to ask are:
  1. What changes do we have to make?
  2. How will we know that we've done them correctly?
  3. How will we know that we haven't broken anything?
The main approach is to use tests as a way to detect changes.

But, when there are no tests, we end up in the:
Legacy Code Dilemma
When we change code, we should have tests in place. To put tests in place, we often have to change code.
Sometimes, it is possible to make changes without getting existing classes under tests:
  • Sprout Method: develop a new method and call it from the existing code.
  • Sprout Class: develop a new class and use it from the existing code.
  • Wrap Method: develop a new method that wrap an existing method.
  • Wrap Class: create a new class that wrap an existing class (the Decorator Pattern).
A technique like TDD is perfect in this context and only the new method or class will be tested.

However, when you need to touch existing code, it is necessary to do very conservative refactoring to get tests in place first.

The goal is to change as little code as possible to get tests in place.

The steps to follow are:
  1. Identify change points
  2. Break dependencies
  3. Write tests
  4. Make changes
  5. Refactor
Identify Change Points

Reading through code and playing with the system helps you to identify the change points. It often pays to draw pictures and make notes to improve your understanding.

Scratch Refactoring is a useful technique for learning. Grab the code and start applying refactoring without tests and at the end throw away all your changes. As a result, your knowledge about the code base will be increased.

Object-Oriented Reengineering Patterns is a recommended book for learning how to read and understand large code bases and build a big picture of a project. Once you identified the areas of the code that you need to change, it is important to answer the following question:

If I make some changes here, where I can see the effects?

Answering this questions is very important because it helps to identify which code you should be cover with tests in order to create a good safety net that gives you the confidence you need for subsequent changes.
It is important to know what can be affected by the changes we are making!
Effect Sketching is a useful technique that can be used to answer this question. The idea is to create a little graph that shows the effect of your changes. Navigation tools like ReSharper can help you identify all usages of a particular piece of code. However, if your class has a superclass or subclasses pay attention because there might be other clients that you haven't considered.



A Pinch Point is a narrowing in an effect sketch, a place where it is possible to write tests to cover a wide set of changes. If you can find a pinch point in a design, it can make your work a lot easier. It is a place where tests against a couple of methods can detect changes in many methods. Writing tests at pinch points is an ideal way to start some invasive work in part of a program.

The tests that we are going to write are called Characterization Tests. What the system does is more important than what it is supposed to do. You are not fixing bugs at this stage! The goal is to capture what the system does to increase your confidence of making changes.

How to break dependencies?

Adding tests is not always easy. Often, it is necessary to break dependencies.

The book contains a catalogue of dependency breaking techniques:
  • Extract Interface
  • Adapt Parameter: wrap a parameter behind an interface
  • Parametrized Constructor: create a new constructor that takes the dependency and update the old constructor to use it
  • Break Out Method Object: move a long method to a new class
  • Extract and Override Call: extract a call to a new method and override it in a testing subclass (ideal to break dependencies on global variables and static methods)
  • Extract and Override Factory Method: extract hard-coded initialization work from a constructor to a factory method and override it in a testing subclass.
  • Parametrized Method: if a method creates an object internally, pass the object from the outside
  • Pull Up Feature: you can pull up a cluster of methods into an abstract superclass and you can subclass it to create instances in your tests.
  • Push Down Dependency: make a class abstract and create a subclass that will be the new production class and push down all problematic dependencies into that class.
  • ...
For languages like C and C++ it is possible to use some specific techniques like:
  • Preprocessing seams: use ad-hoc macros to replace behaviour in tests
  • Link seams: override behaviour linking to a different implementation in a test module
  • Replace Function with Function Pointers: use pointers in tests to swap real implementation with fakes
  • Template Redefinition (C++ only): make a class a template and instantiate the template with a different type in the test file.
In using these techniques it is very important to try to preserve signatures whenever possible! It is always better to do this work using pair programming.
Working in legacy code is surgery, and doctors never operate alone.
Consider reading the book Pair Programming Illuminated. Refactoring

One of the most important principle to keep in mind is the Single Responsibility Principle. It is important to find responsibilities and extract classes when required. You can start applying it at the implementation level. It makes it easier to introduce it at interface level later.

Try to describe the responsibility of the class in a single sentence.
The best way to get better at finding responsibilities is to read more books about design patterns and in particular to read more code.
You can identify responsibilities using the following techniques:
  • Method Grouping
  • Hidden Methods: many private or protected methods indicates that there is another class
  • Coupling between variables and methods
  • Sketch (dependency graph between methods)
When you do refactoring, remember to do just one thing at a time.
Programming is the art of doing one thing at a time!
Ask your partner to challenge you constantly asking: What are you doing?
Remove duplication as much as possible! 
You end up with very small focused methods. The goal is to have orthogonality in the system. Your system is orthogonal when there is only one place you have to go to make a change. Removing duplication often reveals design.
Remember, code is your house, and you have to live in it.
Rename Class is the most powerful refactoring. It changes the way people see code and lets them notice possibilities that they might not have considered before.

Consider the Command/Query Separation Design Principle
A method should be a command or a query, but not both. A command is a method that can modify the state of the object but that doesn't return a value. A query is a method that returns a value but that does not modify the object.
Extract Method is a core technique for working with legacy code. You can use it to extract duplication, separate responsibilities, and break down long methods. It is also recommended to extract methods in a bottom up approach. Extract small pieces first!

Conclusion

It is true that working with legacy code can be frustrating at times. However, it is only a matter of perspective and approach. Working with legacy code can be fun and doing it using pair programming is a way to get a better result.

Surely, working with legacy code is a challenge and offers the opportunity to significantly improve your software developer skills. In any case, I totally agree with what Michael Feather say at the end of the book.

There isn't much that can replace working in a good environment with people you respect who know how to have fun at work

Sunday, 2 February 2014

Design Patterns Series - Learn Design Patterns quickly

What is a design pattern?


From Wikipedia:
In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design.
I think that learning design patterns and the underline Object Oriented Design principles is really important. However, it is really difficult and time consuming. It requires a fair amount of discipline.

This is why I created this series of posts.

This post is a simple index that aggregates all the post I have written in the last two years. Most of the frequently used design patterns are covered but there are many others to cover.

I will update this post as soon as I create a post on a new Design Pattern.

My goals for this series of posts

  • Read a lot of resources and consolidate the information in a single post
  • Present the pattern in a easy way
  • Write a good example to illustrate the benefits of using the pattern
  • Put the pattern in the context of .NET
  • Find real examples of the pattern in the .NET Framework

My main sources of information


 Design Patterns Posts


Hope you find this series of posts useful.

Thursday, 5 December 2013

The Light Game for Windows Phone - The User Voice

1 of 8The Light Game is a simple but incredibly unique and fun game that I built for Windows Phone.

Since the first release, the game has been downloaded by more than 200,000 people, it has been the top free game in Windows Phone in some countries for a while and it has received hundreds of very positive reviews with an average of almost 5 stars.

In this post I would like to share with you some of the most interesting and positive reviews I received in the last 12 months.

All of these comments made me really proud and they surely stimulate me to continue in improving the game over time.

Thank you very much!




Friday, 22 November 2013

Are you serious about achieving mastery? Find your mentor!

Few months ago, I read a book that significantly helped me in reflecting about my career and aspirations as a Software Engineer. It helped me in taking a very important decision that, I am sure, will have a great impact in my future.

The book is called Apprenticeship Patterns: Guidance for the Aspiring Software Craftsman and in this post, I am going to tell you my decision and the reasons behind it.

The book offer advices and solutions to dilemmas that software engineers typically have. The goal is helping them in increasing their expertise and becoming masters in what they do.

The book celebrates the importance of Software Craftsmanship as one of the best way to really learn the skills and the practical abilities required to design and develop high-quality tested software.
"Having knowledge is not the same as having the skill and practical ability to apply that knowledge to create software applications. This is where craftsmanship comes in."
There is one advice in particular that emerge constantly:
"If you are serious about achieving mastery, be tenacious about finding mentors to guide you."
These words made me deeply reflect.

I am an avid self-learner and definitely serious about achieving mastery. I read a lot of books written by experts in their fields that in an indirect way are like mentors for me. At the same time, at work, I am surrounded by very smart and talented people that are always willing to help and share their knowledge with me. I attend events and I am a founder of a community that helps me to network with passionate and energetic individuals.

This is awesome and it is great but I realized that I needed something more.

I really needed to find a mentor outside work, a person who I respect, with many years of experience and a strong reputation in the field, a professional that can follow me in my learning process and coach me in the right directions to become a great software engineer.
"The goal is to find ways to expose yourself to the daily working habits of other skilled people, and observe the ways in which they gradually refine those habits into even greater skill"
The main question was: Who to choose?

The answer to me was almost immediate: Matteo Baglini.


Matteo Baglini is a very senior software developer and architect with a lot of experience in building software in various different domains from business, web, mobile applications to embedded softwares. He is freelancer, a consultant, a technical writer, a speaker and founder of DotNetToscana and Coders TUG.

I have to say that Matteo is the most disciplined, the most pragmatic and the best programmer I ever met. I met him during my last year at the university and he already had a lot of impact on me at the time when we founded DotNetToscana and he surely represent what I want to become in the future. In addition, he is also a very good friend of mine.

So, in August, I sent a mail to him explaining my reflections and my intention to have him as my official technical mentor. 

Luckily, he was in a stage in his career when he wanted to invest more time in technical coaching activities so he accepted with enthusiasm and pride.

We started officially in October after my wedding and since then we had a meeting every week.

I have to say that the experience so far is incredible and I have all the intentions to share on my blog the results of this experience and the big lessons I am learning.

The ultimate goal is to being able to build cathedrals and Matteo can help me in achieving this :)
"Digging deep into a technology is that you can actually explain what’s going on beneath the surface of the systems you work on. This understanding will distinguish you from other who can’t describe the software they've helped build in a meaningful way because all they understand is one little portion. Once you’re part of a team, it’s the application of this pattern that separates out those who are making random piles of rubble (the Pragmatic Programmers called this “programming by coincidence” while Steve McConnell calls it “cargo cult software engineering”) from those who are building cathedrals."
If you are interested in the technical coaching services offered by Matteo, get in contact with him using his web site: Make It Simple.

This experience will be profound and useful for me and I am really excited about it.

Tuesday, 5 November 2013

Top Coder Problem - WolfDelaymaster

During my last SRM 593 on TopCoder I found the medium problem quite interesting and I was happy that I have been able to solve it relatively quickly using the technique of Dynamic Programming.

Solving this problem taught me two important lessons:

  1. The power of Dynamic Programming
  2. The trap of over-optimization

The interesting thing is that I didn't realize the second lesson until I wrote this post so I am really glad I decided to write it.

I am going to quickly describe my solution.

The problem statement: WolfDelaymaster (Why register on TopCoder?)
My solution: WolfDelaymaster implementation.

The definition of the problem suggest an immediate recursive implementation.

You can first check that the string satisfy the first condition. You start checking against "wolf", then "wwoollff" and so on. Considering that the maximum input string is 50 characters the biggest string to test against contains 12 times each individual character.
  1. For each positive integer n, the string which consists of n copies of 'w', then n copies of 'o', then n copies of 'l', and finally n copies of 'f' is a valid word.
If this test fail, we can use the second rule and split the original string in two parts and recursively check them. It is important to try all the possible split points that are multiple of 4 (there are no valid strings shorter than 4 characters).
  1. The concatenation of two valid words is a valid word.
This is the initial implementation:


Does this implementation works?

Yes, it works!

Are you concerned about the performance implication of having two recursive branches?

I was and for some reasons I decided to apply the technique of dynamic programming in order to speed up the program. You can learn more about dynamic programming on Wikipedia. It basically consist of caching the intermediate result of computation to quickly cut the recursion tree.

Here the implementation (addition highlighted).


Does this effort was required?

Absolutely not!!! The original implementation was good enough.

What is the worst case?

The worst case is a string that is invalid with a length of 50 characters like "fofflwllwooowowwwllllwlwllwwlwwfwwfwofwwfolowlolwo".

The execution time of the original algorithm on the worst case is: 0.0110 seconds.
The execution time of the optimized algorithm on the worst case is: 0.00056 seconds

Dynamic programming is powerful as it improved the speed of the algorithm of a factor of 19 but in this case it was not necessary. This is the biggest mistake I made. I wasted a lot of time that I could have spent on the next problem.

It is worth to mention that the problem could have being solved in an iterative way but for some reasons the I didn't get it during the competition and the recursive implementation was more natural for me.

This is a possible implementation adapted from the winner of the competition (I didn't test it using the TopCoder system tests).


The time of the iterative version on the worst case is: 7.1E-06

This version is absolutely the quickest version!