Change Calculator

A dig at one of those code puzzlers from dzone. Thanks to Abhi (a buddy) for sharing it with me and instilling the urge for this adventure. I have utilized a subset generation algorithm (highlighted in code) from my mentor and friend (Pai) here.

Change Calculator 

Say you are given an infinite number of coins in the following denominations:

  • 25 cents
  • 10 cents
  • 5 cents
  • 1 cent

Write a method that would take an integer parameter named change. Work out all the permutations that can return that amount given the coins that you have available. For example, calculateChange(5) would return

  1. 1 x 5c
  2. 5 x 1c
var calculateChange = function (denominations, amount) {
	'use strict';
	var changeSets = 0,
		printChangeSet = function (denominationSet) {
			var matchFactors = [],
				findCombinationSet = function (denominationIndex, cumilativeSum) {
					var transientSum = 0,
						i = 1,
						denomination = denominationSet[denominationIndex],
						factorCount = denominationSet.length;
					while (transientSum <= amount) {
						//Pretty Printing
						matchFactors[denominationIndex] = i.toString() + " x " + denomination.toString() + "c";
						transientSum = cumilativeSum + (denomination * i);
						if ((denominationIndex + 1) === factorCount) {
							if (transientSum === amount) {
								changeSets += 1;
								console.log(changeSets + ". " + matchFactors);
							}
						} else {
							findCombinationSet(denominationIndex + 1, transientSum);
						}
						i += 1;
					}
				};
			findCombinationSet(0, 0);
		},
		// This function computes the possible denomination sets
		generateChangeSets = function () {
			var bitcount = denominations.length,
				mask = Math.pow(2, bitcount),
				i = 1,
				j = 0,
				k = 1,
				denominationSet = null,
				denominationSum = 0;
			while (i < mask) {
				j = 0;
				denominationSet = [];
				denominationSum = 0;
				while (j < bitcount) {
					if ((i & (k << j)) > 0) {
						denominationSet.push(denominations[j]);
						denominationSum += denominations[j];
					}
					j += 1;
				}
				if (denominationSum <= amount) {
					printChangeSet(denominationSet);
				}
				i += 1;
			}
		};
	generateChangeSets();
};
/*jslint indent: 4, maxerr: 1, passfail: false, browser: false, devel: true, windows: false, rhino: false, undef: true, node: true, bitwise: true */

To test this, simply execute:

calculateChange([1, 5, 10, 25], 5);

The decomposition technique utilized here (that of finding all the denomination sets first and then searching for the combinations that would yield the amount) doesn’t hold good against this classic NP-Hard problem where despite parallelization, you cannot cheat death owing to stack overflow for the larger sets, lower denominations and higher amounts.

Advertisements

ecnalG

Still wondering what this title means???

I can see the wry smile on your face telling me “No Big Brainer Dude!”
I know how easily you would have cracked this word Jumble. But, how many of you ever wondered why the “Jumble” was arranged this way? Well! There’s a reason for everything. I never thought I would carry this as a blog title when I was solving this “lateral thinking” (the one where you are supposed to think out of the box) puzzle a couple of months back.

The title indeed is “Backward Glance” and not just “Glance”!

I believe it is more difficult to frame a puzzle than solve one. Note the use of word “frame” rather than create. Language plays an important role in encoding the clues (both wanted and unwanted) that lead to the cipher (solution in our case). Dexterous encoding creates “intended” diversions and confusion to the reader. But remember the cipher is lying there to be discovered “beneath” framed layers of clues (information). We normally tend to leverage just our innate X-Ray vision (a.k.a. pragmatic mind) to look for the cipher “through” these layers of clues rather than giving a “Backward Glance” (Slide these layers aside and directly look at the cipher beneath) at it.

Let’s try to decode the title:
Real Clues:

  • It is a “simple/easy” Jumble (credit to my intuition or IQ)
  • The Jumble is arranged directly by “writing the word backward” (this is the most important clue which a pragmatic mind tend to overlook)

Diversion:

  • It is “just” a Jumble (blame it on my egoistic IQ)

