August 12, 2011

I recently finished reading The Black Swan (well, I've yet to start the extended essay that has been added to the second edition, but still). A moderately interesting read, with a few intriguing and insightful ideas, but there is no satisfaction at the end, the satisfaction that comes from reading a book that puts its key messages in a tight-knit, coherent form and packs a good punch, so to speak. The book would also have benefited from a better editing process -- the language doesn't flow that easily in quite a few places. A good thing I got this book as a gift and didn't have to spend money out of my pocket.

The author's contempt for CEOs, Frenchmen, and academics (economists in particular) also comes through too strongly and bitterly -- this is probably his F*** You Money talking. Somewhat ironical, considering that there is a quote from a trader in the book along the lines of "Be nice to people on your way up, since you'll meet them on your way down". He could also have gone a bit easy on the frequent attempts at cheap titillation through mentions of prostitutes, how many lovers did Catherine the Great have, and so on.

With respect to the meat of the book, can't really disagree with the author's contention: we do not know what we're doing half the time, unknown forces are lining up against us as we speak, it's no use trying to do long-term (maybe even short-term) predictions, and our brains are hardwired to see patterns where none exist and are prone to all kinds of cognitive biases (on a side note, this paper does a more thorough job of this). Scalability is a theme that runs through the book -- be it scalable/non-scalable professions (the relation between the amount of money one makes and the physical number of hours put in -- e.g., doctors/plumbers vs hedge fund managers) or scalable odds (Gaussian vs Mandelbrotian).

While on the subject of scalability and the medical profession, today I learned that one can get an *ahem* discount of Rs 5000 on an MRI scan bill of Rs 8000 if the doctor is kind enough to not ask for his commission from the diagnostics center.

GitHub

I've finally gotten around to collecting all my code in a single place. This is a pretty much complete collection, except for my JSON implementation for VisualWorks. A recent scare with my home laptop (a faulty chip related to the display) is the reason for this. I have an external drive where I periodically back up stuff, but I was not able to access my files during the absence of the laptop. I could have taken them from the external drive, but didn't want the hassle of again bringing the laptop contents in sync; not to mention I didn't have much time during this period due to a family emergency.

Predicting the English Premier League - Part 2

As promised, here are the results of the number crunching. Some of the number crunching is still ongoing as I type this -- to figure out which of the parameters give the best results (the code in the AWS instance is running for six days; hopefully it will terminate before I hit the free tier limit of 750 hours).

First, a list of the prediction methods considered:

1. Homegrown method 1: In this method, we consider three parameters: home advantage, total form and recent form (three matches). Whichever team comes out on top on the cumulative score based on these three factors is designated the winner (no draws in this method).

2. Homegrown method 2: This method uses historical (this season only) values for fractions of home wins, draws and away wins; generates a random number between 0.0 and 1.0, and chooses one option based on where the number falls in the spectrum (length of each segment in the spectrum (HW, DR, AW) determined by the historical averages).

3. Random: Generate a random number between 0.0 and 1.0. If this is <= 0.33, it's a home team win; if it's between 0.33 and 0.66, it's a draw; otherwise it's an away team win.

4. Linear (GLM): The generalized linear model with least squares regression.

5. KNN: The K Nearest Neighbours method. There are two variations to this -- one where we simply consider the three classes as home win, draw, and away win; the other where we convert the three classes to real numbers. We also vary the number of neighbours considered from one to three.

Some general notes about the exercise:

1. We use data from match-week 10 to match-week 21 (inclusive) as training data for GLM and KNN

2. Predictions are for match-week 22 onwards

3. All match-weeks do not have the same number of games for various reasons (scheduling, snow, etc.)

4. These are the predictors used:

• Home record of home team
• Away record of away team
• Total record of home team
• Total record of away team
• Most recent (three matches) record of home team
• Most recent (three matches) record of away team
• Goal difference of home team
• Goal difference of away team
• Rank in points table of home team
• Rank in points table of away team

Here are the results of the prediction, first in table format, followed by graphs (click to enlarge):





As I mentioned earlier, pretty 'meh' results. Maybe the brute force method to identify the best parameters will yield something better. This method basically considers all the combinations of parameters from the above ten, and computes the average accuracy of prediction -- for the same training data and the same prediction period -- for all of them, and picks the combination (there are actually two combinations, one for GLM and one for KNN) with the highest value. But I'm not holding my breath.

Update: The brute force number crunching is finally done and the results are in. KNN (n=3) with classes, with two three parameters -- the away record of the away team and the total record of the home team the most recent records of the two teams and the rank of the home team -- gives the most accurate predictions:

Quote of the Day

“I am the president of FIFA; you cannot question me” -- Sepp Blatter, President of the Federation of Insufferable F**tards Associations

Lisp Compiler

I am working through "An Incremental Approach to Compiler Construction". Great fun. I started reading Lisp in Small Pieces (LiSP) a while back, but this paper is a more hands-on, tutorial approach; you're able to see the fruits of your labour sooner and measure your progress better. It would have helped more if I could have gotten my hands on the extended tutorial that is supposed to accompany the paper -- it seems to have disappeared from the web. Anyway, tackling the project with only the paper for company is more challenging.

Both this paper and LiSP use Lisp dialects as the source and implementation languages. While this has a number of advantages (can't imagine using C or C++ as the implementation language *shudder*), there is a minor drawback (I say minor because the benefits far outweigh the costs; most notably a) the joy of coding in Lisp and b) the obviation of the need for a parser) -- when you're writing regular Lisp code, you are juggling with the concepts of compile-time, run-time and read-time (to be fair, I haven't felt the need to concern myself with read-times yet), whereas when you're writing a Lisp compiler in a Lisp dialect, you now have two sets of these times to contend with -- one for your compiler and the other for your generated code. Moreover, there are transformations that convert the source expressions into simplified Lisp expressions in the source dialect, which adds to the fun and merriment. You are writing Lisp code that is acted upon by Lisp code, which then takes a quoted Lisp expression and produces another quoted Lisp expression, which is then acted upon by yet another piece of Lisp code which generates the equivalent assembly... As I said, great fun.

On second thoughts, I'm not sure whether the point about two sets of times (read/compile/execute) is really valid. The complexity mentioned at the end of the previous paragraph captures the situation more accurately.

May 24, 2011

The two most powerful human emotions are said to be relief and love, and this was borne out with the closure of the EPL season this weekend. There is something pathetic, and at the same time endearing, about supporters going berserk because their team scores a goal that is neither the equalizer nor the winner, but is one which enables their goal difference to climb above that of their fellow languishers in the relegation zone.

Speaking of the EPL, I have persevered in the data collection process, i.e., I have the full 38 weeks' worth of match results fed into the predictor. Time for some analysis, and hopefully, insights. Stay tuned.

May 5, 2011

Listening to Harsha Bhogle's inane and faux cheerful prattling has always been an ordeal. I finally figured out a way to handle this (other than using the mute), based on a contrived answer to the question "Why is Harsha Bhogle so happy?" The real answer is, of course, that Harsha Bhogle is so happy because he makes shitloads of money, he's a celebrity, he's got a nice rug, and so on, but that's not the road we are going to go down. What if the reason for the overdose of cheerfulness is that he's not really happy at all, but that His Bubbliness' behaviour hides a dark secret? A secret never revealed to anyone, a secret that festers in his mind every single waking second, a secret that can only be kept at bay by focussing solely on the shining happy things in life, like the way the sunlight dances off Danny Morrison's shiny pate, like the significance of the fact that the number of stumps on both sides of the pitch are wonderfully symmetrical and equal, like how quaint and innocent is the fat lady screaming her head off in the stands when the camera is on her, like how wonderful it would be to have Kiss Cams in the IPL so we can catch geriatric couples expressing their undying devotion for each other before the entire world...

Sorry, I got carried away a bit there.

Anyway, getting back to the dark secret, if you listen to Harsha Bhogle with this backstory [*] in mind, your irritation vanishes completely, to be replaced by a tender pity for the poor man, and you almost want to pull him close to your chest, a la Robin Williams and Matt Damon in Good Will Hunting and repeatedly whisper "It's not your fault" (I said 'almost' because, you know, you don't want to get too close to the rug, considering that it will be just below your nose, with Harsha Bhogle discharging copious amounts of tears on your clean new shirt).

On second thoughts, maybe it was his fault -- I can picture him as a small child saying, "Uncle, do you think stars are God's puppies? Isn't it wonderful the way they twinkle 'Woof! Woof!' all night long? Uncle, why are you looking at me that way...?"

Man, I can't wait to watch the match today and put this theory to test.

[*] Since this is a family blog, I don't want to speculate on the dark secret, but being the sadistic bastard that I am, I'll just throw in the words 'uncle' and 'broom handle'.

May 3, 2011

Two comments from RI that sum up the Osama Bin Laden kill:

So Public Enemy 1, on the run for 10 years, allegedly responsible for the most heinous crime on american soil, is whacked last night/early hours of the morning, DNA test taken, then dumped off a boat the same day, before I woke up. Are you f*cking kidding me?

and

I'd like to throw out this scenario:

Let's just say that both US and Pakistani intelligence have known of Osama's whereabouts for a long time.

And for SOME reason they have thought it in the best interest not to act on this information.

And this man Osama has been very ill for a long time.

One day Osama suddenly passes away.

What would the US do?

To announce the passing by natural causes of Osama?? (this would be an unsatisfactory conclusion to the US public, I'm sure)

Stage an operation and claim that he was killed in said operation?

Dispose of his body to prevent a cause of death from being established?

Pure conjecture, I know.

Natty Narwhal is the suckiest Ubuntu ever. Not just because of the new interface, but from a general stability perspective. Two days' worth of freezes and I'm back to 10.04 (for good, probably; now I know why they have LTS).

Is it just me, or does anybody else get the feeling that the IPL team owners sitting in their special thrones watching the match is the epitome of the rich/poor, elite/plebe divide and all that's wrong with our country?

April 9, 2011

Trust The Pervie Painter to portray something as noble as Anna Hazare's anti-corruption drive in erotic terms. What's the need for a woman with a bare midriff leading the march? Also check out the glutes on the corruption monster.

Raymond Davis freed

Raymond Davis, the CIA contractor arrested in Pakistan for murdering two people, has been freed by the payment of blood money. Two things worth mentioning:

1. The sheer hypocrisy of the American government; on the one hand, Davis was part of the diplomatic corps (no matter that this claim was torn to shreds quickly, which probably led to the whole blood money option -- which, you have to admit, was a stroke of evil genius), and therefore enjoyed immunity against prosecution even for as heinous a crime as murder, while on the other hand:

   In 2004, Mrs. Clinton and the senior senator from New York, Charles Schumer, presented a Bill that advocated cutting foreign aid to countries who owed unpaid parking fines to the City of New York. Senator Clinton was obviously incensed by the fact that diplomats were abusing their privilege. Diplomatic immunity was never intended to allow diplomats to violate traffic laws of the host country, or for that matter, commit murders.
   
   She registered her discontent with diplomatic immunity and argued that it was not “acceptable for foreign diplomats and consular officials to hide behind diplomatic and consular immunity to park in illegal spaces in New York City and avoid paying parking tickets. It is my hope that this legislation will ensure that the City gets the money that it is owed.” Senators Clinton and Schumer were successful in amending the 2005 congressional Foreign Operations Bill in the Senate that froze foreign aid to countries by amounts they owed New York City in parking ticket violations and unpaid property taxes.
   
   ..
   
   In 1987, a car driven by the ambassador of Papua New Guinea, Kiatro Abisinito, hit four other cars in Washington, DC. The ambassador invoked diplomatic immunity. However, the US Attorneys prepared a criminal case against the ambassador for operating a vehicle while being intoxicated.
   
   Consider the case of Georgian diplomat, Gueorgui Makharadze, who in 1997 killed a 16-year old girl in a fatal traffic accident in the US. The diplomat invoked diplomatic immunity and was ready to leave when the Georgian President, Eduard Shevardnadze, ordered the diplomat to stay in the United States and face criminal charges. Mr. Makharadze was convicted by a court and served time in an American prison.



2. The supreme irony of using Sharia Law to save Davis.

Lawyers protest against examination

From The Hindu:

Hundreds of train commuters on the Tambaram-Chennai Beach section were stranded on Sunday for over an hour as lawyers squatted on train tracks between St. Thomas Mount and Guindy Railway Stations... The agitators, who had come to the city from various parts of the state ahead of the All India Bar Examination, were protesting against it.

The nation-wide open-book objective-type qualifying test was held in English and several regional languages across the country.

<snip>

Soon after the examination began, disgruntled candidates stormed out of the exam venue, assembled on the railway tracks and roads outside.

<snip>

[The president of the Tamil Nadu Advocates Association] said that a test of this nature would expose the lack of knowledge of students from local law colleges when compared to those from schools of excellence.

Why am I not surprised? The so called local law colleges breed some of the most politicized and virulent forms of Collegius studentus in the city, specimens whose actions would make the Bus Day celebrators seem like five year old schoolgirls. Getting a strong grounding in law is the last thing on their minds, and expecting them to clear the exam is probably a bit too much. Here's what happened: they enrolled for the exam, paid the fees, and so on, and turned up at the exam center, and a cursory look at the question paper (I'm not even going to comment on the fact that it was a frigging open-book exam) was all it took to convince them that the money paid for the exam would have been better spent on, I don't know, booze and movie tickets.

Bus Day

The yearly ritual of hooligans college students commandeering buses and causing mayhem on the streets of Chennai is not just a law and order issue. It's a symptom of a deeper problem: the government's desire to keep the youth off the list of job seekers for another three years by getting them enrolled in worthless degree programs (not to mention building a support base for political parties). Everyone knows that these degrees lead to nothing except dead-end jobs as sales representatives and collection/verification agents zooming around recklessly on two wheelers -- on the same streets that bring bring back nostalgic memories of beating up bus drivers and stoning passersby and policemen -- but people still enroll themselves in these programs. The pittance that is charged as fees probably contributes to this, but a more important reason is the disdain for blue collar work. The same three years, if they had been spent acquiring vocational skills like plumbing, auto repair, refrigerator repair, and so on, would provide them with a solid career with decent wage potential, but no, they would rather study a bachelor's degree in economics, get barely passing grades (if at all they don't retain a set of 'arrears' in perpetuity) and go to work selling Eureka Forbes vacuum cleaners.

February 22, 2011

This would be funny if things weren't so serious (from Gaddafi's thug of a son's speech; italics mine):

Before we let weapons come between us, from tomorrow, in 48 hours, we will call or a new conference for new laws. We will call for new media laws, civil rights, lift the stupid punishments, we will have a constitution. Even the LEader Gaddafi (sic) said he wants a constitution. We can even have autonomous rule, with limited central govt powers. Brothers there are 200 billion dollars of projects at stake now. We will agree to all these issues immediately. We will then be able to keep our country, unlike our neighbors. We will do that without the problems of Egypt & Tunisia who are now suffering. There is no tourism there. We will have a new Libya, new flag, new anthem. Or else, be ready to start a civil war and chaos and forget oil and petrol.

What a tool.

Meanwhile, there is talk of blond women snipers in Tunisia. Scary stuff.

Via Reddit: The hero of Bahrain. Effing bastards.

February 2, 2011

I came across this op-ed on the revolutions sweeping across the Arab world via The Deccan Chronicle. It tries to make all the right noises and strike the right notes, but doesn't really cut it. Question for the author: any reason why Jordan, Saudi Arabia and Kuwait don't find a mention in the list of autocratic regimes? Wait, I guess I have my answer:

Hussain Abdul-Hussain is the Washington correspondent of the Kuwaiti newspaper Alrai.

Not to mention that this appears in The New York Times/IHT.

E Coli

Man, the E Coli bacterium is one versatile thing. Not only can it serve as secondary storage in a computer:

E. coli gets a bad rap – probably due to the violent illness it induces – but a group of Chinese University students in Hong Kong have found a novel and potentially reputation-changing use for the bacteria: data storage. The team has devised a way to encrypt and store information in the DNA of bacteria to such an effective degree that they say just one gram of E. coli could store the same amount of data as 450 two-terabyte hard drives.

it can also produce oil:

In September, a privately held and highly secretive U.S. biotech company named Joule Unlimited received a patent for “a proprietary organism” – a genetically adapted E. coli bacterium – that feeds solely on carbon dioxide and excretes liquid hydrocarbons: diesel fuel, jet fuel and gasoline. This breakthrough technology, the company says, will deliver renewable supplies of liquid fossil fuel almost anywhere on Earth, in essentially unlimited quantity and at an energy-cost equivalent of $30 (U.S.) a barrel of crude oil. It will deliver, the company says, “fossil fuels on demand.”

December 26, 2010

The Economist has an insightful article about life in Shahabpur, a village in Uttar Pradesh -- the caste dynamics, how well (or poorly) its residents are adjusting to the changing times, and so on. A positive article overall, the frequent references to the villagers' open-air toilet habits notwithstanding (what's with all the "turd"s?). A couple of choice cuts -- one an open admission of corruption by the person working in the village ration shop (What was he thinking? Anyway, he can always claim that his words were mistranslated if the authorities try to prosecute him for this):

Mr Lal, who is popularly considered to have the best job in Shahabpur, also admits to skimming off a share of the loot. He puts his pilferage at a modest 2kg of rice for every 52kg-sack he handles. “I’m only paid 900 rupees a month, so of course I have to steal!” he explains.

and the other a poignant and pathetic story of justice denied:

Two months ago, while Sarju was visiting his parents in Madhya Pradesh, his 13-year-old son Ravendra was beaten senseless by two patel neighbours. The boy had skinned and dumped a buffalo carcass, from which a dog took a meaty bone into their field. Ravendra, who carries scars from this beating, was discovered by the local skin merchant, who informed the local BSP partyman, who reported the matter to the police. They took no action. Yet this flicker of official interest in their plight represents significant progress for Sarju and his family.

December 10, 2010

A surprisingly mature response from our government, when compared to the hysteria in the States over Wikileaks (italics mine):

Some of those conversations with politicians, industrialists and others have been leaked to the media and have been reported on widely. The government has also said that while the leak should be investigated, it cannot stop the media from publishing transcripts of the conversations on the leaked tapes.

This and that

First off, the new Airtel logo: whoever the ad agency is, they made a killing alright ('Let's take the logo we did for the mobile services company, who was it, yeah Videocon, rotate it by 90 degrees, invert it, and, just in case someone calls us on it, we'll change the colour'). Probably the easiest crore or so they've ever made.

The 2G scam is devolving into a tit for tat, with the BJP government in Karnataka being fingered in retaliation. I don't know if anybody still believes that these scams are 'discovered' just when they can be leveraged to the full. Odds are near certain that there are people from the opposite camp watching all the irregularities and filing them away for future use.

It also proves the adage that it is better to ask for forgiveness than for permission, since moves are now afoot to 'regularize' the deals -- through tap-on-the wrist penalties, no doubt -- by which the violating companies got their licenses.

Staying on the subject of mobile services, yeah, mobile number portability is just around the corner, I promise.

Update: This from Reddit.

Speigel interview

I don't know if the questions were really this hard hitting or if the translation is to blame (italics mine):

Schäuble: I'm not that pessimistic in this regard. Although the Irish have accumulated huge debts to bail out their banks, they are making good progress in cleaning up their economy. And I also have great respect for the Greek government's resolve. A few months ago, hardly anyone would have believed that the Greeks would manage to implement such a drastic austerity program. They're moving in the right direction now.

SPIEGEL: Conditions in Europe are not as orderly as you describe. Just two weeks ago, the European Council (the EU body in Brussels that includes the heads of state and government of the membber states) decided to introduce a new crisis mechanism for over-indebted euro nations. Are you satisfied with the result?

and

Schäuble: The Council's decisions are a great success. Only a few weeks ago, many predicted that France would never support Germany in its commitment to a European crisis mechanism. And that the French would be willing to change the European treaties to do so was seen as completely out of the question. But then Chancellor (Angela) Merkel and President (Nicolas) Sarkozy met in Deauville and achieved a historic breakthrough on both issues. It's completely in line with the approach we Germans have always supported.

SPIEGEL: You can't possibly believe what you're saying. Until recently, Germany was demanding automatic penalties for countries that violated the debt rules of the euro zone. That demand is now off the table.

Ballsy, alright. Can't imagine our fawning media (or, for that matter, the American press) doing this.

Predicting the English Premier League - Part 1

My current project is to come up with a predictor for the English Premier League. Football + coding in Lisp + modeling/statistics -- throw in a fat man and it's Christmas. Not to mention, if the predictor is any good, a chance to make some money as well.

The bulk of the coding is complete -- the data loading, extracting the various bits from the match statistics, and so on. It's the prediction part that's tricky, as it should be.

The idea is to identify the predictors first. This is the first cut:

1. The home record for the home team


2. The away record for the away team


3. The overall records for both teams (points scored out of the maximum possible so far)


4. The recent records for both teams (recent == last three matches)


5. Goal difference for the teams

These variables are not strictly fully independent (goal difference and overall record, for example), but I'm going to go with them for now. The prediction takes into account only the current season's matches, though ideally it would be better if it included all the match stats available -- this would help facts like 'Team A has never beaten team B in since 1973', for example, to come through and influence the prediction.

In machine learning terms, the problem is a multiclass classification problem, with the classes being 'home team win', 'away team win' and 'draw'; I am not looking at predicting scores, only results -- I assume one can bet on (and make money with) just results.

I turned to the venerable Elements of Statistical Learning to beef up on the theory, but soon beat a hasty retreat -- if you're just looking for overviews of the different techniques/algorithms and how to implement them, this book is not for you. I next turned to Wikipedia and found it somewhat better, though the sections on statistics and machine learning are still too heavy for my liking.

Anyway, I started with a) a linear regression model, with the three classes represented as equal intervals in [0,1] (I hope this is kosher) and b) the k nearest neighbours algorithm. I wanted to implement both of these methods myself, but the linear regression seemed too much of a diversion, and I settled on using R's glm() function for this instead. KNN proved pretty easy to implement, on the other hand.

The season is only eight match-days old, so there's not a lot of training data. Both the methods' predictions are pretty abysmal (accuracy of around 30-40%), and my own predictor which just looks at the total record and recent form matches these methods' performance (not to mention the method based on random number generation that behaves like the fricken Rain Man).

The next step is to try out other methods and read up on model selection.

Speaking of using Lisp, I have sort of come to a decision with respect to programming languages: it's going to be Lisp from now on (more particularly, Common Lisp). Yeah, I know about Stroustrup's quote about being fanatic about a single language, and the warm, fuzzy feeling I get when I think about Smalltalk, but Lisp is, to paraphrase Robert Pirsig, the high country of the programming world, what with its purity and elegance, "code is data", and the way you're able to accomplish so much with so little, with code that simply flows. I had considered this question earlier, and had settled in favour of Smalltalk, but I guess you gotta do what you gotta do. Anyway, Smalltalk and Haskell are still going to be in the toolbox. Another thing in favour of Lisp is that I made the effort to get to know the Allegro CL IDE better, and have taken a liking to it -- while the shortcomings I have mentioned earlier are still there, my productivity has definitely improved because of the increased familiarity with the shortcuts and IDE features. Oh, and the fact that I took the time to fully grok the chapter on CLOS in On Lisp and had my mind blown helped, too.

