Archive for May, 2011

The Easy life of a Programmer


A friend of mine have a saying

Even if you will never write a line a code in your LIFETIME, learn how to program so that your LIFETIME can be easier.

I confirmed this saying today when another friend gave us a problem, according to him most people got it wrong, but all the programmers got it right. It is a very simple real life problem

The problem:

A shop sells candies for 10 NGN each. You can exchange 3 candy wrappers for 1 candy. If you have 150NGN, how many candies can you totally get.

Manual Solution:

First how many candies can you get with 150NGN. 15candies, so we start from 15 candies. 3 candies or 3 candy wrappers are the same, since you can’t steal candy wrappers from your friends, so 15 candies will give you an additional 5 candies when you exchange the wrappers for candies. But your 5 candies are also eligible for the candy wrappers promo, therefore your 5 candies will give you an additional 1 candy and you will have 2 candies (or 2 candy wrappers) left. In total you now have 3 candy wrappers. These last three can give you 1 more candy and then you can’t have more candies because you are left with only one candy wrapper.

Going back from above, you now have 15 + 5 + 1 + 1 candies = 22 candies. You can have 22 candies from 150NGN.

Automated Solution:

I will assume that you know your multiplication tables very well, therefore you know how many candies you can get for the X amount of NGN that you have. So starting from N candies

  1. Lets define Q as number of candies / 3 (Quotient after division)
  2. Lets define R as number of candies % 3 (Remainder after division)
  3. At every point in time, the number of candies you have is Q + R, NOC = Q + R.
  4. Lets define ACC as the accumulated number of candies you have, in the above ACC = 15, ACC = 20, ACC = 21, ACC = 22.
  5. Starting from Q = 15, and R = 0 and ACC = 0 we can have the below procedure
  1. NOC = Q + R
  2. if NOC < 3, ANSWER=ACC
  3. if ACC = 0, ACC = NOC
  4. Q = NOC / 3
  5. R = NOC % 3
  6. ACC = ACC + Q
  7. ANSWER = back_to_step(i)

In step 7, we recursively call the procedure again until we get an answer. So Starting at Q = 15, R = 0, ACC = 0

NOC = 15 + 0 = 15

NOC > 3, noACtion

ACC = 0, ACC = 15

Q = 15 / 3 = 5

R = 15 % 3 = 0

ACC = 15 + 5 = 20

ANSWER =
      NOC = 5 + 0 = 5 
      NOC > 3, noAction 
      ACC != 0, noAction 
      Q = 5 / 3 = 1 
      R = 5 / 3 = 2 
      ACC = 20 + 1 = 21 
      ANSWER = 
            NOC = 1 + 2 = 3 
            NOC = 3, noAction 
            ACC != 0, noAction 
            Q = 3 / 3 = 1 
            R = 3 / 3 = 0 
            ACC = 21 + 1 = 22 
            ANSWER = 
                  NOC = 1 + 0 = 1 
                  NOC = 1, ANSWER = 22

ANSWER = 22.

The beautiful thing is the automated solution can now be used to solve for ANY amount of initial candies. To complete this post, I will post the python script that I used to solve it.

def hmc(q, r, acc):
      noc = q + r
      if(noc < 3):
            return acc
      if(acc == 0): 
            acc = noc
      newQ = noc / 3
      newR = noc % 3
      acc = acc + newQ
      return hmc(newQ, newR, acc)
Advertisements

Comments (15)