Monday, November 4, 2013

Introducing Super Secure File - One File, Completely Secure, Access Anywhere!

Super Secure File gets you a really secure password protected file that you can access anywhere with an internet connection. Smartphone, Tablet, Laptop, SmartTV, anything!

To cut to the chase and create your Super Secure File, go to: http://secure.foamsnet.com.

How does it work?

Super Secure File basically uses Google Drive to store your encrypted file and does all the encryption and decryption locally in Javascript. The key never ever leaves your computer. Once you close the tab, boom, the key is gone. Nobody knows the key but you (and probably your spouse if you are married).

Motivation

This is not a big feat or anything, this is merely a mashup of a few libraries to prove a point to myself. The motive behind this app is to build a secure mechanism to store my passwords and credit card numbers on the cloud so that I can access it anywhere. I do not trust anyone who links me up to a server when it comes to information like this. Which is why i wanted a completely static HTML page with no server access whatsoever to provide me with this functionality.

Feel free to examine the source code here (and please let me know if you find anything utterly stupid): https://github.com/vickyg3/super-secure-file

Hosting and Links

Since this is a static page, I have not hosted this on my server. This is merely hosted as a github page (if you look at the repo, you'll see the default branch to be gh-pages and not master). Hosting it as a github page also proves that it has no server interaction whatsoever and cannot steal your key by any mean.

So, all you need is to remember your password and one of these URLs (they all redirect to the same Github Page): http://bit.ly/securefile or http://bit.ly/supersecurefile or http://secure.foamsnet.com or http://vickyg3.github.io/super-secure-file/super_secure_file.html

Get your Super Secure File and make your life a little easier! :-)


-Vignesh

Wednesday, October 23, 2013

Open sourcing Social Photos

I have been working on a lot of open source projects lately (chromium, AOSP, ffmpeg, etc.) and I have had this tremendous change in the way i look at software projects now. I am all the more convinced that open source is the only right way of doing software.

With that in mind, I've made a pledge to myself that no matter what I do, I am going to put the source out there. As a first step, i'm open sourcing the one big project of mine, Social Photos.

The source can be found here: https://github.com/vickyg3/social-photos

It is a snapshot of the one that's currently powering the live site: http://socialphotos.net (with API keys redacted). Feel free to fork and use as you please. Although i'd appreciate a link back, it's not mandatory. Also, i'll be more than happy to look at Pull Requests.

One of the main reasons that developers (including myself) don't post our code out there is that we are ashamed of our code. I was really ashamed by the number of hacks i did in this project that i couldn't even think of making it public. I'm over it. I'm ready to accept people fixing my mistakes.

Happy Coding!



-Vignesh

Tuesday, October 8, 2013

Why do we always have to f*** the opponents?

Note: This article is related to soccer (and other American sports).

I have always been a football (soccer) fan. In fact, i refuse to call it soccer, but for the sake of convenience, I am going to mention it as soccer the whole of this post.



I have been going to a lot of games lately (soccer, football as well as baseball). One common behavior I see across all these sports is that, the home fans always have an attitude that the opponents suck and we gotta f*** them. There are loads of banners, tifos, chants, etc. which are particularly targeted against the opponent players. Usually, fans just pick on random opponent players. They wouldn't know anything about that player, they merely look at the back of the jersey for his name and start yelling "hey <name>, you suck". For no reason.

Is yelling vulgarity at opponents really called passion?

I am an Arsenal fan by heart. I have been following Arsenal ever since i started watching soccer. As much as I want Arsenal to win, that doesn't mean i feel that the opponents suck. As much as I hate Robin Van Persie leave Arsenal, It doesn't mean that I don't enjoy watching him score quality goals for Manchester United.

I really enjoy the positive passion in local home games, but why can't the passion and support be just about us? About how good our players are? Do we really need to pick on the opponents to show that we are passionate about the sport and the team?

Consider this post by the 1906ultras. Before I say anything, I really want to make this very clear: I am a big San Jose Earthquakes fan. I take it really personally when they lose. I love the Ultras and the passion that they put in to Buck Shaw. But for such a wonderful and passionate supporter group like the Ultras, do we really need such vulgarity? There's nothing wrong in hoping Colorado will lose, but do we really need to f*** Seattle? If you look at all the other posts by them, they are all really positive and it actually ignites passion in the heart of every fan. And not to forget the recent letter to the players written by the ultras. It even gave my wife goosebumps (she just started following sports and she has never been so passionate about a team before). Why can't it just be about these good things? Why do we need to f*** the opponents?

