Sunday, April 8, 2012

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. ;-)