Friday Puzzle #4

22 09 2011

Set is a card game requiring good perception and quick thinking. It is played with a deck of 81 special cards. Each card has four properties, and every property has three different values. There is exactly one card for every combination of property values, hence the size of the deck is 3^4 = 81. A “set” is three cards for which all four properties have either the same value, or all have a different value. A more elaborate description of the game can be found here.

What is the probability that three randomly chosen Set cards form a “set”?


Swapping Without Temporary Storage

21 09 2011

Swapping two variables typically uses a temporary variable. But how do you swap if you are short of storage space? For instance, suppose you have your home keys in your left hand, and a grocery bag in your right hand. If you’re right-handed you’ll need to swap the keys to the other hand in order to open the door, but how do you do that with no temporary storage around?

The following algorithm is perhaps not the most efficient one but it fits the bill perfectly!

template <typename Thing> void Swap( Thing &oneHand,Thing &otherHand )
throw oneHand;
catch( Thing falling )
oneHand = otherHand;
otherHand = falling;

Again, the complete code can be found here.

N.B. This article was written tongue firmly in cheek. If you read the code like a story it should appear humorous, but in real world I do not advocate using exceptions as a mechamism for program flow control.

Solution To Friday Puzzle #3

19 09 2011

John: “Hi, Mary, how’s it going?”

Mary: “Fine, thanks. Have you been thinking of that spinner problem someone blogged about on Friday?”

John: “Tell you what, I was just going to ask you the same. You wanna try solving it using the Monte Carlo method?”

Mary: “Monte who?

John: “Heehee…  Monte Carlo method is an experimental way to get approximate solutions to problems about probabilities. You repeat an experiment over and over and over, and make notes about the outcomes. When you have repeated the experiment a great many times you will have a pretty good idea of the probability you are trying to figure out. For instance, if you toss a coin ten times you may get 7 heads and 3 tails, but if you toss the same coin 10,000 times you may get 5,014 heads and 4,986 tails. The ratio will converge to 1/2 just like it should if the coin is good.”

Mary: “All right, let’s try it out. Hey, wait a minute, we don’t have any axles or blades to make spinners out of. How you gonna experiment with a device with… no device?”

John: “Mind you, I’ve thought of that, too! See, here are three pencils. Two of them are green and one is red. If the axles are called A and B, and the point at which the blades are pointing to is X, then the distance |AB| =1 must be greater than both of the distances |AX| and |BX| or else the blades can’t overlap.  In other words, the simulated blades will overlap if and only if the length |AB| is the longest side of the triangle ABX.”

Mary: “A-ha, I see now: I’ll toss the pencils on the floor, the pencils will define three straight lines, and those three lines together will define a random triangle.”

John: “Exactly! And next consider the red pen as the base between the axles and the green pens as the blades, then the experiment is successful every time when the red pen defines the longest side of the resultant random triangle. Count successes and divide by total numer of experimentations and voila, Monte Carlo method in action! Let’s start, toss the pencils, Mary.”

Mary: “But…”

John: “Yes I know we have a long task ahead of us so lets just start.”

Mary: “But…”

John: “Please, Mary, the longer we argue the longer it takes to find out the approximate solution. You do want to find it out, don’t you?”

Mary sighs and tosses the pencils.

John: “Well?”

Mary: “Well…”

John: “Well?”

Mary: “Well… ummm… errr… I am sorry. I was trying to tell you that I am color blind. I can’t tell apart red and green, but I can say that because there are three pencils, the red pencil defines the longest side of the triangle with probability 1/3.”

John is at loss of words in face of Mary’s spontaneous insight.

So the answer to Friday Puzzle #3 is that the blades overlap with probability P=1/3. Also, my apologies for failing to supply the solution by Sunday like promised.

Friday Puzzle #3

15 09 2011

There is a horizontal plane which has two vertical axles that are 1 unit apart. Both axles have a rotor with two blades, each 1 unit long (hence the assembly of two blades has a diameter of two units). Both rotors can rotate freely without touching each other – but just barely, because the length of a rotor blade equals the distance between the axles. When the rotors are spun, the friction gradually slows them down until eventually they each stop at a random angle.