Just to be clear, I am all for booing the referee when he makes a mistake, or even yelling at an opponent when he behaves in an unsporting manner. But not because he plays extremely well causing trouble to our team. I recently happened to be in Seattle and went for an MLS game there. They have their own supporters groups who are as passionate as us (ok, may not be as much as us). That doesn't make them our enemies or anything. Even though I liked the atmosphere there, I couldn't join them on even a single chant because it just didn't feel right. That's the kind of passion we want. We don't have to hate others to be passionate about our team.

Even in India, where people are crazy about Cricket, butchering and yelling at opponent players does not happen. The Indian Premier League (it is the major cricket tournament in India), has teams and players from all over the country as well as the word. But there the fans don't yell that opponents suck, instead they cheer their players, they say good things about their players no matter what. They respect the opponents.

I love San Jose Earthquakes. My heart will never cheer for another MLS team ever. I love ultras. Even though I don't sit in section 109, i always chant with them involuntarily throughout the game. But i'd really love it if the fans (not just the ultras, everyone) can focus more about the good stuff on our side rather than yelling at opponents.

It is called "home advantage" for a reason. It is not called "away disadvantage". Even the players exchange jerseys with opponents after the game. Why should we see them as enemies? Let's make the opponents feel welcome. Let's beat them in the sport on the field, not with words off the field.

As Eric Raymond said in Cathedral and Bazaar, Any energy you spend hating the opponents would be better spent on loving our team's craft (rephrased to fit into context).

Even though this post talks vastly about soccer, I have seen this happen in all the American games (baseball, football and probably hockey too).

For the first time in life, I have the opportunity to follow a team I love passionately by going to the stadium week after week. This is just my 20 cents for making real passion come out of any sport. Supporting your team is one thing, but bashing the opponents.. doesn't make you sound like a good person. Just think about it for a second before yelling.


-Vignesh

Friday, September 20, 2013

Bucket List of People to Meet in Lifetime!

We all love meeting celebrities. Because of the geography that I live in right now, I have had the opportunity to meet quite a few of them over the past year.

I always had this list of people to meet in person before I die in my mind. Until a year ago, It was mostly more of a fantasy list. But once I moved to where I am now, the fantasy started becoming reality. So I wanted to transfer that list from my brain to a document so that I don't miss out on anyone if an opportunity knocks on the door.

Here is the list (in no particular order):

PersonWho/What/Why?Met/Been There?Note/Souvenir
Thierry HenryThe person I respect the most in the world.No-
Don KnuthFather of modern computer science.No-
Dennis RitchieFounder of C (The R in K&R).Not possible anymore!-
Brian KernighanFounder of C (The K in K&R).Yes2013-06-20: Autograph
Linus TorvaldsFounder of Linux and Git. Strongly believes in whatever he believes in.No-
Robert LoveA huge contributor to the Linux kernel.Yes2013-06-13: Autograph
Bjarne StroustrupFounder of C++.Yes2013-08-15: Picture with him & Autograph
Randall MunroeHe is a hero of mine and worship his sense of Sarcasm and WitNo-
Matthew PerryMy most favorite actor in the world.No-
Lisa KudrowMy most favorite actress in the world.No-
Michael SchumacherHe was a huge inspiration as i grew up watching him win.No-
Larry & SergeyMy role models in life.YesEvery Fridays (now every Thursdays).
Matt CuttsOne of the early employees of Google and famous for his work on Web Spam.Yes2012-12-20: Lunch
Jeff DeanThe most bad-ass engineer ever.Yes2013-01-22: A walk around Charleston Park
Stade De FranceMy most favorite football stadium in the world.No-
Nou CampThe holy grail of football.No-
The Corrs (Sharon Corr)My most favorite band and most favorite violinist.No-
Felicity HuffmanHer character's attitude in Desperate Housewives resembles almost 100% that of my wife.No-
Jim ParsonsWho wouldn't wanna meet him?No-
Ramsus LerdorfFounder of PHP. The language i have written most of my code in.No-
Jeffrey ArcherMost favorite author in the world.No-
Paolo MaldiniI grew up watching him play. Perfect combination of style and class.No-
Arsene WengerI grew up watching him. One of the most inspirational people.No-
Vint CerfThe reason why we all have a job. Founder of TCP.Yes2012-11-20: Said hi and shook hands
Kunnakudi VaidyanathanA person who can talk with violin.Not possible anymore!-
Ron RivestThe R in RSA.No-
Petr MitrichevHas been Topcoder #1 for many years.No-
Mary Lynn RajskubSecond most favorite actress.No-

I will try to keep this list updated mostly as a record for myself rather than for the world to see.