See, it works! There’s no harm in taking a backward glance at the problem when you feel you have reached a solution. This “Out of the Box” approach sometimes helps unearth the vital clues that lead to the right solution. I will try to illustrate this further by taking on these two famous puzzles. Well! I have given you the most important clue by now.

Please see if you can crack it with a “Backward Glance” before attempting a “Forward Glance” at my take.

1. The Bicycle Thief

Here is a little tangle that is perpetually cropping up in various guises. A cyclist bought a bicycle for £15 and gave in payment a cheque for £25. The seller went to a neighbouring shopkeeper and got him to change the cheque for him, and the cyclist, having received his £10 change, mounted the machine and disappeared. The cheque proved to be valueless, and the salesman was requested by his neighbour to refund the amount he had received. To do this, he was compelled to borrow the £25 from a friend, as the cyclist forgot to leave his address, and could not be found. Now, as the bicycle cost the salesman £11, how much money did he lose altogether? (Courtesy: Amusements In Mathematics by Henry Ernest Dudeney)

:: My Take on IT ::

The entire problem ingeniously encoded beautifully boils down to:
Real Clues:

  • The cheque provided by the thief was “valueless”
  • The Real cost of the bicycle to the salesman was £11.00
  • The money that the salesman gave to the thief was £10.00 (as change)

Diversions:

  • All other information

:: The equation is very straightforward now! The total loss for the salesman was £21.00 (£11.00 + £10.00)! ::

2. The Missing Dollar

Three people are eating at a restaurant. The waiter gives them the bill, which totals up to $30. The three people decide to share the expense equally ($10 each), rather than figure out how much each really owes. The waiter gives the bill and the $30 to the manager, who sees that they have been overcharged. The real amount should be $25. He gives the waiter five $1 bills to return to the customers, with the restaurant’s apologies. But, the waiter is a dishonest man. He puts $2 in his pocket, and returns $3 to the customers. Now, each of the three customers has paid $9, for a total of $27. Add the $2 that the waiter has stolen, and you get $29. But, the original bill was $30. What happened to the missing dollar? (Courtesy: Jim Loy)

:: My Take on IT ::

The entire problem ingeniously encoded beautifully boils down to:
Real Clues:

  • The Actual Bill was $25.00
  • The 3 people spend altogether $27.00 ($30.00 – $3.00)
  • And the waiter took $2.00

Diversions:

  • All other information

:: The equation ($27.00 – $2.00 = $25.00) is very straightforward now! There is no case of any missing dollar here! ::

Never underestimate the power of A Backward Glance!

Probabilistic Bliss

This day that year :: 1989

Mathematics had eluded my senses (both common and uncommon) and I was literally treading this pathetic path (identifying problem patterns and memorizing its solutions). It was destination “disaster”. I was traumatized and the probability of a success was merely 0.5

This day that year :: 1990

An apple fell. I should say it literally broke or rather rewired the entire logic circuits of my psyche. I was so glad it fell unlike Mr. Newton who thought why it fell though I felt it fell late (better late than never, right?) I began to reason, analyze and attack the problems. I should confess that I became passionate, obsessed and finally possessed by Math.

This day this year :: 2009

Almost 2 decades. Mathematics rules my senses today. Till day, I don’t really know how this Boolean State Transition (0-1) occurred that too in such a short span. I attribute this success primarily to Mohan sir (my tutor) and to an unseen, unknown force (let me call it God) who, for a purpose, made this happen, which I am still in pursuit of.

Last weekend, I was flipping through the pages of a book on Discrete Mathematics that I bought (thanks to one of my mentors Pai for recommending this book) recently. And I stumbled upon this chapter on probability. It was a feeling that I cannot express through mere words. It was mere bliss as I laid down the Lego Blocks of knowledge one by one and I am sure that I did come up with the most beautiful structure that Richard Johnsonbaugh would have envisioned his reader to create.

