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

15 Comments »

  1. topriddy said

    This is cool! A bit jealous you beat me to thinking of making a blog out of this though. 😐

    Also tempted to write a java equivalent but i’ll pass on it 😀

    • hahahahah…I’ve been dying to blog for a while now…thanks for providing an interesting topic

  2. Sogo said

    Nice one I must say….I would rather say its the joy of being a programmer…

  3. Javalove said

    Heheheh. . .Excellent. . .!

  4. When you spend 10 NGN to buy a candy, you’re actually buying one candy, plus one third of a candy (that you will get in exchange for its wrapper), plus one third of one third of a candy (that you get for the second candy’s wrapper), plus one third of one third of one third of a candy, and so on. This is a geometric series, its total means that spending 10 NGN actually buys you 3/2 = 1.4999… candies (this should be 1.5, but writing it as 1.4999… makes it clearer, I believe) So, with 150 NGN, you would buy 15 x 1.5 = 22 candies (rounded down, because it’s an infinite series), and with 1 350 750 NGN you would be able to buy 202 612 candies – no programming involved.

    Conversely, you could notice that the buy-then-redeem-wrappers process starts by converting every 10 NGN to a candy-and-wrapper, then discards three wrappers to get a candy-and-wrapper, which decreases the number of wrappers by two until there’s only one or two left. This suggests a simple constant-time algorithm :

    let buy money =
    let initial = money / 10 in
    initial + (initial – 1) / 2

    • wow…..I have one question…are you a programmer or not, whatever your vocation is, it surely must be interesting…..

    • pierigno said

      wonderful analysis!!

      Another simple solution would be

      int candies = 15;
      int factor = 3;

      for (int n = candies; n<= factor ; n=n-3+1) { candies++;}

  5. Walter Chang said

    solution in scala:

    def candies(cs: Int, ws: Int): Int = if (cs == 0) ws / 3 else cs + candies((cs + ws) / 3, (cs + ws) % 3)

    println(candies(150 / 10, 0)) // starts with 15 candies and 0 wrapper

  6. Temidayo said

    You know, I almost hastily said, why kill a cockroach with a pestle. But
    when I read more as to, what of if there are more values like: 160,170 etc

    I concluded, programming was created for this kind of monotonous and toilsome
    tasks.

    It was an interesting read. Good Job!

  7. Quintesse said

    To be honest, for this, I think it’s easier to have studied mathematics 😉

  8. blas said

    The easy life of a programmer, but the easier life of a mathematician 😀

  9. Tsa said

    127.0.0.1 is a loopback, it does not mean home

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: