Pre School Problem - A programmer's approach!

Flashback - A few weeks ago

I came across this question in facebook. It said, "This problem can be solved by pre-school children in 5-10 minutes, by programmers in 1 hour, by people with higher education.. well check it yourself :)"

I shared this post and we had few nice sessions of fun with my colleagues in office. Myself and a colleague of mine were discussing about this and i told him, "the best part about this puzzle is that it cannot be solved programatically". And we carried on with our lives.

Train Journey - Last night


Last night when i was travelling by train, I had gotten a side lower berth and hence couldn't sleep (i have grown too tall to fit in to side berths :-( ). So, i had to while away time. I was tweeting, finished through a couple of stanford algo and nlp class videos. Then i had nothing to do, phone was almost running out of charge and so was the laptop. So i closed everything and started staring outside the window. Various thoughts came across, and one among them was "is there no way to programatically solve that facebook puzzle?".

Thus I started thinking about it, the first solution that came to my mind was to convert the numbers into a linear system of equations and apply linear regression on it. Then, the value of the co-efficients would give the mapping between a number and how we arrive at the solution (explained in detail below).

Coding Session - Today


I came home had a nice sleep. When i woke up, the first thing i wanted to do was to test out if my theory works. Obviously python (numpy) was the toolkit in my arsenal that would help me do this quicky. So here are the steps:

• Convert the input number into co-efficients of 0 or 1. For example, 2172 would translate to [0, 1, 2, 0, 0, 0, 0, 1, 0, 0]. (i th element denotes the number of times number i occurs).
• Now we have the coefficient matrix ( of size n x 10 where n is the number of inputs).
• We also have the constants column vector which are the known outcomes
• Now, we apply linear regression on this system to get the output
• Output will be a mapping between a number and how much it contributes to the output (0 maps to 1, 1 maps to 0, 2 maps to 0 and so on.)
• So to compute the outcome of a new number, merely sum the mappings of the digits in that number.

The whole program is embedded below:

The output of the program is:

['0 maps to 1', '1 maps to 0', '2 maps to 0', '3 maps to 0', '4 maps to 0', '5 maps to 0', '6 maps to 1', '7 maps to 0', '8 maps to 2', '9 maps to 1']

As we can see, that's a perfectly valid mapping!

Moral of the story:

1. Mathematics is really powerful. 
2. We can teach a computer much faster than we teach a pre-school kid. ;-)

-Vignesh

DOMCA - Days of my lives!

Note: This is a personal article about my college.

Department of Mathematics and Computer Applications, more commonly known as DOMCA within PSG Tech. It is the place where i spent 5 years of my college education. I have come across many students who have been a part of this department over the past 10 years, mostly through social media like twitter or facebook. But nowhere have i seen an article/post that talks about the fame and pride of this department. So I decided to do that part and this article is my small contribution to the department where i lived for 5 fun filled years.

To begin with, the department offers 4 masters programmes none of which is a BE/BTech/ME/MTech programme. Now, its really tricky to be in an engineering college, especially one of calibre as high as PSG Tech, and to belong to a department that doesn’t have an engineering programme. There will be a lot of internal politics and complexes going on among students between engineering and non-engineering stream within the college, and obviously DOMCA’ites find themselves in the minority (as there are around 15 to 20 different engineering programmes compared to 4 programmes in DOMCA).

But despite all that, the department have managed to produce students of world quality (yes, you read it right, i said “world” quality) excelling in mix of qualities. Its more of a “you name it, we have it” kind of place. Starting from the orientation talk on my very first day, to the last hour of class I attended and the last exam i wrote in my 5th year, i thoroughly enjoyed every single moment i spent in the department.

Key #1 to any department is their students. None of the programmes offered by DOMCA admits students through the government’s single window system, which means there are no school level state toppers in DOMCA. Yet, we somehow manage to groom ourselves through five awesome years of college experience that gives you an example for almost every possible situation that you would ever face in your life.

Key #2 to any department is their faculties. I am not going to claim that all the faculties are awesome. Some of them are really top notch (by this, i mean "world" class). Some of them are lame. But what makes DOMCA faculties unique is their willingness to learn, their willingness to teach us what we want rather than teaching us whats prescribed in the syllabus.

An even more important factor that decides the success of any department is student-faculty interaction. This is something that i personally think DOMCA nails to perfection. All faculties are friendly. Some of them, "literally" friendly. Whenever you have a problem, academic or personal they are there to help you out. I can even quote some of them as best examples of purity by heart.

Every person who is at DOMCA right now, or who are going to be a part of this wonderful place, rejoice it. Your sophisticated office cubes can never match TCS Lab. Your super duper fast multi core giant machine in office can never beat the fun offered by the dabbas in CC. I really wish i could be back at the department some day.


There are a lot of shortcomings, but in the long run, you hardly remember the shortcomings as you remember the good things. So, that's where this post is coming from, all the good things i have been through in the past five years.


This may not be Carnegie Mellon. This may not be Stanford. But our hearts really are proud every time we quote that we are from DOMCA in PSG Tech. So, according to me and possibly many others who were a part of this wonderful department, this isn’t just a department where they teach you subjects, this is an ecosystem that has been built upon human values.


To quote Sheldon, “I love PSG Tech, But my feelings for DOMCA are much greater. It is the singular location in space around which revolved my entire universe."

-Vignesh

Social Photos - Move photos between Google+, Flickr and Facebook!

Introducing Social Photos - http://social.foamsnet.com

A spin off project from my earlier Orkut Deja Vu. This cool web app lets you transfer photos between Google+, Facebook and Flickr using an intuitive drag and drop interface.

Do check it out and leave your feedbacks! :) Once again, the URL is http://social.foamsnet.com

-Vignesh

Having, Giving, Sharing and Receiving!

I was at at a local pizza place yesterday for dinner with a friend. After we had dinner there were two slices of pizza left and i asked the store guy to pack it for me. When we came out of the restaurant, there was a young lad who looked like a beggar and was asking us for money. My friend handed over the packed pizza to him and his face just lightened up. He sat on the platform and starting opening the box very eagerly.

Thats when we realized, giving feels really good. Whether its a material or whatever it may be, giving feels really good. No wonder teaching is the noblest job ever. I have been reading a lot of novels and philosophy books off late. In many of those, people are really thankful for even for the silliest of things, for example, one of the characters i read was thankful just to be born an American during world war 2. Why can't we be thankful for the fact that we don't struggle to get a meal thrice a day without giving a damn? Thankfulness and Gratitude are something thats highly underrated these days. In the modern era, how many of us even bother to thank fellow human beings for the smaller helps that they do to us?

Lets have a look at the major festivals that we celebrate every year. Tamil new year, Pongal, Birthday, Wedding Anniversary, Diwali, Christmas, Ramzan, and much more. Out of these we buy new clothes atleast for two or three of them. Just think of choosing one of these festivals every year, and instead of buying new clothes, donate it to people who can get more basic needs out of that money. Trust me, it feels damn good. When a kid sells drawing books in street, buy them. It will hardly cost 5 or 10 rupees. But the impact that it will make on the kid is significant.

I am no expert in moral values, but i think smallest of gestures can make us feel good and proud. Let us take a stand, feel good ourselves and more than that, make a difference in someone's life.

While writing this post, i couldn't help but remembering this dialogue of Joey's from Friends. Listen to it and have a good laugh :)

-Vignesh P.S.: Did someone figure out the head fake about this post ? It is a desperate attempt to prove that this blog is still not dead :)

This, That and More - The story of our Farewell :-)

Its the time of life that almost everyone has to experience. There is always a time when extreme fun ends. The farewell to college life is the event where one really realizes what he/she has done over the past 5 years, how lame he/she has been over the past 5 years, where he/she realizes the actuality that this part of life is going to end soon.

It was one such day in our lives. October 8, 2011 - The day that made many people who hadn't knew what a tear was previously in their lives cry their ass off.

The day was full of surprises. It wasn't just the day. The whole tale of farewell, right from the informal invitation to the formal invitation to the awesome ride to the farewell venue (which we never knew till we got there) was full of surprises.

Suspension Memo

Let me rewind back a few days to start telling this story. It was a usual day in college and I was with my friend in a nearby pani poori shop. My phone started ringing and at first I was kind of amused to see that it was my dad calling me (usually he never calls me unless its some emergency). I picked up the call and he said, "hey whats happening in college? we have received a letter from college that looks very threatening. it says you are suspended!". At first thought, though i was shocked, I definitely knew it was some prank. Then i asked him to read it out fully and confirmed it was indeed a prank. It was the informal farewell invitation that i was talking about! Many people fell for the letter. Few girls even started crying right away when their parents called!

(Click to Enlarge)

Handmade Invitation

Two days before farewell, the juniors asked us all to assemble in a classroom during lunch. It was quite a small classroom and there were 130 people in it. Needless to say the amount of noise we were producing would definitely turn all the heads to look at us. Then, each one of the juniors came and gave us an invitation. My first thought on seeing the invitation was that it was really awesome. For one, it was totally handmade. 70 handmade invitations? Thats a loooooootttttt of work to do!! It also had a nice picture of both our batches together. As one of my friends rightly pointed out, "anyone can spend a lot of money, but putting in effort for preparing 70 invitations really shows love!".

Note that, its just two days to farewell, and we don't know the venue yet.

Trailer

To add to all the expectations, the juniors released a trailer video for the farewell. Still, no clue of the venue! They kept us guessing!

The D Day - Assembly at IM Amphitheater

Even on the day of farewell, we didn't know the venue. We all gathered at IM amphitheater, 5 or 6 juniors were along with us to direct the proceedings. When everyone was there, the first instruction was to "Proceed to Peelamedu Bus Stop". People started fussing! What? Bus stop? Really?

The Journey to the Venue!

The first surprise of the day was parked at Peelamedu Bus Stop, we weren't going to take a city bus. There was a specially arranged bus which was waiting to take us to the venue! Even the bus driver was properly trained to play along with the lines of juniors to keep up the suspense of the venue!

The bus first started westward (towards lakshmi mills), so the first thing we did was to strike off of the major hotels on the east (jennys club, park plaza and le meridian). The bus journey was on and so was the music and dancing within no time. The bus slowed down and stopped in front of Tristar Deja Vu! Everyone shouted saying, "Yaay! We've reached! Our guess was right!". One of the junior guys got down and talked to the hotel security. He came back into the bus and said, "This hotel is very bad, olunga paint kooda adikala, we'll go somewhere else!". That was the heights of surprise!

Then the bus took a "U" turn. Everyone was able to guess the venue after the U turn! It was definitely one of the three hotels which we struck off earlier. The journey went on, along with the music and dance. We crossed jennys club and park plaza. Now everyone knew the venue! It was Le Meridian!

Le Meridian - Kovai Ballroom 1

Amidst of really personal warm welcome, we entered the room. My first thought on entering the room was "WOW"! I was totally speechless, it was amazingly decorated and well lit.

First item of the day was to celebrate the birthday of an unlucky junior soul. Unlucky because there were around 70 people waiting in the queue to wish him with birthday bums! There was a nice bigg cake with which we celebrated his as well as few others' birthday who fell in the proximity of few days.

Next was a video depicting how we have evolved over the past 5 years. The video rekindled many nice memories from our past. It indeed amazed me to know how much everyone has changed in personality over 5 years. Then came a tea break.

