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...)