Mendocino Flowers

During a recent camping trip, we visited Mendocino. It was a very cloudy / foggy day, so I could not take any good pictures of the coastline. So the attention turned to the flowers in the front-yards of all the shops in the downtown. They have a very nice variety of flowers there.

Grouping Permutation Strings

This is a straightforward problem.

Given N strings of equal length (K) on an alphabet, you have to partition them into sets, such that every set contains strings that are permutations of each other. Of course, a string can be added to only one set and if 2 strings get added to 2 different sets, they should not be permutations of each other.

This can be easily done in O(N*K) time by using a hashmap. Each string will be inspected once, and each character of the string will be inspected only once.

We will use a hashmap, that maps the permutation key to a set of strings. We iterate over the N strings to find the permutation key of each string. In each iteration, you need an array to keep counts of characters that appear in the string. This array size will be the same as the size of the alphabet. So it will be able to keep counts of all the characters in the alphabet, that may or may not appear in a string. Then iterate over the characters in the string. Whenever you see a character, increment the corresponding count in the array. After the string is inspected, the array of counts can be used as a key in the map. If 2 strings have the same counts for all the characters, then they are permutations of each other.

Here is the Java code.

// assume all lowercase strings
int A = 26 ; // size of alphabet is 26
int N = ... ; // number of strings
String [] allStrings = new String[N] ;

// code to populate the array with equal size strings
// ...
int K = allStrings[0].length ;
// all strings are of the same length

// we are using a map with a String as key
// and a list of String as a value
// By using a List (instead of Set)
// we preserve the original order of strings
// This may or may not be important depending on the problem
Map permutations_map = new HashMap() ;

// Now iterate over the array and find permutation key for each string
for (String s : allStrings) {
    // counting array length is same as alphabet length
    int [] char_counts = new int[A] ;
    for (int i = 0 ; i < K ; i++) {
 char c = s.charAt(i) ;
 int index = ((int) c) - ((int) 'a') ; // char math !
 char_counts[index] ++ ; // increment the count
    } // 

    // now the string representation of this array can be used as a key
    String bucket_id = Arrays.toString(char_counts) ;

    // add the string to the list in map
    // create a new list if needed
    if (! permutations_map.contains(bucket_id) ) {
     permutations_map.put (bucket_id, new ArrayList()) ;
    } // 

    List str_list = permutations_map.get (bucket_id) ;
    str_list.add (s) ;

} // 

The caveat : This is dependent on character math. It's no big deal, but if it is a problem for the alphabet, just use another map, tp map the characters into unique numbers that can be used for the array index. Simple.

NOTE : For small strings on very large alphabets, an alternative scheme will be better. But the idea given here is reasonable to find permutations within numbers, or ascii strings.

I used this to solve another problem. First I had to generate a list of primes, for which I used the "Sieve of Eratosthenes". Then, I treated each prime as a string of digits, and use the above algorithm to bucket them. That was only part of the solution. I will cover the remaining parts in later posts.

Here is the Java code for grouping the primes. Note that all the numbers are assumed to have the same number of digits. In particular, they were all 4 digit primes.

public static final long MaxNumber = 9999 ;
public static final int NumberOfDigits =
    (int) (Math.ceil(Math.log10(MaxNumber))) ;
public static final long Floor =
    (long) (Math.pow(10,NumberOfDigits-1)) ; // 1000
public static final long Ceiling =
    (long) (Math.pow(10,NumberOfDigits)) ; // 10000

public static String getBucketId (long num) {
    int digits_count [] = new int[10] ;
    int pow10 = Floor ; // start dividing by 1000
    while (pow10 != 1) {
 long digit = num / pow10 ; // left most digit
 digits_count[digit] ++ ; // increment the count
 num -= digit*pow10 ; // remove the left most digit
     pow10 /= 10 ; // for next iteration
    } // 
    digits_count[num] ++ ; // last digit remains
    return Arrays.toString(digits_count) ;
} // 