Next was a funny game. It was named "Balloon Bamblimaas!" :-) We were divided into 6 teams. Each team had to choose a person, who will sit on a chair. Rest of the team members have to place a balloon in the first person's lap and burst it by sitting on it! Team who bursts the maximum balloons will win! It was a fun game and as one of my friends very aptly pointed it out, "S.J.Surya kooda indha maari oru game a yosichirukka mattan da!" :-)

Then there was dancing for quite a while with various pairs formed by the juniors! Also, there were special performance by two awesome dancers of my batch, Santhosh and Michael along with the awesome dancer of the juniors batch, Shyam!

Then was the game named "Queen of Sheeba" (never mind the spelling). The queen will ask for an item, which we will have to fetch from some junior and hand it over to the queen. It was ultimate fun. The first thing that queen asked was for a t shirt. One guy was literally stripped in the process of obtaining the t shirt! ;-) Then was many other fun things like cigarette packet, hair clip and gold chain.

Amidst of all things we had lunch. Usually when we get free lunch, that will be the talking point. But in case of yesterday, no one even bothered to say "yaay free lunch". So much was the effect it had on all of us!

Then, there was a challenge wherein guys were asked to wear saree on stage with girls' help orally from their seats, followed by a cat walk and dance! Few of them did it quite successfully!!

Next was, they gave us all a token of rememberance. They had a song for every one of us and kept us guessing who the next person was. The gift was really awesome! It was a wooden piece with each of our photo carved in it along with a statement from their batch! So personalized and so amazing! It was really wonderful! They also gave us a booklet which had feedbacks about our batch from faculty, seniors and juniors.

Then came the feelings part of the day. The part which many thought can get over easily but went in the totally opposite manner. A video was screened. The video again showed various pictures of us over the 5 years. In the last scene of the video, few juniors were talking about things we'll miss and things they'll miss after we go away from college. The scene was well shot with only candle lights. The lights in the auditorium was switched off during the video screening and we were all totally into the video. The last sentence in the video was, "idhellam en panrom edhuku panrom nu engaluku therila. aana neenga therinjukanum nu nenachingana konjam pinnadi thirumbi paarunga! (இதெல்லாம் ஏன் பண்றோம் எதுக்கு பண்றோம்னு தெரியல. ஆனா நீங்க தெரிஞ்சுக்கணும்னு நெனசீங்கன்னா கொஞ்சம் பின்னாடி திரும்பி பாருங்க). Next moment was the one which made many cry. We all turned around, all the lights in the auditorium came on, 70 juniors were standing with each of them holding up a heart shaped balloon in their hands! That was totally the moment of the day! Unforgettable for life!

What happened after that was quite undescribable with words. Overall, it was indeed an amazing day. I was so happy to see the effort that the juniors have put in, in even the tiniest of things. Their attention to detail and level of personalization was highly amazing. In the end, the day concluded with a simple formula, Xanthronz + Embergs = Xanbergs! As one of the facebook statuses aptly described it: 9 A.M - Xanthronz! 11 A.M - Embergs! 5 P.M - Xanbergs!!

Kudos to every single junior who has worked hard and showered your love to make this day make a mark in our hearts permanently!

-Vignesh

Google DevFest 2011 - Bangalore!

Atlast, I attended a professional developer meet! And it couldn't be better. It was the Google Developer Fest organized by Google at Lalit Ashok Hotels, Bangalore. Most of the speakers were from Google headquarters, working on key Google products like Android, Chrome, Maps and App Engine.

The registration process went on very easily as they had a QR code in the confirmation mail, and used an android phone to take a picture of the same and verify the registration. Also, they had queues based on alphabets range. The T-Z queue was empty while the other queues were having atleast 20 to 30 people in it. For the first time in my life, i experienced an advantage of my name starting with V!

In this post, I am sharing the raw notes which i took during the keynote and various other talks. Hope this will be of some use.

