At The End Of The Rainbow

I am one of the few people who loves rain. One reason is the rainbow, whose scientific explanation has not dulled it's beauty to me. This one was very near my home. These shots are from my window.

The Assassination of Jesse James by the Coward Robert Ford

Movie Review : The Assassination of Jesse James by the Coward Robert Ford
Director : Andrew Dominik
Genre : Western
Released : September 2007
Starring : Brad Pitt, Casey Affleck
My Rating : 4 out of 10

I decided to watch this movie based on the curious title, the cast and the true story on which it is based. Sadly, this turned out to be a long movie (with a long title) - a whole 160 minutes -  that feels way longer than even that. I thought I was watching it for like 5 hours.

First the good news. Great acting by Casey Affleck. Really superb. Very nice cinematography. Last 30 minutes are well scripted. That's about it.

Bad news is plenty. Brad Pitt is not a bad actor, but he is badly cast as Jesse James. Completely unbelievable portrayal. A large number of unnecessary scenes. And they are slower than snail. You will learn almost nothing about Jesse James. There is zero tension in scenes that should have been tense. It's hard to care either way about any character except Robert Ford (Casey Affleck).

And the movie takes itself way too seriously. It's absurdly pretentious.

There really isn't much of a synopsis to write about.

I don't mind watching long slow movies at all. But there has to be enough return on investing so much time. Not here.

Had this movie been cut down by half to 80 minutes, I might have a given a tentative recommendation based on the camera work and Casey Affleck's acting. As it stands, you are better off not watching this one.

Humpy Koneru

I know Cricket World Cup is happening, but this is an important news, that should not be overshadowed. India's highest rated woman GM, Humpy Koneru, has qualified as a challenger to play for the title of the Woman's World Chess Champion against the current World Champion - Chinese GM Hou Yifan !

Humpy has been a leading female player for a while. With some impressive results so far (like winning Girls Junior world championship title). She has been awarded Arjuna Award and Padma Shri by the Indian Government.

The current Woman's World Champion Hou Yifan is a phenomenally talented 17 year old. She won the title when she was 16 years old - and created the record of being the youngest person in the history to win a chess world championship.

Apart from the highest rated female player Judit Polgar (who does not participate in Woman only tournaments), these are the only 2 other girls rated over 2600. So they are the logical contenders for the championship. But the match would be tough for Humpy - in their games so far, Hou has won 7, and Humpy only 2.

If Humpy wins the match later this year, both male and female World Chess Champions would be Indians.

Partial Derangement

As part of a bigger problem, I wanted to solve what I decided to call "Partial Derangement". This may be part of standard course material on Combinatorics, but I couldn't quickly find anything similar. So I gave it a try on my own. I may be reinventing a wheel here, but it was a fun challenge.

The problem is similar in nature to "derangement". In the derangement problem, we want to find out all such arrangements, which do not have any object in its correct place. Here the restriction is placed on only a few items. Say you want to find out arrangements of letters [A B X Y] such that A cannot be in first place, and B cannot be in second place. There is no restriction on X and Y .

For example, [B X Y A] is a valid arrangement. But [X B A Y] is not. Because here B is in its natural second place.

Let's modify the problem we looked at, while discussing "derangement".

Say M men and W women went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, all the men deliberately put on a wrong name tag on their shirts. No man had the right name tag. The women, on the other hand can put the right name tag if they want. In how many ways can they do it ?

Note how this is quite different from simple derangement discussed before. Here a man can put a woman's name tag to satisfy the requirement of the game. For every man, there are (M-1) * W valid choices. Whereas in a simple derangement, every man would have had only M-1 choices. In other words, this is NOT a derangement only within a subset. Hence the answer cannot be D(M) * W! where D(M) is number of derangements of a set of M objects.

This problem is a bit harder than derangement. But very similar logic can be applied to solve it. First, let's define what we want to solve for.

Let's define, PD (N, K) as the number of arrangements of N items, out of which particular K predefined objects cannot be in their correct place. Note that there are specific K objects, already identified to be deranged.

Think of N numbered balls (from 1..K..N) to be put in N numbered bins (from 1..K..N) . The task is to arrange N balls so that no ball numbered (1..K) is in the bin with the same number.

We will solve it using the similar reasoning style for derangement.

Pick a ball, numbered between (1..K) This ball i can either

A : Be put in any unrestricted bin, which is numbered (K+1..N) In this case, any bin can be used, there is no restriction. There are N-K choices for such a bin.

OR

B : Be put in a restricted bin from (1..K) There are K-1 choices here, as ball i cannot be put in bin i .

Let's examine each case in more detail now.