public static void insertIntoBucket
                  (String bucket_id, long num) {
    if ( ! BucketedPrimes.containsKey (bucket_id) ) {
     BucketedPrimes.put (hash_value, new ArrayList()) ;
    } // 
    List permutation_list =
                      BucketedPrimes.get (bucket_id) ;
    permutation_list.add (num) ;
} // 

public static void createBuckets
                    (int num_digits, List all_primes) {
    for (Long p : all_primes) {
 long prime = p.longValue() ;
 String hash_val = getBucketId (prime) ;
 insertIntoBucket (hash_val, prime) ;
    } // 
}

This creates the BucketedPrimaes map given a list of numbers, in this case the numbers happen to be primes. Every value in the map is a list of 1 or more numbers, that are digit permutations of each other.

What a week that was

The last week was very interesting for Sports and Science. Somewhat historic as well. Here is a quick recap of all the things that happened in this short time.

1. Spain's historic win at Euro 2012.
It's hard enough to win a Soccer tournament at such massively competitive world stage. Doing 2 in a row is way harder. Doing 3 in row, definitely deserves being labeled as historic. I wrote about it in my previous post.

2. Federer's win at Wimbeldon.
I don't think I have to say a lot about this, as this is obvious. Astonishing 17th grand slam title, regaining number 1 at the age of 30, what more a man can do ?

3. Anderson Silva's Win at UFC 148
Although UFC is gaining popularity, it still hasn't gone mainstream. More and more will be shown on Fox, so it just has begun its upward swing. Many think of it as too violent. I find it less violent than boxing, as often times the fights are decided by grappling skills. In any case, I enjoy watching UFC, and find Anderson Silva's 10th title defense legendary. In a field that requires insane physical fitness and a lion's heart, no one has been at the top for so long. And Silva does it convincingly. Jon Jones might surpass Silva's records, but till today, Silva has been the best pound for pound fighter in the world.

Now on to Science - where the discoveries are truly historic in nature.

4. Higgs Boson
The confirmation of this so called "God Particle" was one of the main objectives of Large Hadron Collider (LHC) at CERN. To be honest, I don't understand the theory at all. To my layman brain, Higgs Boson has always felt like the "aether" that was supposed to permeate the space. But of course, I believe the modern scientists when they tell us, that Higgs Boson is based on sound mathematics, unlike the discredited "aether". This week the CERN announced that they have indeed found evidence of Higgs Boson in LHC. This is the most important discovery in particle physics, and it confirms The Standard Model. I wish there were more accessible books that explain the Higgs Boson, and particle physics in general.

5. Dark Matter Detected
With all the celebration about the Higgs Boson in the media, one other equally important discovery did not get as much mention. For the first time the dark matter was "observed directly". Dark Matter by definition does not interact with other matter. That's why it has been hard to detect it in spite of it being 5 times as plentiful. The only way to detect it as via its gravitational effects on neighboring matter. On the same day CERN announced about Higgs Boson, Nature announced about the first detection of dark matter "filament" joining 2 clusters of galaxies. Dark Matter is even more mysterious than Higss Boson, but it's at the cosmological scale, not quantum scale. I do not know if this discovery proves the hypothesis of Dark Matter. It does seem extraordinary, confirming that although we know precious little about the universe, we are perhaps on the right track.

The Greatest Soccer Team Ever

It's very rare to watch history in the making, and much rarer to realize that in real time. I think the time has come to declare just that.

About 6 years ago, the Spanish National Football team made a crucial decision. Having realized their inability to out-muscle their opponents, they decided to adopt a playing style that has now come to be known as "Tiki-Taka". This style was not their invention - some credit goes to the Barcelona team during the early 90s under the super-successful manager and a legendary player himself - Johan Cruyff. It has been evolving since then. The Barcelona team under Josep Guardiola (a pupil of Johan Cryuff) and the Spaniards just took it to the level of absolute perfection. There is a significant overlap between the rosters of Barcelona and the Spain National Football team, and the playing styles are nearly identical.