Keynote - Android
* 550k+ activations per day
* Complex Screen density vs Size matrix - unifying everything => android
* Always use DPI (density per square inch) for specifying assets
* Honeycomb features
* Fragments
* Loaders - wrapper on top of asynctask
* Action bar
* Tabs
* Animation framework
* Compatibility library
* Multiple APK Support

Keynote - Bleeding edge HTML5 - http://india-devfest-keynote.appspot.com
* Interestingly, this keynote isn't called as "Chrome", though most of the topics were Chrome specific
* 160M active users
* Page Visibility API
* Prerendering
* Offline capabilities
* Web animation - CSS3, WebGL
* Native Client
* Future
* Web intents
* Fullscreen content - Fullscreen API
* Web Audio API - Real time processing and analysis of audio
* WebRTC - Real time communication
* Be updated
* chromestatus.com
* updates.html5rocks.com

Android Market - Tony Chan
* 250k + apps, 6B+ downloads
* In app billing, carrier billing
* Licensing
* All licenses allowed
* Code Obfuscation
* Don't reuse sample code
* In app billing
* Sell only digital content
* Reports for developers
* Device Filter
* Ability to exclude handpicked devices
* Multiple APK
* Filter by specific segments (platform version, screen size, etc.)
* App available as one product listing
* Apps upto 4GB coming soon (50mb app + 2gb archive)
* Pay attention to graphics - Featuring in android market depends mainly on that

Android Fragments & Open Accessory ADK - Tony Chan
* Fragments
* Fragments need not always have UI
* Fragments are an investment for the future!
* Fragments vs <include/>
* Fragments (optional UI, has lifecycle, not standalone, no direct interaction with intents) vs Activity
* Open accesory & ADK
* USB Device basics (Descriptor, etc)
* Open Accessory -> A USB host device that can communicate with an android device (e.g. Arudino)
* Use Android Accessory Protocol for communication

Building Integrated Apps on Google Cloud Technologies - Alfred Fuller
* App Engine intro
* Google Storage
* Store data in google's cloud
* Access via RESTful API
* Objects of any type (100GB / object)
* OAuth / Web browser
* Prediction API
* Machine learning API
* Upload training data -> Build model -> Predict new data
* Many machine learning techniques, Asynchronous training, Many platforms access
* BigQuery
* Analyze massive amounts of data in seconds
* SQL like query language, REST, RPC, etc.
* Batch jobs (Mapreduce)
* App Engine Identity API (For secure authentication)

Google Apps Marketplace - Claudio Cherubino
* Google Apps as a pure platform
* Google Apps APIs
* Success Stories
* OpenID SSO & OAuth
* Provisioning API
* Gmail contextual gadgets
* Sidebar gadgets in Gmail/Calendar
Twitter: @ryguyrg @scottmcmullan @stevenbazyl

Chrome Developer Tools - Boris Smus
* Basics - Cheat Sheet
* Revision history for all changes made inline in dev tools
* Aim to transform this into an IDE
* Commandline API - console.log takes n parameters, copy(), inspect() and $0
* Javascript debugging - See call stack, Pretty print
* Breakpoints - Line, Conditional, Exception, DOM, Event, XHR
* Future
* Extensions can extend developer tools too!
* Use chromiumer
* Remote debugging (--remote-debugging-port=31337 , Blackberry PlayBook only)

Google Places API - Chris Broadfoot
* What is a Place -> Abstract & Concrete
* Available as a web service and as a part of javascript maps library

