Join me on my new blog

Hi everyone,

It's great that you found me!

This is my old blog. Please, have a look at my new blog.
www.andreaangella.com

Also feel free to connect with me on my social network.

See you all soon,

Thanks,
Andrea

Blog: www.ndreaangella.com

Videos:  www.youtube.com/user/angellaandrea

Twitter: @angella_andrea

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

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

Webcast (in Italian)

Slides

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

Configuring the TopCoder Arena for C# developers

If you read my previous post (Learning Algorithms with TopCoder - Getting Started Guide) you are probably motivated in solving TopCoder problems and putting yourself under test. You probably created an account and tried the arena and you quickly realized that the experience is not that great.

Why?

• You have to read the text of the problem inside the arena
• You have to manually create the class and copy the method signature
• Testing the code with the examples is a manual process in the arena
• Debugging against the examples force you to code all the examples manually
• You have to copy the code from Visual Studio into the Coding Area

This is tremendously annoying!

Fortunately, there is a solution to these problems using some arena plugins. It is a little bit annoying to setup but once done your coding experience is vastly improved and you can finally focus on writing algorithms.

You can find some only-text documentation at the following link:
http://www.topcoder.com/contest/classes/ExampleBuilder/ExampleBuilder.html

First of all, download the TopCoder.zip file and extract it into C:\TopCoder

The folder contains an empty Visual Studio .NET 4.5 C# console application and a folder jars with the plugin code.

In this post, I want to explain step by step how to configure the TopCoder arena to be able to start solving SRM problems in TopCoder using C# and Visual Studio.

Launch the arena and open the Editor options.

Add a new editor with the following information:

• Name: ExampleBuilder
• EntryPoint: codeprocessor.EntryPoint
• ClassPath: C:\TopCoder\jars\CodeProcessor.jar;C:\TopCoder\jars\FileEdit.jar; C:\TopCoder\jars\ExampleBuilder.jar

Select the new editor and click Configure.

Insert the entry point fileedit.EntryPoint and the processor class tc_plugin.ExampleBuilder

Then, click Verify.

Press OK and then Click Configure.

Specify the enter directory to C:\TopCoder, check "Write the problem description using HTML" and check "Write the Problem Description to separate file" with extension html.

Click the Code Template tab, select the C# language.

Copy the template code from here but feel free to customize it as you like.

Save everything.

Now you have everything set up and you are ready to code.

Open one of the past SRM: Practise Rooms > SRMs.

Select one of the problem.

The default editor will launch by default. Make sure that you select C# as your language.

Change your editor to ExampleBuilder.

This will trigger the creation of two files:

• A C# source file with the problem and the tests
• An html file with the description of the problem

You can open the html file and read the problem statement in your favourite browser (maybe in a separate screen if you have a multi-monitor setup).

At this point, you can open the TopCoder Visual Studio solution and include the file in the project.

You can see that all the examples has been automatically added as tests and the only thing that you need to do is to provide the implementation of the algorithm in the method.

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BinaryCode 
{
    public string[] decode(string message) 
    {
        // IMPLEMENTATION GOES HERE  
        string[] res = new string[0];
        return res;
    }
    
    // BEGIN CUT HERE

    public static void Main(String[] args) 
    {
        try  
        {
            eq(0,(new BinaryCode()).decode("123210122"),new string[] { "011100011",  "NONE" });
            eq(1,(new BinaryCode()).decode("11"),new string[] { "01",  "10" });
            eq(2,(new BinaryCode()).decode("22111"),new string[] { "NONE",  "11001" });
            eq(3,(new BinaryCode()).decode("123210120"),new string[] { "NONE",  "NONE" });
            eq(4,(new BinaryCode()).decode("3"),new string[] { "NONE",  "NONE" });
            eq(5,(new BinaryCode()).decode("12221112222221112221111111112221111"),
                  new string[] { "01101001101101001101001001001101001",                  
                                 "10110010110110010110010010010110010" });
        } 
        catch(Exception exx)  
        {
            Console.WriteLine(exx);
            Console.WriteLine(exx.StackTrace);
        }
        Console.ReadKey();
    }
    ...

    // END CUT HERE
}

You can see the results of the tests simply running the project with F5.

How do you actually submit your code?

Click Compile and the source code will be automatically copied into the arena.

Finally click Submit.

To summarize, once you setup your development machine like I explained in this post you will be able to open any TopCoder problem, start coding your algorithm immediately and have a lot of fun. During a competition, this technique can also save you a lot of time and increase the chance of getting an higher score.

Enjoy coding!

Andrea

Learning Algorithms with TopCoder - Getting Started Guide

I have lots of friends who are passionate developers and every so often we discuss about

algorithms design and how important this is. The TopCoder platform offers a very good opportunity to put yourself under test, improve your skills and compete among other coders around the world. Everyone is pretty excited when I explain them about the platform and they seems willing to try it out but for some reasons this does not happen.