-Vignesh

Wednesday, September 11, 2013

VLC Media Player: Automatically Skip Songs in Indian Movies!


I watch a lot of movies. Really a lot. And VLC Media Player is my (and many others') favorite. Indian movies are plagued with songs in irrelevant times and most of the time it just interrupts the pace/flow of the movie. No offense to music lovers/music makers, I like listening to songs in general. But I don't like them in the middle of an important scene in the movie.

The Problem

Whenever a song starts, inevitably I try to use the seek bar (using the seek bar is really one of the big pain points of any media player as it almost never takes you to where you want) and seek to the end of the song. Most of the time I end up seeking either just after the song (thereby missing something important) or to some portion in between the song (thereby having to wait for some more time for the song to end).

As an engineer, I naturally wondered, Wouldn't it be wonderful to have an automated way (preferably a keyboard shortcut) to just skip the song and move to the more important stuff?

This is exactly what I sat down to solve. Based on this xkcd, it seemed like it would be worth the time.And I (sort of) have a perfect solution that helps me skip songs automatically in the press of a button in VLC Media Player.

The Solution

As hard as the problem might seem, I ended up using a very simple heuristic. Start analyzing the audio stream, and whenever there is a silence for about a second or so, it's likely that the song ends there. I just came up with this heuristic based on the fact that most Indian movie songs are continuous (either lyric or the music goes on throughout the song without any breaks) and when the song ends, there is usually a small interval of silence before the next scene starts. And if there is a silence somewhere in between the song, just do the analysis again and it will take you to the next silence which is most likely the end of the song.

Is it perfect? Absolutely not. It's not even a solution, it's more of a heuristic (aka hack) which exploits some pattern in the Indian movie songs. And in my observation (I have been using this for quite a while now), It seems to be working correctly 99% of the time.

Implementation Details

Note: This section has technical jibber-jabber. If all you care about is how to use the script in your VLC media player, skip ahead to the "Usage" section.

First things first, I chose VLC media player, because that's the one I use. If you aren't using it, then you should start using it too. To begin with, we need to query VLC Media Player.

The overall flow goes something like this:
  1. Get the name of the file that VLC is currently playing
  2. Get the time point of the current playback from VLC
  3. Analyze the audio stream of the file and detect the next silence beginning from the time point of current playback
  4. Seek VLC to the determined duration where silence was detected (this is likely the end point of our song)
As complex as these steps might seem, they are fairly trivial to accomplish. To perform steps 1, 2 and 4 all we need to do is enable the HTTP interface in VLC. Once that's done, it is straightforward to get details of playback and control the player through a simple HTTP interface. The 2nd step is a little more tricky as it involves analysis of the audio stream of a file. Fortunately, we have a swiss army knife in our hands which will not only analyze the audio stream, but pin point us to the exact location of silence that we are looking for. The tool is none other than FFmpeg. The silence detect filter in ffmpeg has been used to accomplish this.

Here is a rough sketch of the ffmpeg command that I use:

ffmpeg -ss <start_time> -i <input_file> -t 600 -vn -af silencedetect=noise=0.1 -f null -

Let me break that up:
  • -ss <start_time> :- seeks to the specified time in the input file. this value for this is obtained from VLC's HTTP interface
  • -i <input_file> :- absolute path of the file that VLC is currently playing. this value is obtained from VLC's HTTP interface
  • -t 600 :- analyzes only 600 seconds (10 minutes) of audio to detect for silence (as Indian movie songs are hardly longer than 10 minutes).
  • -vn :- ignore the video
  • -af silencedetect=noise=0.1 :- enable the silence detection filter with a threshold of 0.1dB. this value was picked by trial and error.
  • -f null - :- just print the output of the filter in stdout rather than a file.

We then grep for the exact duration and then seek VLC based on this output.

Code

Look into the variables on top of the file and change them as per your environment if required.

Usage

To use this script, you need to install the following (fairly straightforward if you are tech-savy, but doable even if you are not).


Once you do the above steps, all you need to do is to bind a keyboard shortcut such that the script will execute. For Mac, I used Keyboard Maestro to set up a global keyboard shortcut which will invoke the script. There should be an equivalent program for Windows/Linux too. So that whenever a song starts, I merely use the keyboard shortcut to skip it.

Hope you enjoy it.


-Vignesh


Education is a cure for all problems. Donate for the cause of Educating kids: Computer Kindness Foundation is helping schools to build Libraries. Follow the link to contribute.

Monday, July 29, 2013

Our Story!


Circa May 2005 - The Characters

Boy - A 10th standard student in Coimbatore, who moves to Madurai for higher secondary schooling.

Girl - A 10th standard student in Chennai. No prizes for guessing where she moves for her higher secondary schooling!

May 2005 to June 2007 - The Beginning

As many would anticipate, they both ended up being classmates in their new school. Despite that, sadly, nothing interesting happened in this period of time (we know, they were such idiots back then!). They just looked at each other on random days and barely spoke.

June 2007 - The Actual Beginning

The girl moved back to Chennai and the boy moved back to Coimbatore for college. As with most couples of this generation, they started conversing with each other in the form on SMS'es and phone calls. Few days after that, they felt they were really close to each other. Few months after that, they realized they can't live without each other.

Few Months (or years) Later

The boy was on a late night train journey and as it was always, they were talking over phone (despite the annoying train noise). He felt something spontaneously and popped the question. It took a while for him to get an answer, but it was an answer that he rejoices till today!

P.S. The time frame of the above paragraph is omitted intentionally. ;-)