A : When the ball i is put in an unrestricted bin, we lose one unrestricted bin, of course. But now the corresponding bin i for this ball becomes unrestricted, as any ball can be put there without violating the rule. Meaning the number of unrestricted bins remains same, and the number of restricted bins is now one less. So after this placement, we have N-1 balls, with K-1 restricted bins. This is same as PD(N-1, K-1) . And since there are N-K choices for choosing an unrestricted bin, the sub-total of these arrangements is (N-K) * PD(N-1, K-1) .

B : This is where I am copying the logic used in finding derangement. Here ball i was placed in a restricted bin, from (1..K) . Since it cannot be placed in its own bin, there are K-1 choices for this. Let's say it was placed in bin j . Now let's decide a place for the ball j corresponding to that bin. There are 2 choices - it is either placed in bin i or it isn't.

B1 : It is placed in bin i . This effectively removes the pair i and j from the set. We are left with N-2 balls, to be placed in N-2 bins, out of which K-2 are restricted bins. This is same as PD(N-2, K-2) .

B2 : If ball j is not be placed in bin i, let's represent that restriction by simply renaming bin i to bin j. This leaves us with exactly the same problem, with one less ball. That is, we have N-1 balls, with K-1 restricted bins. This is nothing but PD(N-1, K-1) .

Since B1 and B2 are mutually exclusive, for every choice of bin for ball i we have 

PD(N-2, K-2) + PD(N-1, K-1) 

arrangements. Since there are K-1 choices for bins, the subtotal here is 

(K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) ) .

Since, A and B are mutually exclusive, let's add them to get the final answer.

PD(N, K)
= (N-K) * PD(N-1, K-1)
+ (K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) )
Note the term PD(N-1, K-1)is common in both. So after simplifying, we get a nice elegant formula
PD(N, K) = (N-1) * PD(N-1, K-1) + (K-1) * PD(N-2, K-2)

To use this formula, we have to have certain definitions, to avoid negative values. This is similar to saying 0! = 1 by definition, to terminate the recursion of formula  N! = N * (N-1)!

PD(0, 0) = 1 (by definition)
PD(N, 0) = N! (No restricted bins, so all arrangements are valid)

We require one last definition, and it needs some explanation.

PD(N, 1) = (N-1) * (N-1)!

Here we want to know how many arrangements are there, in which one specific ball is not in its corresponding bin. The total arrangements are of course N!. How many invalid arrangements are there ? To find out put the ball in its corresponding bin and arrange the rest of the N-1 balls. This is nothing but (N-1)!. So we have

PD(N, 1)
= N! - (N-1)!
= N*(N-1)! - (N-1)!
= (N-1) * (N-1)!

Let's do a couple of quick checks.

PD(1, 1) = (1-1) * 0! = 0
Obviously, there is no way to arrange just 1 ball with our restriction.
And
PD(2, 1) = (2-1) * 1! = 1
Correct, as there is only 1 way to arrange 2 balls with out restriction.

Let's also check if we are in agreement with full derangement.

PD(N, N) is full derangement - no ball in its corresponding bin, so this should be equal to D(N) .

Let's see. Using our formula,

PD(N, N) = (N-1) * PD(N-1, N-1) + (N-1) * PD(N-2, N-2)
= (N-1) * ( PD(N-1, N-1) + PD(N-2, N-2) )
= (N-1) * ( D(N-1) + D(N-2) ) (using induction)
= D(N)

This was definitely harder than derangement, but it was also much more fun to prove a more general result.

Anoop Desai

Anoop Desai was a contestant in American Idol season 8, finished at 6th place. His first music video is out. Pretty good song for a newbie.

Rome (HBO Series)

Review : Rome (a mini TV series)
Produced by : BBC and HBO
Aired : 2005 to 2007
My rating : 8 out of 10

HBO's "Rome" TV series covers the events of the Roman Empire in 1st century BC. It ran for 2 seasons in 2005 and 2007. Both the seasons are available on DVD. The first season has 12 episodes, starting with Julius Caesar's victorious conquest of Gaul and ending with his assassination on Ides Of March. The second season has 10 episodes beginning with Marc Antony discovering the assassination and ends with his eventual death (along with Cleopatra) when Octavian's (Augustus Caesar) army defeats him in Egypt.

With so many movies already filmed about all stories related to Roman Empire, what's the point in watching a TV series that cannot be really as "grand" ? Plenty of reasons, I would argue. It may not be as grand as a big budget movie, but it's very detailed. And in fact, the budget was not all that small. Due to expenses needed to recreate Rome, the series was cut short to 2 seasons, and the story at the end was compressed to a few episodes.

We follow 2 common soldiers in Julius Caesar's  army, Lucius Vorenus and Titus Pullo. Their lives are entangled with that of the nobility and all the dirty politics that was rampant during that time. The story of Roman Empire (as much as is covered by the series), remains very faithful to the known history than most of the movies I have seen. Of course, some kind of artistic license is needed to make it dramatic.

Rome is recreated as accurately as is possible. The sets, costumes, customs and daily lives of people in this series feel real. The acting is top notch. You understand every character, the motives and come to like them of hate them. Not a single soul is clean - in fact most are shallow, selfish and outright despicable. But that's how it was. Life was hard. Nothing mattered more than power. Revenge and brutality were commonplace. In spite of the lavish palaces and a Republic government (in theory),  it was not a pretty world for most people, and it's shown as it was.

That's the real strength of the series. It doesn't depict grand battle scenes with awesome CGI effects, but shows the lives of people in extreme close-up. It may be too much of a close-up for many viewers, but that's what the series is about.

I highly recommend this series. But with a strong warning. Things are way too explicit and graphic here. Subtlety is completely nonexistent. If your sensibilities are easily offended, then stay away. I am not exaggerating. This is correctly rated "MA" - and is not suitable even for teenagers.

Singularity

Book Review : Singularity
Author : Bill DeSmedt
My Rating : 2 out of 5 stars

In June 1908, there was a meteor impact in Tungaska, Siberia. This is the largest known impact on land, as powerful as 1000 atom bombs and devastating millions of trees in a 2500 sq km area. It's sheer luck that this was in an isolated area in Siberia, else the consequences would have been truly horrific.

There have been many alternate theories about the cause, including a crash of an alien spaceship. One theory, with little scientific backing, is this event was due to a subatomic black hole that passed through the Earth. There are many problems with this hypothesis. Can black holes be that small ? Can they be stable if they are this small ? How can such a small black hole get created in the first place ? If it was created during the early period following the Big Bang, how did it survive for this long ? That's for theoretical physicists to debate.

But one simple reason for opposing this theory is, lack of an exit event. If indeed a black hole passed through the Earth, then there would have been another explosion as it exited the Earth. Well, author Bill DeSmedt, has an answer. The black hole never left the Earth ! It's trapped inside and slowly eating the Earth away !!

Look, most science fictions have to bend the known laws of Physics, else even a "simple" thing such as inter-galactic travel cannot be used to make a story. So I am willing to play along - but to a limit. The ideas started transcending that limit when some evil Russian plans to "capture" the black hole using magnetohydrodynamics - yeah, look up that term, it's real. They track it's trajectory inside earth, build a trap exactly at the right spot and boom - capture it, just like that. I wish, building particle accelerators was that simple ! And if you think that's bizarre, wait till you find out, why exactly did they want to capture it. Are you ready for the spoiler ? To change history, of course ! To make Russia great again. Whatever.

Actually, that last part about changing history could have been made really interesting. And that's where the book really really really fails miserably. The last few chapters gave me an impression, that even the author was completely confused as to how to tame the weirdness of his own ideas. So many things are left unexplained, may be because it was impossible to explain them.

The characters are as clichéd as they can get. A computer hacker who can do pretty much  hack into whatever he feels like. A beautiful female spy, who has lost her parents. A rich Russian with evil intentions. How novel.

Books like this, give Science Fiction a bad name. I have to mention the hilarious awkwardness of the prose.

In the fresh, clean hours after midnight, with the petty interruptions and annoyance of the day fading like dreams at dawn, he essayed prodigies of system design, assembling soaring fairytale architectures of logic, elegance, and power from dry dust of global variables and reserved keywords.

Wow.

DEEP TIME. Its texture is the granular trickle of sand through the fingers, its signature sound, the echoing of footsteps down marble corridors, past doorways opening onto light of other days.

And

... the cool and quite were all but sepulchral.

Sepulchral ? I know my English is quite bad, but reading a fiction book should not make you feel like appearing for GRE.

This book should have been very good. Mixing spy thriller with science fiction is a tantalizing idea. And it does start well - except of course the forced usage of jargon. And then it just fails. Flat on its face. I have to recommend against reading this book.

Obesity Crisis :-)

Heard on Colbert Report.

Folks, there is an obesity crisis in America. Do you know that 33% of Americans haven't had a chance to be obese yet ?

Khamosh Pani

Movie Review : Khamosh Pani (Silent Waters)
Released : 2004
Language : Punjabi
Director : Sabiha Sumar
Starring : Kiron Kher, Shilpa Shukla, Aamir Malik
My Rating : 9 out of 10

