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!

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