Wednesday, September 30, 2009

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.

Thursday, September 24, 2009

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.

Wednesday, September 23, 2009

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?

Monday, September 21, 2009

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.

Saturday, September 19, 2009

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

Sunday, September 06, 2009

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