September 2011 - LGTM

The girl told about her life choice to her parents and the boy did the same to his parents. Both of them were genuinely happy instantaneously. No hesitation, No fuss, Pure happiness. It was then they realized how gifted they were to have such wonderful parents!

September 2012 - Its Official

The boy and the girl got engaged on September 2nd, 2012. It was a small but wonderful ceremony with family and friends.

December 2012 to March 2013 - The Present

We are writing this draft over a video chat (damn you geography!). We are really excited about the brand new phase of our lives that we are about to step on to. So please mark your calendars and try to be there on our special day, as your wishes would mean a whole world to us!

By the way, the girl's name is Gayathri and the boy's name is Vignesh! :-)

March 2013 and Beyond

We are undergoing our "Happily ever after" phase. :-)

P.S.: I didn't write this now. I am just copying this from my wedding website. Since that domain expired, I wanted this to live somewhere on the internet.


-Vignesh

Sunday, July 14, 2013

Announcing Social Photos v2!

I have been working on this side project for quite a while now and I am happy to announce that it is launch ready now!

Visit http://socialphotos.net to manage all your digital photos across Social Networks in one roof using a simple intuitive user interface.

Features Include:

  • Transfer Photos
  • Transfer Albums
  • Download selective albums as a zip file
  • View Slideshow of your albums
  • Monitor progress in a simple pane
  • And much more!

Please do feel free to give feedbacks/suggestions. Use it and Share it!


-Vignesh

Sunday, June 30, 2013

Using hash tags to organize bash history

We use hash tags all over the place in social networks. We use it extensively on Twitter and Instagram. Facebook recently launched support for hash tags as well.

So, in a way, our online life revolves around hash tags. Given that, it’s a really great thing for bash power users that # in shell means comment. I usually tend to type long commands and won’t bother remembering or saving them somewhere as it is in the bash history and i can retrieve it by reverse-i-search (Ctrl+R) anytime I want. 

As time passes by, more than often I end up retyping the whole command as reverse-i-search doesn’t have a unique combination of letters/words to search for. So, off late, I have found a dead simple way to never lose control over reverse-i-search because of too many similar commands. I just append a hash tag every command I type in. And later search for the hash tag in reverse-i-search. Since, anything that follows # is treated as a comment, the text is silently ignored, while giving you power to search through it alter on.

For example, when i write PHP code, I often tend to run lint on all the php files before executing them to make sure there aren’t any silly syntax errors. This is the exact command that i run:
find . -iname '*.php' -print0 | xargs -0 -n1 php -l
If you look at this command, none if its contents are unique by any mean. All these phrases and commands are something that we use over and over again. So it’s very plausible that this might get lost in the bash history and practically un-searchable with reverse-i-search. Now this is the command with a hash tag appended:
find . -iname '*.php' -print0 | xargs -0 -n1 php -l #phplint
Tada, there we go. From now on, we can do a reverse-i-search for “#phplint” or merely “phplint” to get back this command from the bash history. Also make sure you set HISTSIZE to a large value in your .bashrc to make sure you history is practically infinite.

-Vignesh

Do a good deed today. Donate to the Prime Minister's National Relief Fund.

Wednesday, May 8, 2013

Indians in USA: Why we do what we do!

Warning: Quite a lengthy article ahead. No pictures, mere yada yada yada.

