On the way to Skeyer…

Recently I’ve had some free time on my hands , So I’ve started looking at writing a Maliit plugin for a gesture based keyboard.. I spent the last weekend coming up with a basic Demo of such a keyboard in Qt/QML … Apparently it’s really not that difficult.

This was really a quick and dirty project to test the waters and I’d say i’m pleasantly surprised how easy and how performant this was. Even on my 5 year old Samsung Galaxy Captivate( 1Ghz processor, 370MB RAM), there was absolutely no visible lag in predicting ~5 words from a dictionary of around 30000 words.

And here is the demo of what’s working so far:

What works:

1) A basic disambiguation algorithm, which says how likely “hgfdedfghjklo” is to be the word “Hello”.  At it’s core, this is a modified Levenshtein Distance algorithm.

2) A basic prediction function which ranks words like “Hello” “He” “Hell” … in the increasing likelihood that they generally  appear. ( Currently I’m using a basic Unigram generated from http://norvig.com/big.txt – written for his spell checker )

3) All the necessary infrastructure to parse keyboard definition files and create a virtual keyboard. ( I am designing this with multiple languages/keyboard layouts in mind )


1) Improve the word disambiguation algorithm and the feedback system. (quite interesting, probably – priority 1)

2) Improve the prediction precision by analyzing more real world text and analyzing user’s error model – priority 3)

3) Add a gesture to support inputting repeating characters. (priority 2)

4) Implement a proper state machine in engine to support things like backspace, arrow keys, auto capitalization etc.. (priority 1)

5) Make a Maliit plugin out of it. (priority 2 – mainly because it seems like it would be faster to develop and test the demo than the whole Maliit plugin)

6) Look into multi language support. (priority 5 – kind of too much for me)

7) Make it prettier (priority 4)

I’m hoping to make this FOSS… But I haven’t yet decided if I would want to put a price on this => the code stays behind closed doors for now. So if you don’t hear any updates from from me about this in 1-2 months from now (I’m only working on this during weekends, and spare time as of now…), feel free to ping me and I’ll open up the source code immediately.

Thanks to :

1) norvig.com/spell-correct.html
2) codeproject.com/Articles/36869/Fuzzy-Search
3) presage.sourceforge.net/
4) www.iconfinder.com/
5) invokeit.wordpress.com/frequency-word-lists/
6) abloz.com/huzheng/stardict-dic/dict.org/


On the way to Skeyer…

Moving on…

Since I m long overdue for this blogpost, here are a few pictures to say it all……

Thanks a ton for the Maemo Community: The Puppy File Server won this gorgeous device in the Maemo Coding Competition 2012!
Got to have a really amazing conversations with really amazing people during the 3 days of interviews for Dream Industries in Moscow! I really wish them a very good luck with dreamindustriesunderattack.tumblr.com
It was really an exciting time for Luna: Apart from numerous improvements, Thanks to Michael Holub, Aditya Bhatt, Smit Shah, The upcoming VSXu 0.4 even got some OS X love!

2012 really was an year full of amazing conversations, really interesting ideas and interestingly interesting events for me….. since i might or might not ever talk about them again……. let me simply jot them down briefly:

a) Why the current state of Mobile Advertising is done horribly wrong… – a conversation that probably became one of the major reasons i quit my previous job:

b) How do we build an ideal music recommendation service: simply(and magically) suggest all the songs a user likes – then how would the user even know if he likes/dislikes a song? Adding a sense of progress/exploration?  A sense of flow? – a conversation that only lead to more questions…

c) Talked about even more interesting things I never thought I would even think about, with even more amazing people – which finally helped me choose the path i currently am on…

But as we all know, all talk, no work makes jack a dull boy. So

I’ve joined e-GITS as a Software Engineer.
Moving on…

4 weeks of unemployement

And its that time for a bit of looking back at things…

So the first week was a bit of cycling for pleasure and meeting up old friends I ve been wanting to meet for over a year…
And the next week I made the Puppy File Server and pushed it to the Nokia Store! 😀 (Visit the project page for more details)
And the Week After that I rewrote the forgotten VSXu-Tomahawk Integration to get it ready for primetime! 😀
And then…. Experimented a little bit with meteorjs, half finished a surprise pet project with VSXu, Resurrected my good (9 year) old machine because my fav. 5 year old laptop decided to die (fried up motherboard because of overheating :/ ) and umm… thats mostly it i guess…

And Then a week of tooooooootal slacking off….. i cant even find how/where the time leaked away ………….  So i guess its time i  start looking for a job … so let me know if you know of any interesting opportunities for me 🙂

4 weeks of unemployement

An Interesting solution to a (not so) tricky problem

Once upon a time (a.k.a a couple of weeks ago)  in a far away land (a.k.a at work), We were asked to solve a problem :

We had a mapping of the number of times a user clicked on an Ad from a given ip addresses,

We also  had an initial black/white-list  of ip addresses and usernames.

We needed to use the initial blacklist(s) and whitelist(s) to assign a score (of 0 to 100) to all the remaining ip addresses and users we had – 0 being the score of a blacklisted node and  100 being that of a white-listed node.

So we had to write a program which takes the above data as input and outputs:

Phase 1: Tab-Separated output with (Username, Score) where Score is a quality score between say 0 and 100 (100 is best quality — 0 is worst)

Phase 2: Tab-Separated output with (IP, Score) where Score is a quality score between say 0 and 100 (100 is best quality — 0 is worst)