Let me be clear now.

Do you know what is the reason?

The answer is that...

They are frightened!

Saying that you don't have time is not an excuse because a competition is just 90 minutes long and everyone can give it a try. They are coders so why should they be scared of coding?

Why?

The reason is because they "don't feel ready to compete". They fell they need to do additional learning before actually competing otherwise they hurt their reputation and self-esteem. This is perfectly reasonable and I completely understand these feelings because this is how I constantly feel. TopCoder problems are usually very difficult and this fear of failing is completely blocking them.

So what?

What they don't consider is that TopCoder is not only a competing platform but also a learning platform. Once registered you have access to all the exercises from previous competitions with solutions completely explained, you can try them on your own without competing, you have access to lots of tutorials. There are tons of materials. You will be never ready so after trying few exercises I recommend to try a SRM (Single Round Match) competition. Competing really change the game and makes you more aware of your true skills. You are then able to identify areas of improvement, practise and then compete again. At the end of the day, you are always and constantly learning!

TopCoder is a learning platform!

Competitions can be seen as just a way of learning but you are not forced to compete.

However, if you are ambitious and you are truly committed to becoming a great coder, like I am sure you are, competing is the best way to put yourself under test and really find your potentials and limitations.

If you are scared you probably are not really serious of becoming a great coder.

It does not matter how strong you become compared to others. What matters is constantly learning and improving yourself.

This idea is also clearly expressed by the founder of TopCoder, Jack Hughes:

"TopCoder intends to help developers increase their skill level as well as increase their value to employers"

Then what?

If you read so far, it means that I convinced you to try TopCoder and in this post I would quickly introduce you to the platform.

First of all, you need to register.

Open the following website and click on Register Now in the top right corner: http://community.topcoder.com/tc

TopCoder allows you to learn and compete in many different areas. If you want to practise your algorithmic skills just select "I want to compete on TopCoder" and then follow the procedure where you will be asked to provide all your personal details.

Once registered, you can login into the website.

Expand the Competitions menu item and enter into the Algorithm category and then into the Single Round Matches section. It is probably a good idea to read the Overview page and then the Algorithm Competition Guide.

You can access to all the past problems clicking the Match Archive link under Statistics. In addition, you can also read the code submitted by all the people who participated to the competition. This is a lot of stuff!

There are also an interesting set of tutorials about algorithms that you can find in the Tutorials page.

However, there is nothing better than actually trying a problem yourself.

If you want an experience that is similar to a rate event, you can launch the Arena clicking the O(n) image in the top-left corner or the Launch Arena link.

The Arena is written in Java and you need to have it installed.

In the arena you enter a practice room and you can submit your code to a problem and get a score of how well you did it. The biggest value of the practise room for a learning point of view is the ability to run the system tests and discover bugs in your algorithm. You can also challenge the code written by other coders to find bugs in their implementations.

More information here: Practising in the TopCoder arena.

You can code using one of the following languages: C++, Java, C#, VB or Python.

The platform has been recently updated to the latest version of the languages.

If you decide to compete, you will get a score and you will be ranked against all the other top coders. You can find statistics about your performance clicking on your login name in the top-right corner.

For example, the followings are my current statistics. As you can see, I am still quite weak. 

I hope with this post that I have stimulated your curiosity.

Happy coding and see you in the arena!

See how to configure the TopCoder Arena for C# developers.

Andrea

Top Coder Problem - Boxing

TopCoder is an amazing platform to challenge yourself.

I decided to start posting my solutions to problems with the following purposes:

• Stimulate myself to practice more
• Stimulate my friends to solve the problem
• Stimulate my friends to join TopCoder and challenge themselves
• Compare and contrast different solutions

Notes:

• TopCoder only accepts solution written in C# 2.0
• The problem statement is the exclusive and proprietary property of TopCoder. You need to login to see it.

TopCoder Problem:
Boxing

This problem was used for:
2004 TCO Online Round 3 - Division I, Level One


My solution:

Tests:

My solution is an usage example of the Greedy Algorithm Design Paradigm.

What is your solution?

BigInteger multiplication - A recursive approach

Recently in the Coursera course "Algorithms: Design and Analysis, Part I" I come across to an interesting introduction of the divide and conquer technique using the multiplication between big integers as an example. My hands started to itch immediately. I would have to try to write an implementation!

The Problem

Given two integers x and y of any size return the product of them.

The Idea

The simplest algorithm is what we are all used to do, writing down all the products and then add them together. This is know as the "Long Multiplication" algorithm.

Using a simple calculus is easy to understand that the problem can be solved using a recursive approach. 

It is always possible to write x and y in the following way:

So the product can be calculated as:

This means that we can calculate the product xy calculating 4 small products (ac, ad, bc, bd) in a recursive way.

More info:

http://en.wikipedia.org/wiki/Multiplication_algorithm

The Implementation

For simplicity, I decided to represent a number using a string encapsulated in a class called MyBigInteger.