Designing UIs for Phones and Tables
* UI Patterns for Honeycomb
* Action Bar
* App Icon - Where am i?
* View details - What can i see?
* Action buttons - What can i do here?
* Multi Pane Layouts
* Take advantage of screen real estate
* Consolidate multiple related screens into a compound view (similar to iframe in web)
* Screen rotation handling - Stretch (Settings), Stack (Calendar), Expand/Collapse (Gtalk), Show/Hide (Gmail)
* App Navigation
* Beyond the List
* Think and use innovative UIs to replace traditional lists (carousel, slidestack, etc.)
* Do's
* Aim for single APK
* Use compatibility library
* Customize visual design completely, if straying from Holo theme
* Support both landscape and portrait
* Extract dimensions for phones and tablets
* Use theme/style/etc. to reduce redundancy
* Marry OS visual style with your brand
* Don'ts
* Assume API level >= 11 (tablet)
* Assume xlarge == tablet (7" inch tablet is large)
* Use small font sizes
* Overuse fill_parent; Avoid excessively long lines of text
* Think tablets are big phones

Btw, the lunch was awesome too! :-P Overall, a great experience! :-)

-Vignesh

How I hacked an android game with Python and OCR!

Math Workout is a famous android game. In fact, it features in the top 5 of google listings for many math game + android related queries. The objective of the game is very very simple. It will fire simple math questions one after the other and you'll have to tap in the correct answer. Its a race against time among other users of the app in the world.

Here's how the app looks like and a few screenshots of questions:

As you can see, the game is fairly straigtforward. So its the time that you have to beat. A naive approach to that would be having a calculator or a computer near by and feeding in the questions to determine the answer and feeding it back to the phone. Totally manual!

Thats when the programming neurons of my brains started itching me that this could be automated and cheated by some mean. Come on think, think! So i sat on to solve this problem during my weekend and started thinking about ways i could attack this problem.

These are the steps that came into my mind in the first thought:

1. Grab a screenshot of every question
2. Crop the screenshot so that only the question is visible
3. Run the cropped image through an OCR engine
4. Parse the result and evaluate it
5. Identify the co-ordinates of the resulting number and appropriately simulate touch events in the phone

Bummer! Every step looked a bit complex in itself at first sight. Then came along a bit of googling, and voila, i found the perfect tool that i needed to perform steps 1, 2 and 5. It is the monkeyrunner tool that comes along with the Android SDK. It opens up a Python API through which i can grab and crop screenshots, simulate touch events given an (x,y) co-ordinate. Exactly what i wanted.



Now, I have the cropped image that has the question in hand. Next step is to run it through an OCR engine. Again googling told me that ocrad is an useful OCR command line tool that was available as a part of the GNU project. I installed it and found that it cannot process png images. So i had to run the image through a converter before passing it to ocrad. This small piece of shell script helped me accomplish that:


To keep things simple, the shell script is invoked from python using os.popen(). Now, I have the actual expression as a python string. As you can see from the sample screenshots, few questions can be solved by a direct "eval" whereas others require some processing. Basic operations like addition, subtraction, multiplication and division can be solved using "eval". Whereas questions like "10% of 20", "square root of 9" needs some processing. Thats what this following if else block does:



Now that the expression is evaluated and we have the result in hand, all that's left is to go through the result character by character and simulate touch events in corresponding positions in the screen. I managed to identify the co-ordinates of each number in the screen by trial and error and hard coded those values within two functions named getx() and gety() which will take a character and return its corresponding x and y co-ordinates respectively, and the simulation happens. Here is the code snippet:



To orchestrate this whole process and play the game fully automatically other cosmetic additions like coping up with the frame rate of the phone and taking care of screenshot/ocr lags are to be considered. These are handled by minor if conditions and sleeps for very small amounts of time.

The end result is as you see in the below screenshot :-P

Here is a video of how the game looks like when it is being played by my script:

Though these steps seem like computationally a bit expensive, in practice i found them to be really fast. The script was able to answer approximately 2 questions per second (with an explicit sleep of 0.2 seconds between two questions - which leads to 2 questions every 0.8 seconds). A C/C++ program might run faster than this, but i stopped here as i have accomplished what i wanted. Overall it was a fun filled Sunday! :-)

Here is a link to the full source code of the automated script: auto_math_workout.py (you can find ocr.sh from the gist above in this page - rest of the source code is in the link)

Any comments/feedbacks are welcome! :-)

-Vignesh