Friday Puzzle #5

29 09 2011

A bottle has diameter of 1 unit.  A box having size 2*2 units can contain four bottles at most.  A box having size 2*3 units can contain six bottles at most. A box having size 2*4 units can contain eight bottles at most. Et cetera…

Is there a box having size 2*N units that can contain more than 2*N bottles? Can you suggest an upper limit for N? Can you compute and prove (or at least justify) a minimum value for N?

Factoring Integers In O(1) Time

27 09 2011

They say that factoring integers is hard. Well, what do they know – this article presents a program which takes an integer (at compile time) and prints its factors in O(1) time. If the number has multiple factors then just one pair will be printed. If the number is prime, then the number itself, times one, will be printed.

Naturally it is impossible to compute factors of an integer in constant time. The trick used here is called Template Metaprogramming. Template metaprogramming is essentially creating a set of C++ templates which encode a program. Algorithms can be represented by a handful of template metaprogramming idioms – there are idioms for conditionals, recursion, expression evaluation, data passing, and more – and if the template is instantiated anywhere in the code, the metaprogram is executed by the compiler at compile time. At this point it is worth noting that template metaprograms cannot contain mutable values; therefore it is impossible to metaprogram regular index-based loops, but recursion must be used instead. This means that trees can be more economical data structures than linear arrays or lists, because the latter needs much more “stack space” (=simultaneously instantiated template objects) than e.g. tree. Anyway, in order to create a program which apparently factors integers in constant time, a vastly greater compilation time must have passed to compute the actual result, but the result is eventually stored into the program code as a plain old constant value.

The most canonical factoring algorithm is trial division. However, in this article I’ve decided to use the Unusual Recursive Factoring Algorithm instead because it uses more economical tree traversal, as opposed to indexed loop needed in trial division. Alas, my fear was unfounded: it seems that the modern compilers (I used MS Visual C++ Express 2010) no longer have limitations to the number and/or depth of template instantiations which they had when I first tried this code for real.

Anyway, here’s the code.

Solution To Friday Puzzle #4

26 09 2011

Reader yrpe was the first to post the correct answer to Friday Puzzle #4.  This is their answer, slightly paraphrased:

Given any two cards there is exactly one card that competes the set, so the answer is 1/79 .

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.