An attempt to visualize follows:

When both rotors have stopped, what is the probability that their blades overlap?

Again, post your answer and reasoning as a comment to this article. Lengthy and tedious integrals are fine ;-) but let me hint that the puzzle has a very neat intuitive solution.

Comma Operator BASICs

15 09 2011

For some of us BASIC was the first programming language we learned. Not because it was pedagogically great, but because it was pretty much the only programming language that was easily available. It came preinstalled on the earliest PC’s as well as the other home computers of the 80’s: Commodores, Sinclairs, Ataris, and many others.

Here is an example of BASIC program:

10 PRINT “What is your name? “;
20 INPUT name$;
30 PRINT “How old are you? “;
40 INPUT age;
50 PRINT “Hello, “,name$,”! Next year you will be “,age+1,” years old.”;
60 END

But hey! This blog was supposed to be about C++, so let’s make that program compileable with a C++ compiler. To do that, we need to do a few things.

Overload comma operator

Original creators of C++ deliberately misused the >> and << operators to read data from an input stream, and to write data to an output stream. I will emulate both functionalities using , (comma) operator instead. It is possible to use a single comma operator to emulate both >> and << operators, because the type of the first argument will determine whether input or output is intended:

template <typename T>

inline istream &operator,( istream &s,T &data ) { return s >> data; }

template <typename T>

inline ostream &operator,( ostream &s,const T &data ) { return s << data; }

Define required BASIC keywords

The BASIC keywords END, INPUT and PRINT are not a part of C++ language, but they can be defined using the C++ preprocessor:

#define END exit(0);

#define INPUT cin,

#define PRINT cout,

Forget about line numbering

Modern BASIC language doesn’t need line numbers anyway.

Once again, here is the complete code for this article.

Solution To Friday Puzzle #2

11 09 2011

Kudos to Al Nikolov, who was the first to correctly answer the Friday Puzzle #2.  The answer is indeed P=1/2, meaning that there is fifty-fifty chance that the Grumpy Old Man will get their seat without fuss.

Here’s the intuitive reasoning: When a businessman finds that their seat is already occupied by someone else and randomly takes another seat, he becomes the virtual Silly Old Lady and the real Silly Old Lady becomes a virtual Energetic Businessman. This adjustment does not affect the outcome but it helps to see that only one person (the real or virtual Silly Old Lady) will ever occupy a wrong seat. For as long as the real or virtual Silly Old Lady takes a seat that belongs to a businessman they will eventually have to move again. But as soon as the real or virtual Silly Old Lady takes either their own seat or the seat that is assigned to the Grumpy Old Man, then all remaining businessmen will be able to board the plane without fuss. Therefore, when Grumpy Old Man enters the plane there are two equiprobable statuses:

  1. All businessmen sit on a seat assigned to some businessman, and the Silly Old Lady sits on the seat assigned to herself
  2. All businessmen sit on a seat assigned to some businessman, and the Silly Old Lady sits on Grumpy Old Man’s seat

Because these two statuses are equiprobable, the answer is 1/2.


Friday Puzzle #2

8 09 2011

There’s a departure gate at an airport. Outside the gate there is a plane that has 256 passenger seats. At the gate lobby there is one silly old lady, one grumpy old man, and 254 energetic businessmen waiting to board the plane. Every passenger has a ticket that indicates their assigned seat.

Silly old lady is a bit absent-minded. When it comes her turn to enter the plane, she randomly chooses an empty seat and sits down, regardless of what her ticket indicates.

Energetic businessmen are efficient. They find their assigned seat easily and sit down after they’ve found it. But because they are also polite, they will randomly choose some other seat if they find that their assigned seat is already occupied by someone else.

Grumpy old man is… well… grumpy. He sits tight in the lobby while others stand in the line, and only after everyone else have boarded will he go into the plane as the last passenger. And boy, won’t he raise hell if he sees someone occupy his seat when he comes into the plane. I mean, after all, he’s paid full price for the flight and has the right to demand flawless service.

And so the boarding begins.

What is the probability that the grumpy old man was satisfied with the service after the boarding is over?

Post your answer and reasoning as a comment. I will post the correct answer by some time on Sunday if not already answered.