The partition of 1947 - when the state of Pakistan was created - has been a subject of many movies. It was a traumatic experience for displaced families to say the least. As is unfortunately usual in such ethnic struggles, the ultimate price is paid by women. The point "Khamosh Pani" illustrates, is that the nightmare doesn't ever end - it just comes back in different but equally devastating forms.

Director Sabiha Sumar tells the story of one such woman "Ayesha" with simple honesty. Ayesha (played perfectly by Kiron Kher) lives in a village in the part of Punjab that ended up in Pakistan. Ayesha is a widow and her life revolves around her son Saleem (Aamir Malik) - who is becoming an adult, but still is not very mature. He has a girlfriend Zubeida (Shilpa Shukla) - who has big dreams of her own. Overall their life is typically placid.

But this is year 1979. Prime Minister Bhutto is hanged by the army dictator Zia Ul Haq, beginning Pakistan's long steady descent into the grips of Islamic Fundamentalism. We are only told about these events via news on radio, but we witness its effect on the protagonists. It's easy to see how an aimless lost youth like Saleem is an easy target to be devoured by fundamentalist recruiters. His conversion begins at the worst time for Aayesha. The Sikh people are allowed to come to Pakistan to visit their place of worship. This creates religious tensions. For Aayesha, this brings back all the painful memories she was trying to suppress all the while - because one Sikh person is looking for his sister who was left behind.

This is a difficult and excruciatingly sad subject. Women who could not escape in time either lost their honor or were killed by their own family members in the name of protecting the honor. It's not hard to guess what Ayash'a past must have been, and Sabiha Sumar treats it with utmost sensitivity.

That is the real hallmark of this movie. The directory just completely avoids the trap of over-dramatization. The entire movie feels really real. The village, the people, their interactions, everything. There is no preaching, no propaganda, just storytelling. There is a lot of symbolism, but nothing overt. It's impossible to miss the Aayesha's tragedy - she could never escape the horrors of partition. It took away her remaining happiness and life many years later, but take away it did.

Everybody performs well, although I thought Saleem's transformation from a naive youth to a blind fanatic deserved a better performer than Aamir Malik, who was overshadowed by his 2 main costars. We don't expect anything less from an actress like Kiron Kher and she delivers far more. Her portrayal of Aayesha is absolutely authentic.

This is a sad movie and not for kids. I would definitely include this in "must watch" category.

Derangement

"Derangement" is a counting problem that commonly occurs in many puzzles, probability questions etc. I wanted to solve another counting problem, that required building upon derangements. So I brushed up on combinatorics to find a quick formula for derangement. It was so elegant, that I had to put it up here.

Derangement is such an arrangement, that no object is in its correct place. For example, if you are to create a derangement of all letters in the alphabet (A .. Z), then such an arrangement should NOT have A at the first place, and B at the second place, and so on, till Z cannot be at 26th place. There is precisely one "forbidden" spot for every object.

As an example, consider only 3 letters [A B C]. The only possible derangements for these letters are [BCA, CAB].

The question is, in how many ways you can do this for N objects ? Let's use the notation for derangement as D(N). Obviously, D(N) < N!.

This problem can be phrased in different ways.

Say N people went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, they deliberately put on a wrong name tag on their shirts. No person had the right name tag. In how many ways can they do it ?
Answer : In D(N) ways.

Another one.

Start with 2 deck of cards. Shuffle each of them separately, and put it next to each other on a table. Start picking one card from the top of each deck, compare and discard. Keep doing it till all 52 pairs have been compared. What is the probability that not a single pair had same cards ?

Answer : D(52) / 52!. Favorable outcomes divided by total number of outcomes.

But what's the formula for calculating D(N) ? It's very elegant.

Think of N numbered balls (from 1..N) to be put in N numbered bins (from 1..N). The task is to arrange N balls so that no ball is in the bin with the same number.

Start with any ball i. It cannot be put in bin i, so there are N-1 ways to choose a bin. Let's say it was put in bin k. For every such choice, following is true. We examine ball k, whose bin was chosen for ball i.

1. Either ball k was put in bin i.

2. Or ball k was NOT put in bin i.

These are mutually exclusive choices. So we can find the count of ways each can be done, and sum them up for getting final answer for D(N).

First choice, ball k was put in bin i. Just remove, the pair bin i and k, with balls k and i in them respectively. That leaves us N-2 balls to be put in an derangement. Each having exactly one forbidden spot. This is nothing but D(N-2).

Second choice, ball k is NOT to be put in bin i. Remove the bin k (with ball i in it). And rename the bin i to bin k, as the ball k is NOT to be put in it. That leaves with N-1 balls to be put in derangement. Each having exactly one forbidden choice. This is nothing but D(N-1).

