Follow @trinisoftinc

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

- Lets define Q as number of candies / 3 (Quotient after division)
- Lets define R as number of candies % 3 (Remainder after division)
- At every point in time, the number of candies you have is Q + R, NOC = Q + R.
- Lets define ACC as the accumulated number of candies you have, in the above ACC = 15, ACC = 20, ACC = 21, ACC = 22.
- Starting from Q = 15, and R = 0 and ACC = 0 we can have the below procedure

- NOC = Q + R
- if NOC < 3, ANSWER=ACC
- if ACC = 0, ACC = NOC
- Q = NOC / 3
- R = NOC % 3
- ACC = ACC + Q
- 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.

Follow @trinisoftincdef 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)

## 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 😀

## Akintayo Olusegun said

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

## Sogo said

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

## Javalove said

Heheheh. . .Excellent. . .!

## Victor Nicollet said

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

## Akintayo Olusegun said

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

## Victor Nicollet said

I can program, yes. My current job is being a start-up founder.

## 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++;}

## 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

## 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!

## Quintesse said

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

## Akintayo Olusegun said

I agree with you.

## blas said

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

## Tsa said

127.0.0.1 is a loopback, it does not mean home

## Akintayo Olusegun said

totally agree with you. but even at that there’s no place like a loopback