Now with this confidence (or rather an element of defiance/arrogance, if I am to confess), I decided to try my fortune on the “Monty Hall” problem. It wasn’t that late before I joined the huge majority that failed trying. My obvious answer was obviously wrong. Hey! At least I tried. I tried to reason where I went wrong and read the solution that was illustrated in detail. I could very easily understand the rationale behind the solution (which is arguably been contested by many as confusing). Thanks to my foundation on probabilistic analysis that was re-solidified by Johnsonbaugh. I would like to share my take on it with the hope that it sheds light to any confused soul.

Monty Hall Problem

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (courtesy: Wikipedia)

:: My Take on IT ::

The key to the solution is to ascertain your best odds of nailing the prize with the choice you had made, assuming your chosen door has the prize hidden behind it, based on the 2 options that you have.

Option 1 (We decide to stick with our initial choice)

Remember the “key”, I had outlined above. Based on this, we would opt for Option 1 because we believe we chose the door with the prize behind it. The probability of choosing “this” door out of the 3 choices given is quite obviously 1/3.

Option 2 (We decide to change our initial choice)

Remember the “key” again. Why does one need to change the initial choice? Because, he/she believes that the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) has the prize behind it.

With this assumption our initial choice (say first event in probability world) had left us with a winning probability (p1) of 2/3 (i.e. the door with the prize is one among the remaining 2 non-selected doors out of the 3 choices). Now, here comes the crucial step in this experiment. The host (unlike in Option 1 where his/her action doesn’t affect the result) is actually telling us something very important i.e. the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) holds the prize in this case. And we can confidently pick this door (say second event in probability world) with a winning probability (p2) of 1 (certainty). So now, as the experiment is fair and the events are independent, the probability of the entire experiment would be (p1 * p2) i.e. 2/3.

Conclusion

To conclude, let’s analyze our findings on options 1 and 2.

  • Assertion 1: The chance of winning with Option 1 is 1/3.
  • Assertion 2: The chance of loosing with Option 1 is 2/3 (1-1/3).
  • Assertion 3: The chance of winning with Option 2 is 2/3.
  • Assertion 4: The chance of loosing with Option 2 is 1/3 (1-2/3).

Now, do I need to tell you what to do? Yeah! You guessed it right. The Assertions says it all!

:: It is best to switch your choice (Option 2) to increase your odds of winning the prize ::

Well that wasn’t that difficult, right? I guess not!

And, if you still find it confusing, please try visiting this site which helped me understand this solution to the problem.

The Impossible Question2

:: Context (Would I move Mt. Fuji?) ::


I couldn’t help wondering if I ever was in Gene McKenna’s shoes for this interview with Microsoft…

The Interview Scene (excerpt from the book):

Suppose you had eight billiard balls, the recruiter began. One of them is slightly heavier, but the only way to tell is by putting it on a scale against the others. What’s the fewest number of times you’d have to use the scale to find the heavier ball?

I shouldn’t deny the fact here that I am not facing this kind of question for the first time . I first heard a similar kind from one of my close friend who was proudly eliciting his success on an interview with Infosys. Well! now you see the line of corporations who has joined this “recruitment-methodology” band-wagon. So, I was kind of ready for this one. I have this habit (good as well as bad) of manipulating similar problems, imparting to it the “larger than life” image that I like to confront, just for the sake of personal joy and satisfaction. And I ended up wondering thus:

Suppose if it wasn’t known if the odd ball in the set was either heavier or lighter, what’s the fewest number of times one would have to use the scale to find the odd one?

Please give it a try if you haven’t, before you read my take on both. To start with, i have highlighted (bold and italicised) the key words that matter.

:: My Take On It ::


:: Take 1::
There are different solutions to this problem. “Divide and Conquer” is the key solution to this problem. But, how would you divide to make the conquest complete in the shortest possible moves?
Sets of 3 or its multiples are ideal in terms of elimination, in this case, as the last set would be reduced to just 3 and with just one weighing we can isolate the heavier/lighter ball. Let me explain it further. If the heavier/lighter ball is one among the 2 that is weighed, the heavier/lighter
scale indicates the heavier/lighter ball whereas if they weigh the same, then the third ball that is not weighed is the heavier/lighter one. On this account, let us try to divide these 8 balls into sets of 3 which leaves us with three sets namely A, B & C with 3, 3 & 2 balls respectively. The heavier ball in our case should lie in any of these 3 (A, B & C) sets.