So for every choice of k, there are D(N-1) + D(N-2) possible number of derangements. Since there are (N-1) choices for k, the formula is

D(N) = (N-1) * ( D(N-1) + D(N-2) )

This formula is very similar to Fibonacci numbers ! But the multiplication makes it grow really faster than Fibonacci sequence.

By defining D(0) = 1 and noting that D(1) = 0, we can calculate all derangements. For numbers up to 10, they turn out to be

D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44
D(6) = 265
D(7) = 1854
D(8) = 14833
D(9) = 133496
D(10) = 1334961

The math textbooks will also show another result that makes this even more beautiful.

The limit of (N!)/ D(N)  as  N  approaches infinity is the number
e (= 2.7182816576664037...).
This means, the answer to our probability question is very close to
1/e (= 0.367879464285714...).

I will be building on this in another problems soon.

UPDATE : See the solution to Partial Derangement which builds on this post.

Company Man

Book Review : Company Man
Author : Joseph Finder
My Rating : 4 out of 5 stars

This was the first book I read by Joseph Finder, who has written many best-sellers. And I was impressed.

The main character - Nick Conover - is CEO of Stratton, a huge manufacturer of office furniture, based in a small town in Michigan. He has recently fired thousands of employees and almost everyone in the town dislikes him. His house keeps getting broken into and he is receiving threats. To add to the stress, he has to raise his 2 kids (a young daughter, and a teenage son) all by himself, as his wife died in a car accident a year ago.

As the story opens, his family dog gets brutally murdered by the intruder, and during the next intrusion, Nick shoots the intruder and kills him. Instead of going to the police about it, he decides to hide it. Much more is written on the inside cover, but I will leave it there. And I would say, forget the inside cover, just read the book.

The books starts out slowly. Finder takes his time developing the characters, creating their lives in your mind. That's the real strength of the book. The interactions feel real. Their world feels real. Finder has done good research into how such a corporation would function on a day to day basis. It reminded me of Arthur Hailey.

Those strengths made me overlook the weaknesses. Our main guy Nick is not all that bright. Wonder how he became a CEO ! It takes him forever to see through the office politics. His judgment is quite poor. Maybe that's author's intention. The mystery itself and its inevitable conclusion is not that hard to guess. Still I found myself getting glued to the last part of the book, reading late into the night to finish it off.

I also have a problem about how long it took Finder to get into the rhythm. It was well past 300 pages when the book became truly gripping for me. Else I would have given this 5 stars.

I am very happy to have read this book and highly recommend it to mystery lovers

Juno

Movie Review : Juno

Director : Jason Reitman
Genre : Comedy
Released : December 2007
Starring : Ellen Page, Michael Cera, Jennifer Garner, Jason Bateman, Allison Janney, J.K. Simmons
My Rating : 8 out of 10

For some unknown reasons, I had simply missed out on watching Juno till now. It had all the buzz when Diablo Cody won the Oscar for Best Screenplay and the movie had a few other nominations. But then I just forgot about it. It was a mistake that I recently corrected.

The story opens when Juno (Ellen Page) - a teenager - discovers that she is pregnant. She chooses the route of adoption over abortion. Fortunately, she has supportive parents (Allison Janney, J.K. Simmons) and even finds the perfect couple (Jennifer Garner, Jason Bateman) desperately wanting to adopt her baby. We see these relationships progress till the story ends with the birth of the baby.

The marketing department for the movie has labeled this as a "comedy". I disagree with that label. Not because the movie is not funny. It certainly is. Although it's unlikely to generate any riotous laugh, but it will surely make you chuckle many times. The reason for my disagreement is, the movie is way more than a comedy. In Juno, what is not being said, is equally important.

Juno does have a tough external shell and is constantly bubbling with energy and quirky one-liners. But we also see her sensitive vulnerable side, and we completely understand what's going on in her mind, without she actually telling it all. That's true for all characters, even the ones that have very little screen time. It's amazing how Jason Reitman and Diablo Cody can paint a complete character with so few brushstrokes.

They are helped by superb performances all around. Juno may come across as a typical teenager initially, but Ellen Page shows us that she is also smart and courageous. Forced into adulthood, she is still learning about the world. Part girl, part woman, she is sometimes confused, even as she doesn't really want to admit it. Jennifer Garner is remarkable too. In general the female characters in this movie are stronger and more likable than the male characters.

The movie navigates around every melodramatic pothole but still clearly conveys the feelings. I would like to highlight the scene at the mall when Juno runs into Vanessa. There are surprising dialogues mixed in an emotional scene. That combination of sweet and tangy flavors is sprinkled all over the movie. And I would also urge you to listen to the songs that play in the background. The lyrics are amusingly offbeat, both musically and literally.