I recently came across a post in Facebook (could not link to it as I don't remember who posted it and there is no way to search posts in Facebook - a story for another day). The same article can be found here: http://goo.gl/F31qK. Even though the article is quite old (2009), I've seen the same resurfacing on social media often and it's pretty relevant even today.The article was titled 22 things that Indians do when they return from the US. Though most of it is true, some of it is done as a force of habit and not as an intention to show off.

In this post I would like to go through those points and give more context to why we do what we do. I don't intend to justify that what we do is right or wrong, I would just like to add a little perspective as to what we go through in the USA that makes us behave the way we do when we are back in India.

22. Use Nope for No and Yep for Yes.

This is absurd. All the peters (Tamil slang for – oh man, what a pseud) in India these days do this. You don't have to come back from the US to do this. Ever since facebook and whatsapp became the norm of communication, "yep" and "nope" have become the norm too. This could be one of those things that could have been relevant in 2009 but certainly not today.

21. Tries to use credit card in road side hotel.

Yes, it is true. It happens because in the US, even the so called potti kadais (small shop usually as a part of a moving truck or some such) accept credit cards. I hold a credit card in my phone's case and that acts as my wallet. I do not carry a separate wallet. I mentioned this on one of my earlier posts as well.

20. Drinks and carries mineral water and always speaks of health conscious.

I haven't done this personally and I believe not many people do this. It may be true that Americans do that when they visit India as they grow up in a little better hygienic environment, they are less immune to lower hygienic environments like India. So if an Indian who grew up in India does this after coming back from the US, you have all the rights to mock at him as he doesn't have any immunity issues.

19. Sprays deo such so that he doesn’t need to take bath.

Name one software engineer in Chennai/Bangalore who doesn't do this.

18. Sneezes and says ‘Excuse me’.

I have seen this a lot among those MBA type people, but it isn't very common among Americans either. So I don't honestly understand why we do this (although I don't). A common thing that Americans say is "bless you" when a person nearby sneezes. I think this more of a manner than show off.

17. Says “Hey” instead of “Hi”.
      Says “Yogurt” instead says “Curd”.
      Says “Cab” instead of “Taxi”.
      Says “Candy” instead of “Chocolate”.
      Says “Cookie” instead of “Biscuit”.
      Says ” Free Way ” instead of “Highway”.
      Says “got to go” instead of “Have to go”.
      Says “Oh” instead of “Zero”, (for 704, says Seven Oh Four Instead of Seven Zero Four)

This is absolutely a force of habit. It is not about showing off. Had the Americans invaded India instead of the English, this would seem natural to all of us (and words like Biscuit and Taxi would have seemed absurd). In the US, everybody uses the words that the Americans use. I have gotten weird looks from many shopkeepers when i ask for Biscuit. I have been stared at for saying Capsicum. So, as time goes by, you get used to these and it becomes usual. It takes time to change it back when we get to India.

On a similar note, does anyone know what the back portion of a car is actually called? "Trunk" may be? After coming to the US I learned that it's called "boot" here. In India (atleast in Tamil Nadu) we call it "dicki". Does anyone even know what language that is? I am 20+ years old and I don't know it.

16. Doesn't forget to crib about air pollution. Keeps cribbing every time he steps out.

If someone does this, he/she is showing off (or putting scene, if you will).

15. Says all the distances in Miles (Not in Kilo Meters), and counts in Millions. (Not in Lakhs)

Lakh is a term used only in the Indian sub-continent. Million is used pretty much every where in the rest of the world. So when you are away from the sub-continent you tend to stop using the word Lakh. You tend to count in millions (for heaven's sake even your salary is counted as hundred thousand dollars or some such and not as one lakh dollars).

In the US, all distances are in miles. Google Maps gives you miles, all sign boards are in miles, all cars' speedometers are in miles. When you live here for a while, you forget to count in kilometers. Miles become an inherent part of your life. So it is really hard to change that mindset when you are back in India. So this is absolutely a force of habit and not a show off scheme. To quote Sheldon, America should have followed the metric system, but sadly they don't.

14. Tries to figure all the prices in Dollars as far as possible (but deep down the heart multiplies by 50).

I would say this is natural human behavior. When your income is in one currency and you are spending it in the form of another currency, it is natural for you to convert it to the currency that you are actually earning. I don't see anything wrong with this. For example, I have seen many Indians say "you can get an iPhone in the US for 10000 Rupees" (referring to the $199 2-year contract price point). It is exactly the same, people earning INR see all the prices in INR. Same applies for USD.

13. Tries to see the % of fat on the cover of a milk pocket.

People in the US are really health conscious. At the same time, they know the difference between being health conscious as opposed to being health freaks. So, they do look into calorie count on every food product they buy. Almost all restaurants list the calorie content of every dish they serve. Few Indians might have genuinely picked this habit up while living here. But most of us do it for showing off. Accepted.

12. When need to say Z (zed), never says Z (Zed), repeats “Zee” several times, if the other person unable to get, then says X, Y Zee(but never says Zed).

Despite being good at English, only we know how much we struggle to make people over here understand our accents. When talking to any sort of customer service representative, making them understand your name itself is a huge pain in the a** (my legal name is Vignesh Venkatasubramanian - try pronouncing that to an American and make him understand). Also, many customer service IVRS systems here work on Voice Recognition rather than keying in numbers (instead of saying "Press 1 to make a reservation", it says "Say 'make a reservation'". So it is absolutely necessary to have some sort of a fake accent so that everyone here can understand what you are saying. Again, force of habit.

11. Writes date as MM/DD/YYYY, on watching traditional DD/MM/YYYY, says “Oh! British Style!”

When I first entered the US, the immigration officer wrote the expiry date on my I94 in MM/DD/YY format. I was totally puzzled at first and it took a while for me to realize that. All the forms that you use on a day to day basis (bank, government forms, etc.) all require the date in MM/DD format. All television channels, newspapers and posters have the date in MM/DD format. So, naturally, once you are here for a while, you will start writing that way too. It's hard to switch a 20 year practice of writing it in DD/MM format when you get here from India. Similarly, it's hard to switch back. Force of habit.

10. Makes fun of Indian Standard Time and Indian Road Conditions.

Indian Standard Time itself begs to be made fun of. It's not just us, even people in India criticize IST. No other country in the world that has 2.5 hour time difference between its extremes has a single timezone throughout the country. No comments on Indian Road Conditions.

9. Even after 2 months, complaints about “Jet Lag”.

Showing off. Accepted.

8. Avoids eating more chili (hot) stuff.

Honestly, I haven't seen anyone doing this. If anything, I was totally sick of lack of spiciness, so I have all sorts of extra spicy food when I go back to India. To give more context, most Indian restaurants here serve sort of Americanized Indian food. Because Americans generally have a low tolerance to spiciness in food (most of their food is bland). So to make business here, restaurants have to reduce the spiciness. Unless you go to a Andhra restaurant, most Indian restaurants serve less spicy food by default unless you explicitly ask for super extra spiciness.

7. Tries to drink “Diet Coke”, instead of Normal Coke.

This is something that many people see as a show off thing, but it is not. Whenever you ask for a coke here, the shopkeeper replies "Regular/Diet/Zero?". Have anyone heard of Coke Zero back in India? Nope, me neither until I got here. Every soda product has a diet version here (ever heard of Diet Mountain Dew, Diet 7up, etc?). Naturally, we end up choosing Diet Coke/Coke Zero when given a choice over Regular coke (as it all practically tastes same to us Indians). It becomes a very heavy force of habit that at some point of time, we start looking at regular coke as some high calorie'd demon that could induce a lot of fat in you. Force of habit.

6. Tries to complain about any thing in India as if he is experiencing it for the first time.

Accepted. Even I am annoyed by people who do this. Especially, second generation Indian kids who despise India and Indians.

5. Pronounces “schedule” as “skejule”, and “module” as “mojule”.

No one does this. A better accusation could be, "Talks in a fake American accent". Even though some genuinely can't lose their accent, most of us do it to show off (even I have done it a couple of times).

4. Looks suspiciously towards Hotel/Dhaba food.

I don't think most of us do it. On the contrary, roadside food is something that is practically non-existent in the US. So most of us miss it like crazy. For instance, I went to the roadside bhel puri shop when I visited India (I took 30 minutes off to do this despite all the other important stuff I had to do).

3. From the luggage bag, does not remove the stickers of Airways by which he traveled back to India, even after 4 months of arrival.

Agree that this happens. But it is more towards the sense of happiness of having been in the US than to show off. Also, most of us do it within India when we take a bag on a domestic flight. It's very rare for Software Engineers in Chennai/Bangalore to go on a domestic flight home. But when he/she does, they don't remove the flight's baggage tag either. I have seen many people doing this.

2. Takes the cabin luggage bag to short visits in India, tries to roll the bag on Indian Roads.

I got nothing to say about this. I am surprised that people have even noticed such minuscule things.

Ultimate one: 1. Tries to begin conversation with "In US..." or "When I was in US..."

Guilty as charged. :-)

If you read this far, you should probably follow me on twitter.

-Vignesh

Wanna do a good deed today? Help someone, visit http://www.computerkindness.org (or click on the banner in the top right corner of this page).

Tuesday, April 23, 2013

Solving Boggle (Scramble with Friends) with a Bot!

Headnote

I am always fascinated by Android games, especially puzzle games. This is how it usually works with me and a puzzle game. I start playing them with random friends. They beat me and I beat them on and off. Then I sit and think, this is so monotonic and algorithmic that a human being shouldn't be sitting and doing it. Then I sit with the computer (with my favorite monkeyrunner Jython in it) and try to come up with a simple algorithm for it. Then i plug in the standard monkeyrunner code to actually feed the output of the program back to the device. Then I usually become #1 among my friends in the leaderboard (often even in the global leaderboard) ;-)

This is one such scenario. Zynga's Scramble with Friends has been really popular among my friends off late. So i hit this routine cycle and ended up with a beautiful bot which usually scores a centum (like the one TamBrahm parents force their kids to get in Mathematics).

With that out of the way, let's begin.

Objective of the Game

The game consists of a 4x4 grid of letters. You have to form as many words you can by starting from a letter and by moving to one of the (upto) 8 adjacent letters. Dead simple, but really interesting and addictive.

The first thing needed to solve this is a dictionary of words. I went on the internet and downloaded a plain text dictionary file which had about 170k words in it. Good enough to start with.

Algorithm - Breadth First Search

The number of valid words is usually very limited. In most games, the total number of valid words is usually < 400. So, a simple Breadth First Search (BFS) will do starting with single letter elements and then add the neighbors recursively. One key insight is, if you come across a prefix that never occurs in the dictionary, you can discard that prefix at that point instead of adding it to the traversal queue.

A rough sketch of the algorithm is as follows:
  • queue = [all 16 characters]
  • while queue is not empty:
    • word = head of queue
    • if word is in dictionary output it [1]
    • for all neighbors adjacent to the last character of word
      • new_word = word + neighbor
      • if dictionary has words with prefix new_word, add new_word to the queue [2]
That's it. Straightforward implementation of a BFS-like algorithm.

Choice of Data Structure

The key to solving this problem efficiently lies in choosing a good data structure for implementing the dictionary. The dictionary needs to support two major operations. One is looking up if a word exists. This is used for step [1] in the above algorithm. The other operation is, given a prefix, check if there is atleast one word containing that prefix in the dictionary. This is used for step [2] in the algorithm mentioned above.

Array ?

One good looking candidate is using a simple array (note that the dictionary is already sorted for us). Look up can be performed using simple binary search. Prefix checking can also be performed using a modified binary search (if search succeeds, then prefix exists. if search fails, prefix existence can be determined by looking at the bounds in which the search failed). Also, note that the dictionary has ~173k words. So, searching is gonna take log(173k) which is approximately 18 hits in the worst case. This is a totally fair deal.

Trie ?

Another possibility is using the Trie, whose raison-d'etre (very reason for existence) is to implement such dictionaries. The Trie implementation is also fairly trivial (since we require only two major operations apart from Trie construction). In the Trie, both the operations are gonna take as many hits as the length of the word or the prefix being looked up. So asymptotically, both these data structures are more or less similar and we don't have a big advantage in using either one over the other since our output is always gonna be < 400 words.

I decided to go with the Trie. After reading this article about Trie implementations in Python, I decided to quickly write my own implementation of Trie. Also, this made life simpler as I couldn't quickly find any good resources about using external libraries within monkeyrunner.

Implementation Quirks

Since I had already used monkeyrunner a few times before, implementation turned out to be pretty straightforward. The following are a few implementation quirks and nuances that the script deals with:
  • Input is manually entered as a raw row-major string of length 16.
  • If the same word can be formed by two different combinations, only one combination is actually considered valid. This is overcome by storing a list of already found words in another Trie.
  • Even though the script finds smaller words first (because of BFS), it actually starts outputting words of length >= 5 first and then after it has exhausted all the lengthier words, it then outputs the smaller words in the reverse order of length (4,3,2). This is to maximize points in case we don't find time to output all the words.
  • The game offers three lifelines. I found the freeze option to be useful to the bot (as each freeze gives you 15 additional seconds of game time). So, the script automatically taps on the freeze lifeline every 30 seconds.
  • We also need to store the co-ordinate of each letter in the queue along with the letters themselves in order to simulate the output in the device.
  • The co-ordinates are hard-coded for Nexus 7 portrait mode.

Code

The whole implementation can be found here: https://github.com/vickyg3/scripts/tree/master/scramble_bot

Sample Video

Here is the exciting part. This is how it looks like when my bot plays the game:



It's always a very nice feelings to watch you script do such beautiful things.

-Vignesh

Wanna do some good deed? Visit http://www.computerkindness.org (Or look for the banner in the top-right of this page).

Saturday, April 20, 2013

C++ COW Craziness

Note: This isn't one of those Linus'ish articles that bitches about C++. I like C++ and I would just like to point out one of the many nuances in the language that could affect the performance of your program without your knowledge.


C++ STL's string class promises Copy-on-write. What that means is that, you can make as many copies of the string, but the actual memory duplication will happen only when one of the strings are actually written to (i.e.) no memory duplication will be made for copies that are made for pure reads. Or atleast that's what I thought, until I discovered today that, if you use the [ ] operator on the string, you rig the COW functionality of it forever. It is something that you normally don't do, but doing so could cost you a lot of performance. Let's run through an example.
string s1(1024 * 1024 * 16, 'g');
for(int i = 0; i < 1000; i++) {
  string s2 = s1;
}
This runs in 19 milliseconds. That's because (obviously) there are no actual copies made. Just 1000 pointers being created to the existing 16 megabytes of data. Now, lets try modifiying the copied string.
string s1(1024 * 1024 * 16, 'g');
for(int i = 0; i < 1000; i++) {
  string s2 = s1;
  s2[0] = 'v';
}
This runs in 4.3 seconds. That's right, from 19 milliseconds to 4.3 seconds for making 1000 actual copies of 16 MB of data. This is the expected behavior, a copy is done when you try to write to it. Next comes the weird part, consider the following code:
string s1(1024 * 1024 * 16, 'g');
for(int i = 0; i < 1000; i++) {
  string s2 = s1;
  s2[0];
}
Guess how much time this should take? Intuitively it seems like this should hit the COW fast path (i.e.) no actual copies, because there is no "write" here. This takes 4.3 seconds too! The problem behind the [ ] operator is that, you can easily stash away a pointer to some portion of the string and modify it later thereby screwing up the state. So, it is impossible to perform COW once you use the [ ] operator on a string. The following snippet illustrates this:
string s1("hello");
char *p = &s1[2];
string s2 = s1;
*p = 'v';
You see what happened there? You stashed away a pointer to the middle of the string and then tried to change it later after the copy. This is sort of an indirect write, and there is no way for the compiler to determine this. So, the moment is sees the [ ] operator, it removes the COW functionality for that string. One way to do such a read without rigging the COW functionality is to do a crazy cast like this:
string s1(1024 * 1024 * 16, 'g');
const_cast<const string &>(s1)[0];
for(int i = 0; i < 1000; i++) {
  string s2 = s1;
}
This snippet takes the fast COW path and runs in 20 milliseconds. The takeaway from this article is that, do not use the [ ] (or the .at()) operator on strings, especially large string that could be copied later on. Even though you think you're doing an harmless read, you are rigging the COW functionality of that string forever. You are paying the price for that pointer you stashed away (or may be even released long back) without knowing.

 -Vignesh

Tuesday, February 26, 2013

The Last One by Myself!

Before you start reading, I really would like to warn you: Stop, Do not read. What follows is utter crap.

It has been almost 5 years now since i fell in love with this amazing girl. It’s almost time now. I am literally counting the last few days of my bachelor life. The 7 and odd years that i have known her has just swung by very fast. It just seems like yesterday that I was a small school kid. I honestly can’t remember how college life went on so fast. Here I am now, sitting in a totally different part of the world, still unable to believe that I am actually here.

When I look back at the past 7 and odd years, there are various wonderful moments which I would say have made my life what it is now. Not to brag, but not many people in life get almost everything they want, especially at such an early point in life. I am indeed one of the lucky ones. I am surprised at so many things that I do these days. It just seems like yesterday (literally like yesterday) that i went around nagging people for career advice. Yet here I am today, talking to many of my friends about building their career, etc. I really am surprised at the way I have turned out.

I am in this state where i ponder upon looking for words to express how my life has turned around to what it is now. There has been unexpected twists and surprises, expected happiness and so many other feelings which words cannot describe.

If I sit back for a moment and think about why I am writing this post, I honestly have no clue. I just felt like I should write something that will forever remain as the last post I ever wrote as a bachelor. Not that it is a big feat or anything, but blogging was something which, despite many resolutions and swearings, i could not keep up with. So, not to feel bad about myself that I hardly write anything these days, I started out writing this particularly pointless post.

I am flying out to India tomorrow. It’s gonna be the most #epic trip of my life. Loads of things to look forward to. Girl of my dreams, getting together with her. Life is fun. Hopefully I write something meaningful sometime soon (of course after I am back from the India trip).

-Vignesh