Update: Part 2 is here

RIP Bloglines

Bloglines is shutting down. It was (the future tense is a bit premature, since the service will be up till October 1) easily the best online newsreader, Google Reader notwithstanding. I have also tried out alternatives like Newsgator and Feedshow in the past, but I didn't feel as comfortable with them as with Bloglines.

One of the reasons for Ask.com shutting down the service: the supposed waning popularity of RSS as compared to Twitter and Facebook as more effective means of real-time information flow. Doesn't sound very convincing to me. Twitter and Facebook have a place -- e.g., when I want to know how Amitabh Bachchan's digestive system reacted to the new breakfast he tried yesterday (not to mention herding away from Blogger and Wordpress all the non-serious twats with short attention spans and few original things to say), but this in no way reduces the importance of RSS; reports of its death are vastly exaggerated.

Sweden

Got back from a three-day trip to Sweden last night. It was actually a one day trip, if you consider that I was in transit for two of the three days.



Sweden is a lovely country with friendly people. The climate was good too, with summer drawing to a close. But one thing that struck me was the number of smokers I came across -- I don't know where the country ranks in terms of number of smokers per capita, and so on, but people don't seem to be bother about emphysema, cancer, and the like. No regulations on public smoking also meant that I was exposed to quite a lot of second hand smoke during my waits at the railway station. One more thing: people are permitted to take their dogs inside trains too. Good for them.