It's a short movie but still feels very complete. I highly recommend it.

Lexicographically Lowest Possible String

The qualification round for Facebook Hacker Cup happened last weekend. I was initially tricked by one of the problems. I thought I had solved it - but the next day while browsing some blogs about the problems,  my wife discovered a mistake I had made. Fortunately, I had solved the other problem correctly to qualify for the next round.

The problem appears simple enough. You have been given a set of string and you have to find a "lexicographically lowest possible concatenation" of these strings. An example makes it perfectly clear. Assume that the only characters in the strings are lowercase characters from 'a' to 'z'.

If the input is abc xyz pqr . The correct output should be abcpqrxyz .

Of all the possible ways in which you can concatenate the strings, this will be the first one if you arrange them in ascending order. Conceptually, this is equivalent to saying, find all the N! ways in which the strings can be combined, sort them in ascending order and output the first one.

That brute force approach is horribly inefficient. So the quick solution that comes to mind is, just sort all the strings in ascending order, and then iterate over them to concatenate them one after another. That will work with our example. That's what I did. So what's the issue ?

Problem with natural sort and concat 

Consider the following example case where the input is just these 2 strings[xa xab]
Since "xa" < "xab" a simple sort and append method will produce xaxab
This is not correct, as the other possible concatenation is the correct answer.
Because xabxa < xaxab

And that's the problem.

For any 2 strings S1 and S2, S1 < S2 does NOT imply (S1.S2) < (S2.S1).

This happens only if one string is a starting substring of another. There is NO problem with natural sort and concat in following cases.

For [abc pqrabc] the answer is still in natural order = abcpqrabc which is < pqrabcabc
For [abcd abczpqr]  the answer is still in natural order = abcdabczpqr which is < abczpqrabcd

Even when we have a starting substring, the simple natural sort and concat can be correct.

For [xa xaz] answer is still in natural order = xaxaz.

Correct solution

My new solution is still a sort and append. But when the strings are being sorted, simple comparison "if S1 < S2" should not be used. The correct comparison is "if (S1.S2) < (S2.S1)". So the strings should be placed in ascending order using the comparison of their concatenations.

Generally speaking, before concatenating the strings should be ordered
[S0 S1 S2 ... Sn]
such that
for any k, the concatenation (S[k-1].S[k]) < (S[k].S[k-1])

Then the entire concatenation would be lowest.

Informal Proof

That sounds intuitively correct. Still, since I was tricked once, I just want to make sure that this approach is indeed correct.

Let's say while sorting we decide to order the strings as [S1 S2] because (S1.S2) < (S2.S1). Then we check string S3, and since (S2.S3) < (S3.S2) we decide to put it last as [S1 S2 S3]. This will give us S1.S2.S3 as our answer. It's correct based on comparison of [S1 S2] and [S2 S3]. But what about the comparison of [S1 S3] ? How do we know that S3 should not be put ahead of S1 giving us the answer S3.S1.S2 ?

To prove that above ordring is indeed correct, we need to make sure that our comparison is transitively correct.

Prove that, if (S1.S2) < (S2.S1) and (S2.S3) < (S3.S2), then it implies (S1.S2) < (S3.S1)

The only interesting case in our ordered list [S0 S1 S2 ... Sn] is when the natural sorting order is violated for all 3 strings. Any ordering [S1 S2 S3] generated by our algorithm is trivially correct if S1 < S2. There is no point comparing S3 to S1 here. In fact we can simply combine such string pairs into one bigger string, and keep reducing the number of strings till we have a violation of the natural order in at least 3 successive strings.

Consider the natual sorting order [xa xab xabc]. But for us, the correct order is [xabc xab xa]. This is the only interesting case. We want to make sure our derived answer xabcxabxa is really the lowest.

Another example.

Consider the natual sorting order [xa xab xabz]. But for us, the correct order is [xab xabz xa]. This is NOT intersting as the order for first 2 strings [xab xabz] is just natural ordering. We can reduce this to [xabxabz xa] and now our solution is trivially correct.

To repeat, the natural sorting order of [S1 S2] will be violated only if entire S1 is a substring of S2, and (S2.S1) < (S1.S2).

So let's consider the case generally and name the substrings as X, Y and Z.

S1 = Z.Y.X

S2 = Z.Y

S3 = Z

Clearly S3 < S2 < S1 using natural order, but solution using our comparison came out to be in exactly the opposite order as [S1 S2 S3]. Let's prove it correct.

Also our algorithm decided that S2.S3 < S3.S2 - meaning Z.Y.Z < Z.Z.Y Removing identical substring from the beginignof both, gives us Y.Z < Z.Y and this implies Y < Z.

Now S3.S1 will be Z.Z.Y.X and compare this to S1.S2 which is Z.Y.X.Z.Y. Since we know that Z > Y, it follows that Z.Z > Z.Y. Therefore (S3.S1) is indeed > (S1.S2) and hence S3 should not be placed ahead of S1.

Maybe I made it too complicated. But I could not figure out a simpler proof. I can also prove it a bit more formally using induction, but I don't think it's simpler. In any case, the solution is really very simple to implement, and that's what matters !

The Alexander Cipher

Book Review : The Alexander Cipher
Author : Will Adams
My Rating : 3 out of 5 stars

I am always on the lookout for books by new authors. When I saw "Alexander Cipher" and read the description, I was very enthusiastic about reading it. Now, having read it, I am not so enthusiastic about recommending it.

The book calls itself thriller, and it's written in the style of a modern page turner. Problem is, there is not enough incentive to keep turning the pages. That's a shame, because there is definitely a lot of potential here. The idea is cool, the author can write a complex plot and develop characters if he chooses to. But by focusing more on the Hollywoodish presentation than substance, the author lets the potential remains just that - a potential. On the plus side, there are no major logical holes - at the end things are nicely tied together.

During a building construction (in Alexandria, Egypt) a necropolis gets discovered which leads to some clues about the real location of the sarcophagus of Alexander the Great. The excavation of this site and ensuing search for the location of Alexander's tomb entangles the lives of all characters in the story. The hero is Daniel Knox, an archeologist who is connected by just one degree of separation to everyone else in the story.

This is a decent idea, sort of Indiana Jones, sort of Da Vinci Code. And there is plenty of running around - in fact way too much running around. That doesn't leave author much scope to do anything else. There is a bit of history lesson, there is some character development (especially the Egyptians) - but there is no puzzle solving as was in Da Vinci Code. And since we are not invested in any of the characters, we really don't feel much for them, let alone root for them. As a result, the countless action scenes do not feel thrilling, as we really don't care about what happens to whom.

I am OK with mindless page turners, but not if they are this long. And this didn't have to be like that. Egypt, Alexander, lost tomb, treasure hunt with clues - this is more than enough ammunition to sprinkle a handful of historical trivia in a gripping thriller. Just stop making your characters run from a place to place every third page, escaping one danger after another and sit down to develop them, throw in some puzzles, blend in some more history, take the reader with you on an intelligent adventure ! Oh well.

I can neither recommend against reading this book, nor for it. Set your expectations right, and you may like it.

It's Complicated

Movie Review : It's Complicated
Director : Nancy Meyer
Genre : Comedy
Released : December 2009
Starring : Meryl Streep, Alec Baldwin, Steve Martin
My Rating : 6 out of 10

Nancy Meyer is known for light, comedy movies and "It's Complicated" is no exception. And .... hmmm, let's just say as it is - this is a "Chick Flick" just like her other movies.

But is it good ? The script starts out well, has some really funny moments. After about 3 quarters of it, the script forgets that it started out as a comedy, tries to change its genre to drama and makes "It's too complicated for itself". That's my attempt to make a pun on the name, just in case you missed.

Jane (Meryl Streep) is the owner of a bakery in an up-scale neighborhood. She is a divorcee, with 3 grown-up kids. She accidentally starts an affiar with her ex-husband (Alec Baldwin) who is currently married to a much younger woman. The romantic triangle is completed by Adam (Steve Martin) who is helping Jane build a dream kitchen.

It makes for an interesting and a bit novel set-up for a light-hearted comedy with a clear target audience demography. I have already stated what's problematic with the movie. Still it has numerous strengths to make it worth watching. The main strength, of course, is the perfect cast. Alec Baldwin does a nice job and we know exactly what type of person his character is. Steve Martin, as a bit of surprise, plays a serious, sensitive and reserved person. The center of the movie is naturally the Godess of Acting herself - Merryl Streep.

The movie is less than 2 hours, but could have been even shorter. It is definitely enjoyable. There are more than a few adult only jokes in it, else it could have been OK for kids. In any case, I really doubt if there are any kids (of any age) interested in watching romance between old folks ! Just watch it for Merryl Streep, if for no other reason.

The Brass Verdict

Book Review : The Brass Verdict
Author : Michael Connelly
My Rating : 3 out of 5 stars

Michael Connelly has written numerous best selling mystery books - based on 3 main protagonists - the detective Harry Bosch, or the lawyer Mickey Haller or the reporter Jack McEvoy. "The Brass Verdict" is a Mickey Haller (or called the Lincoln Lawyer) book with a guest appearance from other 2 characters as well. That was the main reason for me to try this out as my first Michael Connelly book - 3 in 1 !