This seemed like a too trivial story. Isn’t it? It probably is, for those who have studied a bit of graph theory..  Unfortunately that’s not the case with me.. Yet, for some reason, i thought the problem to be a trivial one to solve….. until I got stuck with it for a few days.. and then i somehow came up with a nice little solution (which i really like).

So before giving my solution away.. let me first discuss the problem…

We have a white-list of usernames and ip addresses (Basically the people we trust), which more or less looks like:

*The Good IPs and Usernames*

and a black-list of usernames and ip addresses, (The people who made a lot of fradulent clicks?…),

*The Bad IPs and Usernames*

Which more or less looks like,

The Good and The Bad nodes

And then we have the mapping b/w each username and an ip address, i.e the number of clicks of a user we received from each ip address

(ip address , total clicks, total users, {username:clicks})     5     2     {"userC":3,"userD":2}     1     1     {"userE": 1}     3     2      {"userF":1,  "userG": 2}

Which looks like:

Now The other Nodes

Now what about the scores for this trivial case?

Here, Let me solve that for you….

The Answer for the trivial case

So you might ask me whats so tricky in this problem, well.. let me ask you a question first! what if we add another entry to the ip-user name map like this: 3   3       {"userF":1,  "userD": 2}

i.e what if UserF clicks once on an Ad from a different ip address( and userD clicks on the same ad twice?

The Twist in the story!

Now time to think about it…… how would you score the nodes in the graph?

Its obvious to guess that :

  1. Only nodes: {userF,,  userD} will get new scores..
  2. Since userF is indirectly related to a good node, it’s score will probably have to increase
  3. The score of userD should now decrease for a similar reason

By now you probably have realized that you will have to answer these 3 questions to go further:

  1. what should the score of the ip address be then?
  2. what should the score of userF and userD then be?
  3. how would you generalize this solution of yours for a million nodes?

So ……these are the questions that i was stuck at for a couple of days….. and it was a really tricky thing for me. And then, one fine morning (well i spent the night at office just trying to find a solution),

The EUREKA moment!!

I came up with what seemed like a really cool analogy for the problem, something from my high school days…. and without any further delay, let me present the analogy to you:

  • The Good IP Addresses and usernames can be compared to a Voltage sources of potential 100V.
  • The Bad IP Addresses and usernames can be compared to Voltage sources of potential 0V.
  • The Connection b/w 2 nodes ( in our case it is just a connection b/w IP Address and a Username) can be represented by a resistor of conductance = number of clicks(=1/Resistance).(The Greater the number of clicks the user made from the given ip address, the closer he will be to the node, hence the lower resistance and the lesser the potential difference b/w the two nodes.)
  • The “Good ness”, like current, will have to flow from the good node to the bad node.
  • Ohm’s law and Kirchoff’s Laws would apply (obviously, voltage is not leaking away at nodes or in the resistors)=> Nodal analysis on this circuit = happily ever after!! 😀

But what happens after happily ever after is that:

  1. I had to read up about the SPICE circuit solver
  2. Weed out the stray nodes (the nodes that arent directly or indirectly connected to the voltage sources) from the given input using a simple Graph traversal algorithm. (Thank YOU prof. Sebastien Thrun!)
  3. Write a little python script to convert the processed input to a SPICE circuit file.

So for a nice little  example, lets look at the circuit:

A historic battle

The spice input file for this problem:

* Circuit simulating fraud detection

Vip:: ip:: 0 DC 100
Vip:: ip:: 0 DC 0
Ruser::a~ip:: user::a ip:: 1
Ruser::a~ip:: user::a ip:: 1
Ruser::a~ip:: user::a ip:: 1

 and the (partial) spice output:
  Node                 Voltage
 ip::          5.000000e+01
 user::a              5.000000e+01
 ip::          0.000000e+00
 ip::      1.000000e+02

SO, this solution was more than interesting for me, not just because of the analogy, but because i was able to apply my knowledge of the SPICE software to solve this… and you have no idea how boring the SPICE lab sessions used to be, and this was the first time i actually dug the internet up for more tutorials for such a boring software!!!



P.S If you find any mistake in this solution, please let me know 🙂

P.P.S For some weird reason, this solution reminds me of http://myonlinescratchpad.blogspot.in/2009/02/my-calculus-assignment.html

An Interesting solution to a (not so) tricky problem

VSXu now available in the Ubuntu Software Center!!!

Yes! We finally made it to the Ubuntu Software Center!!!
Get it while it is hot!

So yes, The first thing you might notice is a 5$ price tag for an Open Source software, freely downloadable from github. And probably the proprietary License too. Before you get alarmed, let me assure you, everything about VSXu still remains the same.

Firstly,  We are only experimenting to see if people would actually pay for such a fine piece of software like VSXu. As this is just an experiment, and since we want to appreciate and thank the users who have actually paid for VSXu, we have enclosed a couple of extra visuals in this release, which are not part of the existing VSXu releases. Apart from that, i assure you everything else is the same as what you get in github.



P.S If you cannot pay for VSXu and still want the .debs for free, checkout VSXu Daily builds and VSXu Release builds .

P.P.S Also a Youtube channel with some beginner demos and documentation is on it’s way. 🙂

VSXu now available in the Ubuntu Software Center!!!

A little makefile for our Node.js project……. just to sooth the soul…

Sooo…….. when i joined Chitika…. i had no experience in writing production code in an interpreted language…. And so whenever I had to make a commit, it was a nightmare to deploy it without testing it properly…

So we immediately had to switch to test driven development model…

And the one thing i really missed after the switch was a nice “compilation step” ….. SO , here is my attempt to fix that.

: Dinesh

A little makefile for our Node.js project……. just to sooth the soul…