Step 1 would be to determine this set. The easiest way is to weigh sets A & B of three balls each.

  • If A weighs more, the heavier ball is in set A
  • If B weighs more, the heavier ball is in set B
  • And if A & B weighs equal, the heavier ball is in set C

Step 2 would be to determine the heavier ball as we have reached the final set by now. And as explained earlier, we know how to determine the heavier ball from a set of 3 (A or B) with just one weighing. And of course, to the get the heavier ball from set C is just direct weighing.

:: So in just 2 weighing (cumulative weighing from step 1 through 2), we can determine the heavier/lighter ball ::

:: Take 2 ::
Now consider the case when we don’t know if the odd ball is heavier or lighter than the rest. Divide and Conquer principle applies here as well.

Figure 1 below shows the division of balls into various sets (A through H) for determining the odd ball in the most optimal number of weighings. The dotted lines indicate how sets G & H are derived (the details are available in Figure2):

Figure 1

Figure 1

Figure 2 below depicts the complete flow chart for determining the odd ball in the most optimal number of weighings:

Figure 2

Figure 2

:: So in just 3 weighing, we can determine the heavier/lighter ball ::

The Impossible Question1

:: Context (Would I move Mt. Fuji?) ::


This was one of those moments when I felt at least for a second that I was an older Jim Gibbons (1) in my early thirties, in front of the great William Shockley (2). What really fascinated me was that the reasoning that I had applied for the solution had striking similarity with the reasoning of the then, interviewer (2) and interviewee (1).

The Interview Scene (original excerpt from the book):

Shockley picked up his stopwatch.
There’s a tennis tournament with one hundred twenty-seven players, Shockley began, in measured tones. You’ve got one hundred twenty-six people paired off in sixty-three matches, plus one unpaired player as a bye. In the next round, there are sixty-four players and thirty-two matches.
How many matches, total, does it take to determine a winner?
Shockley started the stopwatch.

Though it’s said think twice (or more) before you do something, I think one needs to understand well “what” one is trying to do rather that worrying “how”, from the word “GO”. I guess that’s how i landed a knock-out in the first round.

Please give it a try if you haven’t, before you read my take on it…

:: My Take On It ::


Shockley was just setting the stage for Gibbons as indicated clearly by the strike-through lines. This is a diversion from the actual problem inducing unwanted complexities to the actual problem problem at hand. Now comes the real kill; the statements underlined will definitely take the interviewee off course on a wild-goose chase (though in this case would definitely lead you to the answer but not quick enough to beat Shockley’s stopwatch), but it discretely conveys the random knock-out nature of the tournament which is a key attribute in determining the solution. So, the final problem statement gets almost reduced to the “italic statements in bold”.

Shockley picked up his stopwatch.
There’s a tennis tournament with one hundred twenty-seven players, Shockley began, in measured tones. You’ve got one hundred twenty-six people paired off in sixty-three matches, plus one unpaired player as a bye. In the next round, there are sixty-four players and thirty-two matches.
How many matches, total, does it take to determine a winner?
Shockley started the stopwatch.

The answer is now lying open in front of you:

:: To determine a fair winner all others would have to be eliminated in this knock-out tournament which leaves us with 126 matches ::

Now the mathematical derivation which Shockley would have liked Gibbons to do based on his underlined statements:

  • 126 players -> 63 matches (A)
  • 064 players -> 32 matches (B)
  • 032 players -> 16 matches (C)
  • 016 players -> 08 matches (D)
  • 008 players -> 04 matches (E)
  • 004 players -> 02 matches (F)
  • 002 players -> 01 matches (G)
Ans: A+B+C+D+E+F+G :: 63+32+16+8+4+2+1 = 126 matches