I spent the one day I was there at Lund, a charming university town more than a thousand years old. The only negative aspect (two, if you count the taxi driver whom I think charged me double the actual fare) was my missing the train to Stockholm because of mistaking the inbound train for the outbound one (in my defence, both trains arrived at the same time, and no train numbers are displayed on the departure and arrival boards), and having to rush to Copenhagen and take an alternate flight, with all the attendant worries about changing your ticket, catching your connecting flight on time, and so on.

Lisp interpreter

From an old interview with Richard Stallman, via comp.lang.lisp:

LinuxCare: Wasn't the LISP interpreter written using lex and yacc?

Stallman: No, absolutely not. There's no reason to use lex and yacc to write a LISP interpreter. The syntax is so simple you don't need it. You'd just be making things harder.

Oops, I never got the memo - a while back I wrote a Lisp interpreter using the venerable old tools. Now is as good a time as any to release the interpreter in the wild -- here it is.

Fare jumpers insurance

Via Xymphora:

[T]urnstile hoppers in Paris have formed an insurance fund so that whenever one of them is caught by the police, their fine/expenses are fully covered.

You guys are just a decade or so late; maybe you can take some pro tips from the experts in Ulhasnagar.

Italy's exit

Italy's exit from the World Cup has been blamed on ageing defenders, unimaginative play, and so on, but I think there's a more direct reason: Buffon's injury. All the three goals conceded by Italy against Slovakia can be attributed to errors by Marchetti, Buffon's replacement -- inability to adapt to an unforeseen loss of possession at the edge of the box (goal #1), not fully covering the near post (#2), and being a step too late to smother the attack (#3). The reason for the attack being lacklustre was Pirlo's absence; witness the improvement in the accuracy of passing and the incisiveness once he came on.

My already low opinion of footballers has sunk even lower, watching their histrionics. Unless something is done to curb their cynical behaviour (allowing post-match usage of video footage to dish out liberal punishment would be a start), using 'football' and 'beautiful game' in the same sentence would make sense only if there is a 'not' somewhere in between.

Some vuvuzela humour (courtesy Reddit):

1. A web site that adds the vuvuzela blare to your browsing experience
2. Vuvuzela instruction manual
3. A vuvuzela hits CD
4. Heaven and hell
   

By the way, the broadcasters seem to have done something to reduce the noise -- things are much quieter in the round of 16.

All time favourite musical moment in a movie

Someone asked the question "What is your all time favourite music moment is a movie?" at Reddit. The first thing that comes to mind is the climax of The Last of the Mohicans, and it's not just me:

I like the part of Last of the Mohicans when they are running up the mountain path to exact revenge. Awesome instrumental accompanied by chopping people up with large blades. Gives me the chills every time.

Amen to that -- goosebumps time, alright.

World Cup

1. Yes, please do ban the fricking vuvuzelas. I had to twiddle with the sound system in my TV for half an hour to figure out a way to create a custom audio profile that reduces the impact of their blaring.


2. I've realized something which has been gnawing at me for quite a while: 90% of football -- 90% of all matches, as well as 90% of any match -- basically sucks. Unless it's your team playing, watching the ball being swatted about as if it's a pinball machine, with nary a goal-mouth action for practically the whole match brings no joy. Stuff like this and this make more and more sense.


3. Some advice to footballers: if you're already on a yellow card, depending on the referee's interpretation of the rules to avoid a second yellow and get off with just a foul is plain dumb, so spare us the indignant looks and hangdog expressions when you're given marching orders. Oh, and stop being such pansies.


4. Maybe it's just me, but the African teams' corner flag celebrations after scoring goals are starting to look cliched and lame. Roger Milla you guys aren't.

Is it just me

... or is the new Parle LMN ad featuring the two bushmen searching for water incredibly racist?

What's with the telecom scam?

Headlines Today have been going hammer and tongs with their expose for the last two or three days, while there's not a peep from the likes of The Hindu, Deccan Chronicle, and The Times of India. Isn't a tapped telephone conversation involving a minister -- in the central government, no less -- in which he discusses portfolio allocation with a corporate lobbyist ("My case is cleared?") worthy of at least a couple of centimeters of column space?

This government has to be the sleaziest one ever, by a long mile. What with doubts being raised about our voting machines, I wouldn't be surprised if it turns out that they came to power by rigging the EVMs. Having somebody like Manmohan Singh at the helm only makes it worse.

Are we alone?

Stephen Hawking has recently weighed in on the question of whether we are alone in the universe. His logic is that there are a hundred billion galaxies, each containing hundreds of millions of stars, so it's unlikely that Earth is the only planet where life originated. Sounds plausible, but here's a counter-argument: suppose a phenomenon occurs once in 10^100 times. We know that there are 10^20 samples, which is a large enough number, and erroneously conclude that it is large enough for the phenomenon to occur more than once. The moot point here is the actual probability of the event, i.e., the 10^100 figure -- there's no reliable and/or scientific way to validate this.

Just throw the bums out

When the President of the United States cannot stay in office for more than two terms, there's no justification for these people to cling to their chairs.

Indian EVMs vulnerable to fraud

Well, all the folks patting themselves on their backs have some explaining to do. From a University of Michigan study:

Electronic voting machines in India, the world's largest democracy, are vulnerable to fraud, according to a collaborative study involving a University of Michigan computer scientist.

Even brief access to the paperless machines could allow criminals to alter election results, the seven-month investigation reveals.

Must read for Farmville affcionados

Well, 'afficionado' doesn't really reflect my opinion of those who play this game, but anyway, this article is a must read. A choice passage:

My mother began playing Farmville last fall, because her friend asked her to join and become her in-game neighbor. In Farmville, neighbors send you gifts, help tend your farm, post bonuses to their Facebook pages, and allow you to earn larger plots of land. Without at least eight in-game neighbors, in fact, it is almost impossible to advance in Farmville without spending real money. This frustrating reality led my mother—who was now obligated to play because of her friend—to convince my father, two of her sisters, my fiancée and (much to my dismay) myself to join Farmville. Soon, we were all scheduling our days around harvesting, sending each other gifts of trees and elephants, and posting ribbons on our Facebook walls. And we were convincing our own friends to join Farmville, too. Good times.

Another worthwhile quote, this from an RI forum post:

Here are some recent FB updates from my circle of friends:

"Big Ben to the Raiders? I think you need a little more than just a sexual harrassment claim for your steet cred before acceptance here, beyotch."

"So the President just gave an intro to American Idol where he said to the contestants: "You're all my dogs!". 2010 rules sometimes."

"Farmville neighbors - I need 3 eggs, 1 blanket, and 5 bottles. Thank you very much."

Bliss really is unaware...

Enough said.

Thoughts on the IPL Controversy

On one level, it's easy to dismiss the whole thing as a falling out between thieves and say no more, but certain facts stand out:

1. Not giving Modi the requested five days or so to prepare his response is very fishy. After all, the guy has busted his hump organizing a glitch-free tournament (here's a thought: with the preparations for the Commonwealth Games going as well as they are, asking him to have a look at things -- only for the logistics, not financial -- would work wonders), and denying him this time smacks of vendetta. All the more so when you regularly see the respondents of a show-cause notice given a whole month to, well, respond to allegations against them.


2. Sashi Tharoor did nothing that his colleagues (both in the ruling party and the opposition) don't indulge in on a daily basis; he only had the misfortune to get caught. The sheer hypocrisy of other politicians in baying for his blood is disgusting. Not holding a brief for him, but one needs to be fair.


3. If everybody claims to be in favour of transparency, why would Modi releasing the details of the ownership patterns of the teams (which, BTW, is already out in the open, so I don't know what is hidden here) "complicate matters" and should not be done in haste? Which leads me to my next point.
   


4. A fundamental issue is the transparency with respect to property rights. In India, it's practically impossible to figure out who owns what. It's not like in the States, for example, where any citizen can walk into the local administration's office and find out that the corner store is owned by so and so. Try doing this in India, and you'll be paid an unwelcome visit by unsavoury characters in the middle of the night. In fact, I'm not even sure this is legally possible here.


5. Why the fsck don't we ban all transactions originating from entities registered in places like Mauritius? It's a given that these are nothing but fronts for corrupt scumbags. I know, the stock market will lose something like 50% of its value if we do this, but screw it -- rooting out corruption is more important.


6. To think that all this is came out in the open because of a single intemperate 140-character web post is to dwell upon the delicious strokes of fate that the universe engineers for us mortals from time to time, irrespective of whether we are clueless celebrities addicted to Twitter or one of the 200,000 followers of these celebrities looking on with awe and wonder. Almost makes me believe in the Big Bang Theory.
   

Quote of the day

In baseball terms, the Contagion Team is at bat. Portugal is in the batter's box and Spain is on deck. Greece is on second base in scoring position. The EU is on the mound lobbing softballs while the IMF is in the bullpen warming up. Germany plays for team EU but refused to dress for the game.
-- Mish Shedlock

Obligatory IPL Post

1. The level of commercial crassness has gone up (c.f. the middle-of-the-over ad intrusion). No surprises there.


2. The slipping in of sponsors' names at the drop of a hat continues to irritate -- Citi moment of success, Karbonn Kamaal Catch (or is it 'Katch'?), and the worst of them all: the fricking MRF blimp that serves no purpose other than for the camera to be aimed at it and the commentators reading from the script ("do you know that MRF makes motorcycle tires too? MRF Pace Foundation blah blah Dennis Lillee blah blah 20 years blah de blah").


3. What the hell is Mukesh Ambani's wife doing, sitting in the players' dugout with a bored yet stoic expression on her face? It's not like she's in the same boat as Preity Zinta, with a need to grab whatever chance she gets to be in the limelight -- she's got enough money to take out full page ads for a year with her portrait on them, for heaven's sake.


4. Testing the patience of the viewers eager to know the third umpires' decision by delaying the result with animations of flying jets is not a Good Thing. In fact, empirical studies have shown that such practices may result in an 8% drop in airline passenger revenues. To be fair, the Kingfisher ad featuring the singing players is almost as good as the zoozoos.


5. What's up with Indian spectators? All you have to do is train a camera on them, and they faithfully prove Darwin's theory over and over again.
   

One-line question; 8000-page reply

From The Hindu:

It was quite literally a bundle of a reply that left its recipient flummoxed. Choudhary Rakesh Singh Chaturvedi, Deputy Leader of the Congress Legislature Party in Madhya Pradesh, received a reply running into 8,000 to 10,000 pages to a one-line question he had asked in the State Assembly. The bundles of paper were sent to his home through an autorickshaw.

Mr. Chaturvedi called it a “cruel joke.”

“During the monsoon session on July 7, I had asked a question to which the State Housing and Environment Ministry last week sent me a reply in the form of number of huge bundles,” he said. The reply came early this month.

Mr. Chaturvedi said he had asked Housing and Environment Minister Jayant Malaiyya to state the names of industrial units which were issued No Objection Certificates from January 2006 to December 2008 regarding permissible emission limits.

“I was astonished when eight to 10 bundles containing the answer were delivered at my residence,” he said

Technology provides a way to deal with such intransigent babus: ask them for the documents in soft copy, host the entire thing in a server, and let the crowds pick them apart. Oh, and by the way, ten years' hard labour for any bureaucrat exposed because of this scrutiny (twenty years for the smartypants who came up with the 'let's send them an autorickshaw full of documents' idea).

The world's first green legislature building

Instead of shouting from the rooftops about the world's first green legislature building -- a singularly worthless distinction -- how about spending similar effort on taking care of the people's problems for a change? Making sure that commuters are not put to hardship because Mount Road was shut down for three fricking hours so that the Security Liabilities can whiz by in their cavalcades would be a good start.

Let it go

To all the people bemoaning the step-motherly treatment being meted out to hockey and writing letters to newspaper editors in anguish: let it go. Face it, hockey's heydays are over; people have voted with their feet and wallets, and the -- ahem -- national game lost its deposit. The best thing to do would be to strip the game of this meaningless title and allow it to claim its rightful place, which I surmise would be somewhere between kabaddi and kho-kho.

The reasons for hockey's demise are quite obvious: the resources needed to play this game are beyond the grasp of most people (as opposed to cricket, where all you need is a rubber ball, a plank of the right size, and some chalk to draw the stumps on a gully wall). Also, maybe it's just me, but watching a hockey game is pretty much an exercise in frustration: compared to a football game, there is very little scope for a good rhythm or flow to build up -- the referee's whistle blows with a much higher frequency than football ("Did the ball touch your feet? Sorry. Oh, did you touch the ball with the wrong side of your stick? Oops." You get the picture).

Ahem

About the tracks displayed on the right: no, I haven't branched out to the nursery rhymes genre -- it's my daughter's Amarok playlist.

Talk about a stupid idea

An advocacy group is bringing out a zero rupee note that is meant to shame those who demand bribes:

Vijay Anand, from the lobby group 5th Pillar, says they began distributing the worthless note because of a lack of practical solutions for tackling corruption.

"The topic of corruption have never been on the surface," he said.

"Everybody was practising it, paying bribes, getting their jobs done. We thought that the fundamental reason was there was lack of alternatives - there was no practical solutions, no alternatives.

"So we thought we should come up with something. One of our volunteers came up with the idea of the zero-rupee note and we then launched it on a wide scale."

The note, similar to a real 50-rupee note, carries 5th Pillar's email address and phone number.

You may have the occasional success with such a gimmick, but if you think this is going to do anything significant to tackle corruption in our country, you've got another think coming. The odds are better than even that a government employee, on seeing the note, would get incensed, and either a) increase his 'price' or b) make things so miserable for the note profferer ("I'm sorry, but is that your signature? Doesn't look so to me. Can you get a notarized affidavit in triplicate that says this is really your signature?" -- alright, I was kidding, a government employee would never say "I'm sorry") that he wishes he'd never heard of the note.

Any plan that exposes the public before they get their job done and get the hell out of the government office is doomed to fail, given the extent of the corruption in our country.

American Divided Family

A letter to Mish Shedlock, through his blog:

My Dad, now 88 years old, sold out of everything, bonds, mutual funds and even his house a few years ago, right before the crash and has kept it all in laddered CDs. Thank-you for helping to inform our decision there, it helped preserve $150k or more.

Interest payments covered most of his expenses while he was getting 4-5%, but that isn’t happening now and, at 88, he certainly is in no position to go chasing yield elsewhere.

We have hit on what we think is a good alternative. I have seven years left on my mortgage at 6%. Better he should get it than Midland Mortgage Co. so Dad will soon be my new mortgage holder. He gets a monthly check, I get a little break on the rate (5%) and we keep the money in the family.

Can you imagine something like this happening in India? Let me count the number of reasons why not:

1. An 88 year old person managing his finances independently


2. Said 88 year old person also living independently


3. The person loaning money at interest to his own son

Can you say ADF?

The end is the beginning is the end

I think I've used this title already, but here goes, anyway.

I have not been affected by the demise of Worldspace India -- the prime reason being that I had stopped listening to it for nearly three years (can't really fathom what triggered this, hint, hint).

But can't say this of my wife, who, incidentally, is the creator of an advocacy group in Facebook to keep the music alive.

When Worldspace came on the scene in 2000 (or was it 2001?), it filled a big void for me: having gotten used to a staple diet of music from K-Rock (No, not the 'World Famous' one from LA; this is from New York) during my time in the States, I was making do with streaming radio on the Net with a lousy dialup connection after my return. Worldspace was therefore something of a godsend for me (trivia: "Machinehead" by Bush was the first song I heard on WS).

I checked whether K-Rock was streaming online now (they weren't circa 1997), and sure enough, they do. Ergo the title of this post.

Speaking of three idiots

... here's what I think actually happened vis-a-vis the three escaped terrorists, take your pick:

1. They were finished off in an encounter to do away with the inconvenience of a trial (Update: Turns out they had already finished serving their sentences. Why couldn't they then be simply deported to Pakistan?).


2. They escaped from some other place, and the guilty parties are trying to shift the blame.


3. Secret deal with Pakistan to release these persons in exchange for undisclosed favours (alright, this sounds too far-fetched)

I think the universe just winked at me

Call it karma, call it tricksterism, what the heck, maybe it's just a stupid publicity stunt for the movie, but aren't Aamir Khan, Vidhu Vinod Chopra and Chetan Bhagat the three idiots?

Pay attention to the other hand

At first glance, the central government's raking up of the Telengana issue seems to be an act of monumental stupidity: what was the need for the resolution, when a simple face-saving promise to set up a commission to study the issue in detail (and bury it quietly) would have sufficed? Three things:

1. Food prices are up by about 20%


2. Uncomfortable questions are being raised about how the intelligence agencies have dropped the ball on the David Headley affair


3. The 123 nuclear deal is close to fruition, with the government, going by past form, likely to give the American negotiators what they want.

Can you say 'diversion'?

Are you kidding me?

Xymphora, referring to the Climategate emails:

You really have to be illiterate, retarded, or paid off by Exxon to see even the slightest evidence in any of the emails of the slightest wrongdoing.

I'm not illiterate or retarded, and last time I checked, there sure weren't any credits to my bank account from Exxon. Yet, considering just one fact -- the attempted circumventing of the FOI regulations by the scientists, yes, you bet your ass I see evidence of wrongdoing. Why is so much hatred and venom being heaped on anyone who is skeptical about man-made climate change?

The CRU Data Leak

I began to have doubts about the whole global warming *ahem* climate change thing since becoming exposed to the arguments on the other side, but what has tilted the scales firmly is the recent exposure of the internal CRU emails. No, not the contents of the emails themselves -- damaging as they are -- but the deafening silence from the mainstream media about this. Hopefully they're waiting for confirmation that the contents are not fake (which, by the way, is already available).

Update: Call me paranoid, but it looks like the Star Tribune story on this has been taken down. Google cache to the rescue. The doofuses forgot to take down the comments page for the story, however.

When play becomes work

I like work; it fascinates me. I can sit and look at it for hours.
-- Jerome K Jeorome

We've all heard of situations (and have probably even experienced them ourselves) where someone liked their work so much that it was almost like play. Well, the reverse happened to me recently: I was working on my entry for the Intel Threading Challenge, and I was nearing the contest deadline, with my entry still missing the key bits of the algorithm. I was almost at the point where I thought I'd put in as much time as it took -- even if it meant staying up half the night -- and finish the damn thing, when it suddenly hit me: I'm supposed to be enjoying this; I'm working on this in my spare time, after all. I switched off the computer, and next morning, well past the deadline, when I thought I'd experience a pang of guilt at missing the submission, all I experienced was the thought of hacking together the code at my own pace, enjoying myself, and well, having fun.

Rukhsana appointed special police officer

I think this is an acid test -- how well we're able to protect Rukhsana and her family from the militants' vengeance will have a significant impact on the efforts to contain the militancy. Here's a thought (armchair punditry notwithstanding): provide her and her family with Z category security right in her home, instead of hauling her off to Delhi. If we're short of personnel, we can always pull them from our dear netas' entourages -- the cost of this protection is well worth the message this sends.

Jail term for thowing footwear

I think we just lost the right to condemn the treatment meted out to Muntadhar al-Zeidi.

Here's a thought experiment

From an article about Iceland's huge debt to Britain and the Netherlands and how it's trying to wriggle out of it:

Icelanders for their part feel that the EU has treated them as a financial colony while backing a neoliberal kleptocracy preying on an increasingly indebted population. In many ways Iceland is the tip of the iceberg – the proverbial canary in the coal mine showing the need to better cope with over-indebted economies. The EU and IMF-style austerity programs to pay off foreign debts that corrupt insiders have run up is not what was promised in 1991 (to) the post-Soviet economies or Third World debtors. It is not the promise of industrial capitalism. It is a financialized post-industrial dystopia, an imperial neofeudalism.

...

 Instead of imposing the kind of austerity programs that devastated Third World countries from the 1970s to the 1990s and led them to avoid the IMF like a plague, the Althing is changing the rules of the financial system. It is subordinating Iceland’s reimbursement of Britain and Holland to the ability of Iceland’s economy to pay

Do you think any of the Third World debtors would have gotten away with it if they had tried to pull the same stunt as Iceland? Any talk about how their "position as a sovereign state precludes legal process against their assets which are necessary for them to discharge in an acceptable manner their functions as a sovereign state" would only have elicited a "Nice try, just STFU and cough up the money". However, I'm sure the fact that they are not denizens of the civilized white western world would not have had anything to do with such a response. Not.

For a second there I thought you said '14 lakhs'

From The Hindu:

Mohandas Karamchand Gandhi’s iconic Dandi March in 1930 to protest against the British salt tax has inspired pen-makers Mont Blanc to come out with a limited-series pen on the Father of the Nation.

The high-end pen is priced around Rs.14 lakh, according to a watch retailer.

The pen comes with a gold wire entwined by hand around the middle, which "evokes the roughly wound yarn on the spindle with which Gandhi spun everyday."

You can't make stuff up like this even if you tried: using somebody whose life was the epitome of simplicity to sell a fricking designer pen that costs Rs. 14 lakh.

There's a bright side to this, though: all we have to do is hook up some magnets and coils of copper wire to Gandhi's mortal remains in Raj Ghat, and voila, an instant solution to our perennial power shortages.

Somebody please take the keyboard away from him

At this rate, he's not going to last long in politics. I think it's time the writer in him is locked up in a closet, at least as long as he's a minister. Here's an idea: whenever the urge to tweet seems to become overwhelming, summon one of your minions in the ministry and bawl him out -- this will have the added benefit of bringing in some discipline as well.

By the way, studies have shown that cutting down your twittering by even as little as five tweets a day can allow one to fit in an average of 1.2 extra engagements in an already 'ridiculously full' day.

Question

If The Lost Symbol is so hot, why am I being spammed with so many emails offering the book at big discounts, including exclusive offers from my credit card company (yeah, exclusive as in "only for our two million cardholders")?

Indiaplaza even went so far as to send an email masquerading as a review of the book, with the reviewer practically wetting themselves in their praise. Wait, I think I was too harsh -- reading the review more closely, it looks like a really different plot this time: last time it was a French scholar who requests a meeting with Langdon and dies before the meeting could take place, leaving behind a tantalizing clue, while this time it's an American professor who pulls more or less the same shit. My bad.

Update:The Onion chips in:

Most chillingly, many agreed, is that while Michael Crichton's death has been a positive step, Dan Brown remains very much alive.

World Bank approves $4.3 billions in loan to India

Nothing particularly significant in this, except what a portion of the loan is meant for: to shore up the capital of some of the state-run banks. Two questions: 1) What is the need for a loan from the World Bank for this insignificant -- relatively speaking -- amount when we have something like $258 billion dollars of foreign exchange reserves? 2) Do these loans come attached with any conditions related to deregulation or 'financial innovation' that these banks must agree to?

The hydrogen bomb controversy

Today's Hindu carries an article about the controversy generated by Santhanam, in which M K Narayanan defends the government's position about the success of the thermonuclear test. Unfortunately, nearly all the points are pretty much untenable (unless he said something more, and it was not published). Samples:

The thermonuclear device had a yield of 45 kilotons. I have chosen my words carefully — 45 kilotons and nobody, including Mr. Santhanam who has absolutely no idea what he is talking about, can contest what is proven fact by the data which is there

I find it hard to believe that the DRDO project lead in charge of the whole thing (i.e. Santhanam) doesn't have a clue what he's talking about.

Asked about the doubt the former Army Chief, V.P. Malik, had raised about the efficacy of the hydrogen bomb, he said: “I think the person to answer that, is the present chief and not the past chief…”

Just because someone has retired from his post, he doesn't lose whatever credentials he may have built up over his career. Reading along:

“We have thermonuclear capabilities. I am absolutely sure. We are very clear on this point. If you hit a city with one of these you are talking about 50,000 to 1,00,000 deaths,” the NSA said.

Just saying so repeatedly will not cut it. Also, does anybody else find such casual mention of deaths more horrifying than Santhanam's statements?

One can understand where Narayanan is coming from: after all, proclaiming to the whole world that our hydrogen bombs are duds is not exactly good for the morale of the country and would cause our enemies quite a lot of satisfaction, but going after those who are interested in the truth doesn't serve any purpose, either.

Haskell, monads, graph theory and the puzzle that took 19 years to solve

Well, 'solve' is actually a misnomer, since it turns out that the puzzle doesn't have a solution (at least that's what my code tells me). Here's the puzzle:

Given the figure below, find a path from point A to point B that crosses every edge line segment exactly once:

I came upon this when I was in college, and spent an hour or so on it, trying out different paths by hand, but could not find a solution.

Nineteen years later, The Communications of the ACM carries an article on the P=NP question, which triggers an impulse in me to read up more on the complexity of algorithms, and I learn about graph theory, DFS, BFS, the entire works. Quite a fascinating subject. Anyway, the upshot of all this is that I realize that there is a formal method of solving the puzzle that had piqued my curiosity nearly two decades ago.

Coincidentally, my copy of Real World Haskell arrives at my doorstep at around the same time I am thinking of whipping up some code to solve the puzzle. Learn Haskell, solve puzzle. One stone, two birds.

The first thing is to come up with the data structures. Not too difficult (apologies for the screwed up formatting -- getting all the tabs correct in Blogger would probably take me four hours):

type Node = Int
type Edge = (Node, Node)
type Path = [Node]
type Graph = ([Node],[Edge])

theGraph :: Graph
theGraph = ([1,2,3,4,5,6], [(1,2),(1,3),(1,4),(1,2),
(2,3),(3,4),(1,4),(2,5),
(3,5),(3,6),(4,6),(1,5),
(5,6),(1,6),(1,5),(1,6)])

One of the options I considered initially was to model the direction of the path, something along the lines of

type Path = [(Edge,Direction)]

with Direction indicating whether we are going forward or backward, but it turns out that this was not required.

Having gotten the data structures in place, it's just a question of routine code to put together the helper functions that will be needed:

-- to check whether two edges are the same [(1,2) is equal to (2,1)]
edgeEq :: Edge -> Edge -> Bool
edgeEq e1 e2 = e11 == e21 && e12 == e22 ||
e11 == e22 && e12 == e21
where e11 = fst e1
e12 = snd e1
e21 = fst e2
e22 = snd e2

-- get all the edges joined at a node
getEdges :: Node -> [Edge]
getEdges node = [edge | edge <- snd theGraph, fst edge == node || snd edge == node]

-- get the node at the other end of an edge
getOtherEnd :: Node -> Edge ->Node
getOtherEnd node edge = if fst edge == node then snd edge else fst edge

-- get all the neighbours for a node
getNeighbours :: Node -> [Node]
getNeighbours node = map (getOtherEnd node) (getEdges node)

-- converts a path into a list of edges (e.g. [1,2,3,2] to [(1,2),(2,3),(3,2)]
buildEdges :: Path -> [Edge]
buildEdges path | null path || length path == 1 = []
| otherwise = (head path, head (tail path)) : buildEdges (tail path)

-- get the list of neighbouring nodes that are yet to be visited in the current path
getUnvisitedNeighbours :: Node -> Path -> [Node]
getUnvisitedNeighbours node path = map (getOtherEnd node) untravelledEdges
where untravelledEdges = deleteFirstsBy edgeEq (getEdges node) (buildEdges path)

-- check whether a given path is a solution
isSolution :: Path -> Bool
isSolution path = head path == 5 && last path == 6 && length path == length (snd theGraph) + 1

The astute reader will observe that the graph object -- is it OK to call things 'objects' in Haskell? -- is baked into the solution; I initially had a version where the graph object was passed as a parameter to every function, but this made things more verbose, and anyway, my objective was not to produce a graph library, but to solve the puzzle.

With that out of the way, time to move on to the actual algorithm. The algorithm is a DFS brute search, where we start at a node (note that the area outside the figure is also modelled as a node), choose one of its unvisited neighbours, choose one of the neighbour's unvisited neighbours, and so on, till we run out of neighbours to visit. Check the path to see if we have covered all the edges and if the path is bookended by the start and end nodes that are of interest to us, and we have our solution. An NP-hard problem, BTW.

It's obvious that recursion is needed here, but I was not sure how to handle the enumeration of the different branches, the backtracking from a dead end, and so on in Haskell, considering that looping is frowned upon, and the strongly typed nature of the language implies that both the if and else clauses should return the same type, i.e. you cannot do the equivalent of:

if <path is a solution>
then <print solution>
else <add next neighbour and try again>

While working on the solution, I was also reading up on monads, and man, are they a pain to wrap your head around. But luckily I ran into [*] Monads as containers (and its sibling Monads as computation, which I'm still digesting), where I learned that a list is also a monad, and we can do stuff like take a list, apply a function that produces a list, and end up with a flat list, so to speak (yeah, we don't need monads for this, a simple map and concat are enough, but I learned this in hindsight, after realizing that >>= was exactly what I was looking for). Anyway, that sort of nails the algorithm:

-- build a list of candidate paths for a given path
getNextChoices :: Path -> [Path]
getNextChoices path = nub (unvisitedNodes >>= (\x -> [reverse (x : reverse path)])) -- hack to append to end of a list
where unvisitedNodes = getUnvisitedNeighbours (last path) path

-- filter out all the solutions from a given list of candidate paths
findSolutions :: [Path] -> [Path]
findSolutions paths = filter isSolution (nub paths)

-- find all the solutions starting from a given list of candidate paths.
-- invoked with a single node path, i.e. solve [[1]]
solve :: [Path] -> [Path]
solve paths = if null choices
then findSolutions paths
else solve choices
where choices = (paths >>= getNextChoices)

solve' :: [Path]
solve' = solve [[5]]

From All About Monads:

One use of functions which return lists is to represent ambiguous computations -- that is computations which may have 0, 1, or more allowed outcomes. In a computation composed from ambiguous subcomputations, the ambiguity may compound, or it may eventually resolve into a single allowed outcome or no allowed outcome at all. During this process, the set of possible computational states is represented as a list. The List monad thus embodies a strategy for performing simultaneous computations along all allowed paths of an ambiguous computation.

The above algorithm is not exactly an ambiguous computation, but the bit about "performing simultaneous computations along all allowed paths" sure resonates with its structure.

And now for the denouement, which by the way, takes a looong time (remember the NP-hardness):

*Main> solve'
[]

Nope, still no solution.

[*] It doesn't reflect too well on a book if I still have to rely on Google to help me out. I'm looking at you, "Real World Haskell".

Thank you

Here's an example of what's wrong with our country:



Salsa-dancing, shopping-at-Marks-and-Spencers investment bankers -- yeah, this is the most representative Indian demographic.

And using Phil Collins' Another Day in Paradise as the investment banker's favourite song? These guys won't know it if irony jumped up and bit them on their asses.

Thought for the day

A helpful analogy to understand the value of static typing is to look at it as putting pieces into a jigsaw puzzle. In Haskell, if a piece has the wrong shape, it simply won't fit. In a dynamically typed language, all the pieces are 1x1 squares and always fit, so you have to constantly examine the resulting picture and check (through testing) whether it's correct.
-- From Real World Haskell

Little things

Firefox: Allow one the option of saving the password for a web site after the site has received the password and has indicated successful authentication.

IE: Prompt for saving the password before sending the request, which may result in storing an incorrect password (because of a typo).

Is it just me

... or does this image remind one of -- never mind.



(yeah, that's right, guy #1, move your left hand towards guy #3, just a little higher... perfect! Hold it right there. Guy #3, take your left hand, and...)

Exports to touch same level as last year?

... according to this story. Quite unlikely, considering the quite steep year-on-year dips in the export figures for the initial months of the year.

Bloggots

Dear Farrukh Dhondy,

I have been a regular reader of your columns in The Deccan Chronicle, and have always enjoyed your wit and intelligent insights. However, you have outdone yourself today:

Neither is there much evidence in favour of the bloggots (blogging idiots) who contend that Afghanistan is strategically important because someone somewhere wants to lay a pipeline through it to send petrol or gas to someone else and earn zillions of dollars thereby. Look at a contour map of Afghanistan (and get a life)!

Bloggots. Take two unrelated words, 'blogging' and 'idiots', conflate them together, thereby forming a new word that was simply begging to be coined, a word that succinctly captures the misplaced contempt that professional columnists (aka people who have a life as compared to us poor bloggots) have for folks who are doing an end run around them, and that too for free, and voila, there's your winner for the next year's competition.

Sincerely yours,

Bloggot #76981

P.S. About the whole Afghanistan thing: I suggest you Google for these terms: "grand chessboard", "Melvin Lattimore" and "Ali Mohammed". Spending some time at History Commons and the RI Data Dump won't hurt, either.

P.P.S. And I have been wondering about this for a long time: who the $%@& is Bachchoo?

Pension funds

Here's an example (via Mish Shedlock) of the dangers we would be exposing ourselves to if we allowed our pension funds to be invested in -- ahem -- "non-moribund investment patterns":

As of March 31, Calpers's $17.6 billion real-estate portfolio, a majority of which is invested in commercial properties while about 5% is invested in residential, reported a one-year decline of about 35% in its value.

I'd take a measly inflation-adjusted single digit return any day, thank you very much.

India aims for robust GDP growth despite drought

The Commerce Minister has opined that we can maintain our GDP growth in the current year at the same level as the previous one. Good to know that; the only problem is that the entire article contains not a single factual argument that supports his statement. Things like

"Our domestic demand and consumption is strong. Fundamentally, our economy is strong"

and

"India keeps substantial buffer stocks of food grains after our two successive years of buffer [Ed: I think he meant 'bumper'] crops. We have enough of what we have to sustain availability of food"

and

"We are not overlooking the challenges that we have. At the same time, we are not overwhelmed by them...we hope that this situation will not be there when the next sowing season comes in January"

are not exactly confidence-inspiring, absent any convincing arguments.

I came across this piece immediately after reading an investment advisory about the impact of the drought on the economy -- the detailed analysis it contains shows up the hollowness of these statements even more starkly.

Adieu to social networking

Last week I deleted my Facebook and Orkut profiles, for reasons I've mentioned elsewhere. I am going to delete my Twitter and LinkedIn accounts as well, but haven't gotten around to it yet. Maybe I'll spare LinkedIn, but Twitter has to go -- no two ways about it.

Thank you

Someone finally calls out on this pretentiousness:


This goes not just for tweeting twats, but also for blog commenters.

You give research a bad name - Part 2

From Yahoo:

A new piece of research suggests that what an organization promises to employees-training opportunities, benefits, compensation, etc.-do not matter nearly as much as what the organization actually delivers.

Samantha Montes and co-author David Zweig, professors at the Rotman School of Management and the University of Toronto Scarborough, have found that the influence of promises has little effect on employee's emotional reactions toward the organization, their intentions to stay with the organization, and intentions to engage in citizenship behaviours.

In their study paper, the authors write that people care more about what they receive from their organization, not what they were promised.

Gee, who would've thunk that?

Operators are standing by as we speak

Yeah, that's exactly what the world needs more of right now: a gold-plated guest house complex, when millions are suffering from disease, malnutrition and other crises.

Here's an idea

Abdul Kalam's supposed humiliation at the hands of the Continental Airlines security staff has kicked off a much needed debate on the privileges our so called VIPs enjoy. Here's an idea: instead of referring to these folks as VIPs, why not start calling them SLs (short for Security Liability)? This would a) take away the sheen associated with the original tag and b) lower the cost to the exchequer (the assumption being that the politicos would be shamed into requesting that they do not want to be provided security, owing to the negative connotation of the new tag).

The Rajapaksa interview

The Hindu is carrying an interview with the Sri Lankan president. Most of his answers are politically correct and are what we want to hear -- man, he's one smooth operator, alright -- but this one exposes his true colours:

Q: There has been international concern over the assaults and pressures on journalists in Sri Lanka. Some of these journalists were your personal friends, especially Lasantha Wickrematunge [Editor of The Sunday Leader] who was gunned down in January 2009. Then, in June, a Tamil woman journalist [Krishni Ifhan née Kandasamy of Internews] was abducted in Colombo by unidentified persons [who questioned her for several hours before releasing her in Kandy].

A: Most of these cases were created, I would say. If you fight someone in the street and that man comes and hits you, can the government take responsibility? But we have not done anything against journalists even when they attack us.

Nice dodge.

BTW, in case you haven't done so already, go and read 'And then they came for me', Lasantha Wickrematunge's voice from beyond the grave -- without doubt the most poignant thing I've read in a long while.

Eight queens problem in Lisp

(defun solve-n-queens (n)
  (let ((solutions nil))
    (defun solve-internal (board k)
      (if (eq k (- n 1))
        (dolist (x1 (solve board k))
          (push x1 solutions))
        (dolist (x2 (solve board k))
          (solve-internal x2 (+ k 1)))))
    (solve-internal (make-board n) 0)
    solutions))

(defun solve (board k)
  (let ((solutions nil))
    (dotimes (i (length board))
      (if (present? i k (get-safe-squares board))
          (push (place-queen (clone-board board) (list i k)) solutions)))
    solutions))

Helper procedures left as an exercise for the gentle reader.

Pop Quiz

Which of these two news items is from The Onion?

*This* is how you do it

Their names differ just by one letter, but their career paths can't be more divergent. While one is an over-hyped and pampered underachiever whose claim to fame owes more to her tight T-shirts and short skirts, the other has been quietly flying under the radar, establishing a name for herself on the world stage.

Judicial overreach

From The Hindu:

The Supreme Court on Monday directed the Centre to file an affidavit by June 26 on the steps taken to ensure the safety and security of Indian students under racial attacks in Australia and Canada.

It's nice that there's somebody to pull the government up for its non-performance, but is this the job of the judiciary? Last time I checked, their role was to interpret the law and the constitution, nothing more.

Harish Khare appointed PM's media advisor

Looks like all the years of slanted op-eds supporting the Congress party have finally paid off.

Subramaniam Swamy on EVMs

There is an op-ed by Subramaniam Swamy on EVMs in today's Hindu . He raises a lot of pertinent points, one of which is quite damning (italics mine):

For example, the respected International Electrical & Electronics Engineering Journal (IEEE, May 2009, p.23) has published an article by two eminent professors of computer science, titled “Trustworthy Voting.” They conclude that although electronic voting machines do offer a myriad of benefits, these cannot be reaped unless nine suggested safeguards are put in place for protecting the integrity of the outcome. None of these nine safeguards, however, is in place in Indian EVMs.

I googled for this article, to confirm whether there was any merit to his allegation, but the article is behind a pay wall. Another interesting point he raises is the employment of convicted hackers by a political party just before the elections (no prizes for guessing which party):

On the eve of the 2009 elections in India, I raised the issue at a press conference in Chennai, pointing out that a political party just before the elections had recruited those who had been convicted in the U.S. for hacking bank accounts on the Internet and credit cards.

If these allegations are true, my already low level of confidence in these machines just went down another notch.

Update (May 6, 2010): Vindication from a University of Michigan study.

A fool and his money ...

Today I shelled out $5 to buy the PDF version of the Blue Book when I could have had it for free. And to think that the money could have been put to better use, like helping out Arthur Silber, for example, makes it all the more painful. Grrr.

Here's a business opportunity

From an article in the latest issue of the Communications of the ACM that analyses the reasons for the limited success of the OLPC:

... if the machine fails, it is up to the family to replace it or the child must do without.

Time for someone to step in with an insurance policy, methinks.

Tin foil hat time

Considering that Tech Mahindra is facing difficulties in dealing with the spurt in the share price of Satyam, this statement by the Satyam chairman seems suspiciously like an attempt to drive down the price to levels comparable to the open offer price. I dare say anybody in his right mind would deliberately talk down a company this way otherwise:

"It is hugely overstaffed, costs are very high, and the revenue picture in the immediate future is not that great."

General Motors or Chevrolet?

General Motors have taken a full page ad in the newspapers to convince the world that their Indian operations are going strong, no reason to doubt their solvency, yada yada. If you look at the ad, you will find exactly one mention of 'General Motors': the line below the CEO's name and designation (well, two if you count the GM logo in a picture of one of their factories). It's 'Chevrolet' everywhere else: it's almost like they want to dissociate themselves from the G-word -- which is sort of schizophrenic, considering the intent of the ad.