Saturday, December 25, 2010

Suggest more recipients (in a chat conference)

If you don't already know, gmail has had a feature called Suggest more recipients for a while now.

From the link above, "Gmail will suggest people you might want to include based on the groups of people you email most often. So if you always email your mom, dad, and sister together, and you start composing a message to your mom and dad, Gmail will suggest adding your sister. Enter at least two recipients and any suggestions will show up like this."

I am planning on extending this even for the chat conversation start page in the chat client that I'm working on. So, if you start entering JIDs of people you want to chat with, the client should automatically suggest more participants.

Thanks to Sandy for the providing the link to gmail blog!!

Update (02/01/2011): This feature is now implemented and part of the dev. versions.

Thursday, December 23, 2010

Debugging PHP's $_REQUEST

The $_REQUEST page in the PHP manual, says that "$_REQUEST is an associative array that by default contains the contents of $_GET, $_POST and $_COOKIE. The variables in $_REQUEST are provided to the script via the GET, POST, and COOKIE input mechanisms and therefore could be modified by the remote user and cannot be trusted. The presence and order of variables listed in this array is defined according to the PHP variables_order configuration directive."

I was under the impression that $_REQUEST would only contain data from the $_GET and the $_POST variables. In my application, I was setting cookies that had the same key as one of the GET parameters that I was expecting. The script was hence getting data set by the cookie and not the GET parameter!! I went half mad trying to debug this and was suspecting some caching issue. Things got queerer when changing some of the GET parameters worked, but others refused to budge from their original value!! You can imagine the perplexing situation I was in. Thankfully, though it dawned on me to check the PHP manual to see what the $_REQUEST was supposed to contain and I was able to fix my code to use $_GET.

Since then, I have come across this very useful page which mentions the exact problem I had and also says why one should avoid using $_REQUEST.

Shortest Slowest path

A few weeks ago, I had was presented with a question: "You are given an n X n matrix. Each cell has a non-negative integer that denotes the cost of landing on that cell. Start from the top-left corner, compute the cost of the least-cost-path to reach the bottom-right corner of the matrix such that the sum of all costs incurred during the traversal is the least. Additionally, you are allowed to move only down or right."

Of course, this is just a slight variation of Dijkstra's Shortest Path problem, but I was surprised at the first solution that came to mind. I was trying really hard to not use Dijkstra's shortest path algorithm to solve this problem. I landed up linearizing all the n2 cells into n2 vertices in a graph and applied the Floyd-Warshall algorithm on the resulting matrix (of having side n2). Hence, the total complexity shot up to a whooping O(n6) (n being the side of the original matrix). If I had used a standard BFS or Dijkstra's algorithm, I would have been able to solve it with a runtime complexity of O(n2 log(n)).

However, this was a very interesting exercise in functional programming since I was able to piece together a solution by chaining solutions to existing problems. The composition looks something like this:
Solution(matrix) = FloydWarshall(Linearize(matrix))

Dyslexia Friendly

I made my home page Dyslexia Friendly today. Click here to find out more.