This is the implementation of the multiplication algorithm in C#:

In order to implement the algorithm I also had to implement the sum between two big numbers using the classic mathematical way:

The full code is available in my personal repository (BigIntegerMultiplication).

Tests

Improvements

In this example, we have a recursive tree with 4 branches. In reality it is possible to have only 3 branches using a simple trick (Karatsuba multiplication).

Instead of calculating ac and bd directly it is possible to calculate first:

and then calculate (ad + bc) using a subtraction:

In order to implement this slightly improved version of the algorithm is necessary to implement the subtraction of two big integers. I didn't wanted to do it, so I don't have an implementation to share.

Conclusion

The purpose of the exercise was to prove to myself that I was able to build the algorithm based on the original idea presented in the course. I would like to let the reader aware that the .NET framework already implement a comprehensive class that implement the operations on big integers in a quick way: BigInteger.

2012 TopCoder Open - Qualifications

Yesterday, I participated to the Online Qualification Round 1C that is the first phase of the Worldwide 2012 TopCoder Open Turnament in the algorithm category.

If you look at the algorithm competition schedule you will see that 600 out of 2000 (the maximum number of participants per qualifications round) advances to the semifinals. My final position is 306 so I believe I advanced to semifinals but I didn't received yet an official communication from TopCoder.

The match has been intense but it has started in a very bad way. First, I opened the easy problem and I spent 15 minutes to find a solution. I couldn't come up with a solution. I was shocked because this is usually simple and I always had a first quick solution to it. I decided to move to the medium problem and the same happened. In that case, the text of the problem was too long and I hate this kind of problems so I decided to move on the hard problem. At that point, my hope was almost null because I never been able to solve a TopCoder hard problem. I focused all my remaining time to solve the hard problem and I submitted a solution and I got 448.50 points. I was happy because I knew that I discovered some subtle edge cases and I addressed them but I wasn't 100% sure that my code was fully functional (never I am).

Then the challenge phase. Only three people (included me) in the room (usually 20 people) did the hard problem. Three tentative to break my code has been done with a negative result (each person lost 25 points for this). I challenged the code of a guy that submitted a solution to the hard problem but without covering an edge case and I got 50 points. So my score became 494.80.

Then the system test. The system test is terrible because if only a single test case against a solution does not pass you automatically get a score of 0. Fortunately my code passed the system test.

I would like to share the problem and my code with you but unfortunately for copyright issues I can't. You have to register on TopCoder to have access to all the problems.

However, I can share with you my public profile information.

My total topcoder score in the algorithm category (a kind of average of all the competition you did)  is now 1167. As you can see, my last match has been significantly better than the previous. Solving the hard problem is a great achievement for me.

The most interesting chart is my global position relative to the others TopCoders (3520 out of 9334).  It is good to see that I am better positioned than the average TopCoder. My percentile is 62.2884%. As you can see I am very closed to the blue area (a score greater than 1200) and this is my next goal, an hard goal.

Competing on TopCoder is amazing and I like the adrenaline released during the competition. I strongly recommend the experience to any programmers. It doesn't matter what will be your score, what it matters is challenging yourself, improving yourself and having fun.

Programming a Robotic Car

In the last few weeks I have been quite busy following the course "Programming a Robotic Car" on Udacitity. The course is quite demanding because it force you to implement all the algorithms presented. I think this is by far the most effective way to really learn and their on-line platform based on Python works pretty well.

These are some of the problems that can be solved with the techniques explained:

• Localizing a robot in a map
• Monte Carlo Localization
• Particle Filters Localization
• Tracking objects
• Kalman Filters
• Motion planning
• A Star
• Dynamic Programming
• Robot Motion
• Smoothing
• PID Control
• Simultaneous localization and mapping
• SLAM
• Online SLAM

You can access all the code in my public repository under the following path:

• Udacity >> CS 373 - Programming a robotic car

Here few snippets of the most relevant code. 

Kalman Filter:

Particle Filter:

A Start:

Smoothing:

PID Control:

Twiddle (used for tuning the PID control parameters):

Online SLAM:

Robot Localization using Montecarlo Localization

The problem of localising a robot in a known environment is quite interesting. I would like to share with you my solution to the homework assignment for the unit 1 of the "CS 373 Programming a Robotic Car".

The environment is a discrete map (colours matrix) where each area can be green or red. The robot can sense the colour (sense function) of the area where is currently on and can move in any directions (move function). To make things more interesting and close to reality the measurements and the motions are subjected to errors and this is represented by the variables sensor_right and p_move. Given a list of measurements and a list of motions the problem is to create a matrix of probability that describe where the robot is likely to be after all the specified moves.

More information about the definition of the problem can be found on Udacity.

I used the python module unittest for this purpose. This is one of the unit tests that I defined for the problem:



This is the main code that does the actual calculation:

The current algorithm used to solve this problem is called Montecarlo Localization.

You can find the full code in my personal repository.