A movie producer is arrested and being charged for a double murder of his wife and her lover. The first lawyer hired by the movie producer is also murdered and the case lands on the laps of Micky Haller. As he starts building his defense, naturally he realizes that there is more than meets the eye. Giving any more synopsis, would give out some surprises.

As a mystery, this is quite decent and well-structured. Everything falls neatly in place by the end, nothing seems forced, there are no logical holes and the conclusion is quite satisfying.

What made me give this only 3 stars is they way clues are tied together. In spite of being written as a first person account - we are not given enough insight into the mind of our protagonist. Of course complete insight will mean no surprises, but some of the real investigation is done by Haller's helper and we are never told what he discovered. We just hear the deductions made by Haller. The best mysteries are where the reader has almost the same amount of information as the investigator, but it's presented in such a way that the reader is never sure how to tie it all together - till it's explained by say someone like Hercule Poirot.

Nevertheless, this is a very nice book to read. Connelly excels at building a real multi-dimensional character of Haller - who is far from perfect. He takes his time, so the book may feel slow to some. To me the character development was a big plus point. We are given a nice tour of how the justice system really works, and the subplots are interesting too.

I definitely recommend this book. Personally, for the next book by Connelly, I would read a book from his other series - featuring detective Bosch - than by the same Mickey Haller.

Attack of the Frogs !

I have an epidemic of frogs in my backyard. There are harmless to plants, but there are just too many. But I cannot kill them, because they are "aaawwww so cute".  Now they are expanding their territory and climbing over walls and windows !

The Big Bank Theory

The only real financial journalist in the country happens to work for the comedy channel ! Why is it only Jon Stewart's responsibility to catch someone lying ? This time it's The Bernanke who is lying about "printing money".

The Daily Show With Jon Stewart	Mon - Thurs 11p / 10c
The Big Bank Theory
www.thedailyshow.com
Daily Show Full Episodes Political Humor & Satire Blog</a> The Daily Show on Facebook

Invention of Lying

Movie Review : The Invention of Lying
Directors: Ricky Gervais, Matthew Robinson
Genre : Comedy
Released : October 2009
Starring : Ricky Gervais, Jenifer Garner, Rob Lowe
My Rating : 6 out of 10

"The Invention Of Lying" is a very rare comedy that can make you ponder as much as it can make you laugh.

They idea is innovative. Imagine a world where no one ever lies - because they simply cannot ! It's not a matter of choice for the people in this alternative universe - they just speak the truth. All the time. Even when it's the harshest thing to say.

Mark (Ricky Gervais) is a loser who works in a movie producing company. We meet him as he is going on a blind date with an attractive woman Anna (Jennifer Garner). First look, and she announces to him that he is not good enough for her. But out of politeness they go to a restaurant where the waiter tells him that she is way out of his league. This is how people talk to each other in the movie. Not in an insulting tone, but politely stating things as they are. It's a simple and cruel world.  And it's hilarious.

Mark discovers by accident that he can lie - and things get very interesting. Instead of using that ability to lie for his own petty benefits, he starts using it to comfort people. What an idea ! Saying things that are not true can help make someone feel better. Note that there is no such words as "lying" or "truth" in their vocabulary. And there is no word for "God" either.

That's where the movie transcends itself from being just a comedy. It's a funny take alright - but the viewer cannot escape the questions that are being posed in an indirect way. The entire notion of Mark's "Man in the sky", relies on just make-believe statements in order to make people feel better.

That's what I mean when I say, the movie forces you to ponder as much as it can make you laugh. Is lying all that bad if it makes you feel better ? Is that the basis of all religions ? If these unverifiable beliefs actually help people live their life, is that a justification enough for spreading them ? Of course, a comedy movie cannot be expected to answer those questions - these debates have been going on ever since humans developed an ability to introspect. I prefer these subtle questions far more than the extravagant philosophical discussions spawned by the "Matrix" trilogy.

This turns out to be a double edged sword. As much as it helps the movie rise to a different level, it also makes it a bit unwieldy. The comedy sputters and the movie gets very unfocused in the end.

Nevertheless, Ricky Gervais and Jennifer Garner, both make it work. Their acting is spot on. I recommend this movie - it's short, funny and thought provoking. It's not for kids.

Last Crop Of 2010

Now that the temperature is dropping below freezing, I decided to remove all the tomatoes and jalapenos (and other peppers) from the plants. Made a huge batch of Insane Hot Tomatillo Salsa.

Take this quick quiz. How many tomatoes and peppers are there ? :-)