The Dutch made "Total Football" famous and highly effective in the seventies. In this style, the players can switch positions and reliance on specialists is reduced. Barcelona's "Tiki-Taka" takes this basic idea even further and adds more elements to it. In this system, the players can be physically small, as long as they are technically talented and exceptionally fit. They make quick passes to each other, with just one or two touches before passing. It requires exceptional team coordination, vision and space awareness. A typical pattern in this system is triangulation, where 3 players keep advancing field position while passing ball to one another. Others join in as needed to make new triangles.

But the style is just a technicality if it isn't successful. Barcelona has won 15 titles under Guardiola, and Spain just became the first country to ever win 3 consecutive titles - Euro 2008, World Cup 2010 and now Euro 2012. And of course, success of the style depends on the caliber of the players as well.

The relationship is mutual. This style has created a generation of great Spanish players and the continued success of the style depends on their greatness. Xavi, Iniesta, Villa, Fabregas, Silva, Torres, Pedro - the list is endless. In Euro 2012, they were without Puyol and David Villa - and they still won. This combination of individual talent and a great style, has been a perfect match. Hence, I have no hesitation in claiming that we are indeed watching THE greatest national soccer team ever.

Such claims are often met with skepticism. What about Brazil with Pele, or the Dutch team of 70s ? Comparing players across generations is hard, comparing teams is even harder. What is great about Spanish team today, is that it is not dependent on some key players - rather it depends on having many players that play the system exceptionally well. Surely, Xavi has been the architects on many attacks - but the success doesn't just depend on him. Messi makes Barcelona the ultimate club team ever, but he is not part of the Spanish team. That's the point. Spain doesn't need a Pele or a Maradona or a Platini or a Zidane. There is no one player without whom the whole edifice will collapse.

A key idea of the system is to keep possession at all times. In many games, Spain has possession for 70% of the time, and routinely complete 500+ passes every game (with 80%) accuracy. If your opponents do not get the ball, how will they score ?

This style of play also generates criticism. Spain's goal margin in wins is often 1-0. People find the game slow, some go as far as calling it boring. I can see why they might feel it that way. But I find their play mesmerizing. It's like watching an intricately choreographed ballet. Elegance and precision are two words often used to describe their play.

What's remarkable is this style is not a secret. Other teams have been studying them, trying to copy some of their ideas, but more importantly figuring out ways to defeat them. Neither Spain, nor Barcelona is invincible. Chelsea has had success against Barcelona. But overall, both Spain and Barcelona have maintained their position at the peak for a long time. This playing style, and the physique of current players makes the long crosses and headers a bit rare. Very few players are over 6 feet. I don't mind that.

You cannot defeat them because you cannot take away the ball from them, and if you get the ball, you cannot score a goal against them. That's true. Often during the Tiki Taka talk, what gets little mention is Spain's defense. In the entire Euro 2012, Spain played more games than everyone else except Italy, but there was just one goal scored against them. Just ONE. This was when their main defender Puyol could not play the tournament due to an injury. Think about it. Victor Valdez is considered to be the best goalkeeper Barcelona has ever had. And he is a reserve for Spanish team, because current goalkeeper and captain Iker Casillas is on track to be called one of the greatest goalkeepers ever. Spain's coach has the reverse problem - who to keep on the bench ! The talent pool is very deep.

No matter what you think of this being the greatest team ever, it's beyond doubt that Spain and Barcelona have redefined Soccer. And this happened in last 5 years. Many great teams have come and gone, many more will surely come in future. But very rarely a team is credited for starting a new School of Soccer playing. I consider myself to be absolutely lucky to have watched Spain - and in particular Barcelona play. It has been a pure joy. Thank you Spain, thank you Barcelona !

Here is a very nice video explaining this style of play - not goal scoring, just passing.