Programming and Logic Puzzles

We all know that the daily grind of programming for a living can get a little tedious at times.

Joanna: So, where do you work, Peter?
Peter: Initech.
Joanna: In... yeah, what do you do there?
Peter: I sit in a cubicle and I update bank software for the 2000 switch.
Joanna: What's that?
Peter: Well see, they wrote all this bank software, and, uh, to save space, they used two digits for the date instead of four. So, like, 98 instead of 1998? Uh, so I go through these thousands of lines of code and, uh... it doesn't really matter. I uh, I don't like my job, and, uh, I don't think I'm gonna go anymore.*

Okay, so it's not that dreary at my office, but I still like to give my brain something a little bit more stimulating than work once in a while. Like most programmers, I love exercising my mind on interesting coding problems and logic puzzles. It's much cheaper than taking the office printer out to a field (warning: explicit lyrics) once a week, and almost as much fun. Here's a list of my favorite programming and logic puzzle sites that help me keep my brain in shape.

Project Euler - Heavily mathematical programming challenges that can be solved in any language you choose. Many of the problems can be solved without programming at all, but most require a computer. Once you solve a problem you can view solutions that other users have posted. These alternative solutions are often helpful in cracking later problems with similar themes.

The Python Challenge - A series of programming challenges designed specifically to teach the Python programming language. Although any language could be used to solve the puzzles, many of the clues are easier to decipher if you're working in Python.

Ruby Quiz - A collection of challenging programming problems that can be done in any language, but if you want to submit them for evaluation, they should naturally be solved in Ruby. There's a companion book, Best of Ruby Quiz, that discusses possible solutions to selected problems.

Top Coder - Timed programming competitions in a variety of categories (algorithms, testing, design, assembly, and many others) with cash prizes from sponsors such as Microsoft and the NSA. Solutions can be submitted in Java, C++, C#, or VB. Take a look at the match archives to get a feel for what kinds of problems you can expect in competitions. There are also a lot of good tutorials written by moderate- to high-ranking competitors.

UVa Online Judge - Hundreds of problems from past programming contests such as the ACM International Programming Contest. You can submit solutions to the judge in C, C++, Java, or Pascal. Be sure to check out the companion book, Programming Challenges, as well as the new book From Baylor to Baylor, cataloging all the problems used during the 1991 to 2006 ACM-ICPC World Finals.

Sphere Online Judge - Hundreds more problems used in a variety of online programming contests. The best part of SOJ is that you can submit solutions in dozens of different languages (see the list at the top of the problems page to see if your favorite language is included).

C Puzzles - Puzzles on this page explore common traps and pitfalls of the C programming language. Expert C programmers will probably make pretty short work of these problems, but they can be somewhat challenging if you don't know the idiosyncrasies of C.

Facebook Puzzles - A small set of programming problems used by Facebook to evaluate potential hires. You can submit solutions in C++, Erlang, Haskell, Java, OCaml, Perl, PHP, Python, or Ruby.

Google Code Jam - A timed programming tournament where contestants solve algorithmic problems in the language of their choice. I don't know if Google has any plans to hold another tournament in 2009, but you can still check out the problems from the 2008 Code Jam to see how you measure up.

Microsoft Interview Questions - First, let me say that I'm completely biased against the practice of using "brain teaser" questions at job interviews. Many of these questions depend more on a "flash of insight" than on logical thinking or real-world problem solving ability. If you use this style of question to screen potential employees, be warned that you're probably really only testing whether or not a candidate has read similar problems in the past. Having said all that, these questions are still a lot of fun to solve outside a job interview.

wu:riddles - An archive of hundreds of challenging logic puzzles with a wide range of difficulty. Problems are labeled if they require any special knowledge of math, physics, computer science, or chess.

Mindcipher - Bills itself as "The social repository of the world's greatest brain teasers, logical puzzles and mental challenges." There are puzzles in a variety of categories including, Logic, Mathematics, Physics, Lateral Thinking, and Optical Illusions. New puzzles are added frequently, so check back often.


What am I missing? If you don't see your favorite programming challenge or logic puzzle site listed above, please leave me a comment with a URL letting me know where to find it. I always love a new challenge!


Updates from the comments

Thanks to all the readers who left a comment directing me to new (to me) puzzle sites. Here are a few that I'm looking forward to visiting on a regular basis.

Programming Praxis looks like a promising new blog full of programming exercises to "sharpen your saw" on. It looks like new problems have been published on a regular schedule since February. I've already subscribed to the RSS feed.

Code Kata was a short series of problems published in 2007 by Dave Thomas of The Pragmatic Programmer fame. Code kata are "simple, artificial exercises which let us experiment and learn without the pressure of a production environment." Exactly what I'm looking for.

Any Prolog programmers will want to check out The First 10 Prolog Programming Contests (free PDF e-book) and Ninety-Nine Prolog Problems.

If you're interested in organized programming contests, you may want to check out the USA Computing Olympiad or the ACM Programming Problem Archives (many of the problems found here can also be found on the UVa Online Judge, mentioned earlier).

Al Zimmermann's Programming Contests (list of previous contests) present classic computer science problems for programmers to compete for cool prizes. It looks like the contests run from a few months up to a year, so there's plenty of time to enter the current contest.

Anarchy Golf has hundreds of problems and a server that allows you to submit solutions in 69 different languages. This submission reminded me that I had previously forgotten to mention Code Golf. For anyone who isn't familiar, code golf is a contest to see who can come up with the shortest correct solution to a problem. Java Enterprise Application programmers are allowed to play, but Python and Perl one-liners dominate in code golf.

Lastly, as pointed out by a couple of readers, programming and logic aren't the only kinds of puzzles out there. Chess and Go problems can be a fun distraction as well. Chess.com has a daily puzzle that's moderately challenging for casual players, and GoGrinder is a terrific open-source program for practicing Go problems.

Thanks again to everyone who took the time to share their favorite puzzling Web sites. Hopefully everyone's productivity isn't impacted too much in the coming weeks. :)


* If you don't recognize that scene from Office Space, then run, do not walk, to the nearest video store and pick up a copy immediately.

Casting Out Nines

You may already be familiar with the divisibility rule that says a number is evenly divisible by 9 if and only if the sum of its digits is also divisible by 9. For example, I know 3,645 is divisible by 9 without dividing because its digits add up to 18, which I remember from elementary school to be 2 * 9.

This is an interesting rule because it leads to a recursive property of divisibility by 9. Notice that the digits of 18 in the preceding example also add up to 9. If we have a larger number like 13,286,025,801 we can repeatedly apply the same rule until we get down to one digit. Only if that single digit is a 9 is the original number (and every digital sum in between) divisible by 9.

For example, the sum of the digits of 13,286,025,801 is:

1 + 3 + 2 + 8 + 6+ 0 + 2 + 5 + 8 + 0 + 1 = 36

and the sum of the digits of 36 is:

3 + 6 = 9

This process of repeatedly summing the digits of a number until you're left with a single digit is called finding the number's digital root. If the digital root of a number is 9, then that number is divisible by 9.

For small numbers like the ones above it's easy to just do long division to see if a number is evenly divisible by 9, but for extremely large numbers with hundreds of digits, division can be quite time consuming. For example, can you tell me if

153,441,702,921,204,324,780,111,405,711,
801,641,412,504,117,621,135,207,441,603,
126,450,890,010,720,810,243,171,423,583,
110,999,306,450,902,232,414,027,522,126,
087,102,603,909,333,306,252,412,702,011

is divisible by 9? You might be awhile if you try to solve this using long division. I can tell you that this number is divisible by 9, but before you add up all the digits, let me show you a shortcut called "casting out nines." Let's first try it out on the following example, which is a little bit more manageable

1,729,254,036

Start off adding from the left as normal, and for each digit you add, keep a running total.

1 + 7 = 8

8 + 2 = 10

When you reach a total greater than 9, as I have here after the third digit, "cast out" a 9 from the total by simply subtracting 9 from it. In this case our running total of 10 becomes 1.

1 + 9 = 10 (-9 = 1)

1 + 2 = 3

3 + 5 = 8

8 + 4 = 12 (-9 = 3)

3 + 0 = 3

3 + 3 = 6

6 + 6 = 12 (-9 = 3)

If the final total isn't 9 (or 0 after casting out that final 9) then the number is not divisible by 9. Since we were left with a remainder of 3, we now know that 1,729,254,036 is not divisible by 9.

An even quicker method of casting out nines is by grouping the digits that add up to 9 and eliminating them. The sum

1 + 7 + 2 + 9 + 2 + 5 + 4 + 0 + 3 + 6

is much easier to reduce if you group it by digits that add up to 9.

1 + (7 + 2) + (9) + 2 + (5 + 4) + 0 + (3 + 6)

You can cast out these nines at this step before you do any addition at all.

1 + (0) + (0) + 2 + (0) + 0 + (0)
1 + 2 = 3

You can repeat the grouping and casting process as many times as you need before summing the remaining digits.

Now that you know these shortcuts, take a closer look at that monstrous 150-digit number that I showed you earlier. Using the grouping and casting method it shouldn't take more than a moment to reduce even that large a number to see that it is divisible by 9.

Why does the divisibility test even work?

To understand why the test for divisibility by 9 works, we need to use a few properties of congruences. Let's start with the fact that

10 ≡ 1 (mod 9)

which in English says that 10 is congruent to 1 modulus 9, or in plain English that 10 and 1 both leave the same remainder (sometimes called the residue) when divided by 9. (In fact, if the right-hand side of the congruence, in this case 1, is less than the modulus, then the right-hand side is the remainder when the left-hand side is divided by the modulus.) In general,

b ≡ c (mod n)

says that the difference between b and c is evenly divisible by n.

One algebraic property of congruences says that we can raise both sides of the congruence to the same power and the modulus will stay the same (this can be more generally stated as P(a) ≡ P(b) (mod n), where P(x) is any polynomial). Using this property we can say that

10² ≡ 1² (mod 9)

or

100 ≡ 1 (mod 9)

You can substitute any non-negative whole exponent you like.

10⁰ ≡ 1⁰ (mod 9)

10¹ ≡ 1¹ (mod 9)

10² ≡ 1² (mod 9)
10³ ≡ 1³ (mod 9)

...

10ⁿ ≡ 1ⁿ (mod 9)

So 10 raised to any natural exponent will leave a remainder of 1 when divided by 9.

10ⁿ ≡ 1 (mod 9)

This should be intuitively obvious when you consider that

10³ - 1 = 1,000 - 1 = 999 is evenly divisible by 9

10⁴ - 1 = 10,000 - 1 = 9,999 is evenly divisible by 9

10⁵ - 1 = 100,000 - 1 = 99,999 is evenly divisible by 9

...

Another property of congruences says that we can multiply both sides by the same number and the congruence remains unchanged. So starting back at

10 ≡ 1 (mod 9)

we can multiply both sides by any number and still have a valid congruence.

10 * 2 ≡ 1 * 2 (mod 9)
20 ≡ 2 (mod 9)

10 * 5 ≡ 1 * 5 (mod 9)
50 ≡ 5 (mod 9)

10 * 8 ≡ 1 * 8 (mod 9)
80 ≡ 8 (mod 9)

Starting from the following statements (that we showed to be true above)

1000 ≡ 1 (mod 9)

100 ≡ 1 (mod 9)

10 ≡ 1 (mod 9)

1 ≡ 1 (mod 9)

we can multiply both sides of each congruence by any number we like.

1000 * 3 ≡ 1 * 3 (mod 9)

100 * 6 ≡ 1 * 6 (mod 9)

10 * 4 ≡ 1 * 4 (mod 9)

1 * 5 ≡ 1 * 5 (mod 9)

is the same as

3000 ≡ 3 (mod 9)

600 ≡ 6 (mod 9)

40 ≡ 4 (mod 9)

5 ≡ 5 (mod 9)

We can add congruences together as long as they have the same modulus. Adding the four congruences above we get

3000 + 600 + 40 + 5 ≡ 3 + 6 + 4 + 5 (mod 9)

or

3645 ≡ 3 + 6 + 4 + 5 (mod 9)

Doesn't that look like it says that 3645 is congruent to the sum of its own digits modulo 9? Yes, in fact, it does. I deliberately chose the numbers 3, 6, 4, and 5 so that we would arrive back at a familiar example (from the first paragraph of this post), but I could have chosen any digits I wanted. This relationship holds true for any natural number. If s is the sum of the digits of n, then n is congruent to s modulo 9.

n ≡ s (mod 9)

But we're only really concerned with the cases where the sum of the digits is evenly divisible by 9. Another way of stating this is

s ≡ 0 (mod 9)

This brings us to the last algebraic property of congruences that we need to use (I promise, this is the last one). Remember that the transitive property of regular arithmetic says that if a = b and b = c, then a = c. The transitive property of congruences is similar. It says that if

a ≡ b (mod n)

and

b ≡ c (mod n)

then

a ≡ c (mod n)

This is simply saying that if a and b leave the same remainder when divided by n, and b and c leave the same remainder when divided by n, then a and c must also leave the same remainder when divided by n. For a concrete example, consider that

32 ≡ 18 (mod 7) and 18 ≡ 11 (mod 7)

so that

32 ≡ 11 (mod 7)

(They all leave a remainder of 4.)

Since we've already shown that in the general case

n ≡ s (mod 9)

and we know that in the particular cases we're concerned with that the sum of the digits is evenly divisible by 9, or

s ≡ 0 (mod 9)

we can say that in those cases

n ≡ 0 (mod 9)

This means that in those cases where the sum of the digits of n is divisible by 9, the number n itself is also divisible by 9. Precisely what we set out to prove.

A Java Puzzler

A co-worker presented me with the following Java puzzle today (thanks, Josh). Given the following two classes:

public class Base
{
   Base() {
       preProcess();
   }

   void preProcess() {}
}

public class Derived extends Base
{
   public String whenAmISet = "set when declared";

   @Override void preProcess()
   {
       whenAmISet = "set in preProcess()";
   }
}

what do you think the value of whenAmISet will be when a new Derived object is created?

public class Main
{
   public static void main(String[] args)
   {
       Derived d = new Derived();
       System.out.println( d.whenAmISet );
   }
}

Give yourself a few minutes to look it over before reading ahead. It's a really simple example to follow, so no fair compiling and running it to find out. Think you know the answer?

It appeared to most people that the output should be "set in preProcess()". The reasoning went that when the Derived constructor is called, it implicitly calls the Base constructor via a call to super() that the constructor inserts automatically for you. The Base constructor then makes a call to the most specific copy of preProcess() that it can find, the one in the partially constructed Derived class, which sets the value of the whenAmISet member variable.

This, of course, is wrong. If you compiled and ran the code above you found that it prints out "set when declared". So what happened there? Is the Base class preProcess() method getting called? Nope. (Go ahead and put a print statement in each preProcess() method if you don't believe me.)

Here's the sequence of events:

1. The Derived constructor is called.
2. Memory for Derived member variables is allocated.
   
3. The Base constructor is called implicitly.
4. The Base constructor calls preProcess().
5. preProcess sets whenAmISet value to "set in preProcess()".
6. Derived class member initializers are called.
7. The body of the Derived class constructor is called.

Wait, what just happened? At step 6, the Derived class members are initialized after the call to the preProcess() method? That's right. You can't count on the declaration and initialization of member variables being atomic. As you can see from running the example, the initialization of whenAmISet in Declared is over-writing the value that gets set earlier in the preProcess() method.

How do we know this is the right sequence? Let's take a closer look at the significant steps.

1. We call the constructor.
   
2. We know the memory for Derived class member variables is allocated before any line of code is run in its constructor. If this weren't the case then the call to preProcess() in the Base class wouldn't be able to set the value of whenAmISet and print it's value (which isn't in the code above, but you can try it and see that this works).
   
3. Java inserts a call to super() at the beginning of the constructor unless you include it yourself.
4. We know this by looking at the code.
5. Also known by code inspection.
6. The initialization must be happening after the call to preProcess(). The Derived class's preProcess() method is getting called, and it is setting whenAmISet's value to "set in preProcess()". Again, if you don't believe me, print out the value of whenAmISet right after it gets set in the Derived preProcess() method.
   
7. We're calling the default (empty) constructor, so there's nothing more to see here.

You can see the relevant section of the Java Language Specification for a much more detailed explanation of the process of object creation in Java. (Thanks to Weeble for providing this link in the comments.) Note that there's a very similar example to this one on that page if you scroll down to the paragraph starting "Unlike C++..."

So what can we take away from all of this? First, never count on any operation being atomic unless you've tested and proven it to be so (and sometimes not even then). Second, and more to the point, be careful initializing member variables in a method of a derived class if that method gets called by the base class constructor. It might be even better to try and avoid calling methods in your base constructors that are overridden by derived classes, and conversely, avoid overriding methods in derived classes that are called by the constructor in the base class. Be careful if you do, and don't say I didn't warn you about what might happen.


Further Reading

I could hardly finish without mentioning that Joshua Bloch and Neal Gafter wrote an entire book full of similar puzzles called Java Puzzlers: Traps, Pitfalls, and Corner Cases. Check it out if you'd like being your team's source for Java trivia and minutae.

Bylaws of Programming and Technology

Amara's Law - "We tend to overestimate the effect of a technology in the short run and underestimate the effect in the long run."

Amdahl's Law - "The speed-up of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program."

Brooks's Law - "Adding manpower to a late software project makes it later."

Clarke's Three Laws

1. When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
2. The only way of discovering the limits of the possible is to venture a little way past them into the impossible.
3. Any sufficiently advanced technology is indistinguishable from magic.

(See So Quoted: Any sufficiently... for many corollaries to Clarke's Three Laws.)

Classen's Law - "In order to achieve a linear improvement in usefulness over time it's necessary to have an exponential increase in technology over time." Or more succinctly:

Usefulness = log(Technology)

Conway's Law - "Any piece of software reflects the organizational structure that produced it."

Gall's Law - "A complex system that works is invariably found to have derived from a simple system that worked."

Gates's Law - "The speed of commercial software generally slows by fifty percent every 18 months thereby negating all the benefits of Moore's Law."

Gilder's Law - "Bandwidth grows at least three times faster than computer power."

Goodheart's Law - "When a measure becomes a target, it ceases to be a good measure."

Greenspun's Tenth Rule of Programming - "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

Gustafson's Law - "Any sufficiently large problem can be efficiently parallelized."

Hofstadter's Law - "It always takes longer than you expect, even when you take into account Hofstadter's Law."

Kerckhoffs' Principle - "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."

Knuth's Law - "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

Kranzberg's Six Laws of Technology

1. Technology is neither good nor bad; nor is it neutral.
2. Invention is the mother of necessity.
3. Technology comes in packages, big and small.
4. Although technology might be a prime element in many public issues, nontechnical factors take precedence in technology-policy decisions.
5. All history is relevant, but the history of technology is the most relevant.
6. Technology is a very human activity - and so is the history of technology.

Linus's Law - "Given enough eyeballs, all bugs are shallow."

Metcalfe's Law - "The value of a system grows as approximately the square of the number of users of the system."

Moore's Law - "The number of transistors that can be inexpensively placed on an integrated circuit doubles roughly every two years."

Norvig's Law - "Any technology that surpasses 50% penetration will never double again (in any number of months)."

Parkinson's Laws

• Work expands so as to fill the time available for its completion.
• Data expands to fill the space available for storage.
• Programs expand to fill all available memory.

Parkinson's Law of Triviality - "Organizations give disproportionate weight to trivial issues."

Proebsting's Law - "Compiler advances double computing power every 18 years."

Reed's Law - "The utility of large networks, particularly social networks, can scale exponentially with the size of the network.

Schneier's Law - "Any person can invent a security system so clever that she or he can't think of how to break it."

Wirth's Law - "Software gets slower faster than hardware gets faster."

Zawinski's Law - "Every program attempts to expand until it can read mail. Those programs which cannot so expand are replaced by ones which can."

How do you test a random number generator?

Human beings are notoriously bad at generating random numbers and sequences. If you ask someone to randomly choose a number between 1 and 20, the numbers they're most likely to choose are 7 and 17. Similarly, if you ask someone to simulate a series of coin flips by writing down a random string of the letters H and T, you'll see very few long sequences of either heads or tails, which would occasionally appear by chance in sequences of real coin flips.

People are just as bad a determining whether an existing sequence is random. Look closely at the following two images.


Which one do you think looks more randomly distributed? If you read the article that the images link to, you already know that most people say the first image looks more random because the points are more smoothly distributed. This is exactly the property that makes it less random than the second image, which has more instances of points in tight clusters. A real set of random data points wouldn't be as evenly spaced as the first image.

Computers are much better than people, but by no means perfect, at generating sequences of random numbers. A number or sequence is said to be random if it is generated by a non-deterministic and unpredictable process. Since computers are inherently deterministic machines, this means that no computer can ever algorithmically generate a sequence that is truly random. They can come very close, though, with the help of a class of algorithms known as pseudo-random number generators (PRNG).

For a programmer writing a PRNG, or software that relies on one, testing its randomness reveals a unique problem. Unit testing software compares the output of a function to an expected value. If the output is expected to be unpredictable, you have a testing dilemma.

To make matters worse, there is no way even theoretically to prove that a sequence was generated randomly. Luckily there are statistical methods that are useful for revealing when a sequence is not random. Let's take a look at a simple PRNG, then use a common statistical method, the Monte Carlo method, to compare its effectiveness to a standard software library implementation.

A Naive PRNG

One of the oldest algorithmic methods for generating pseudorandom numbers is called the linear congruential method. Here's a simple example implementation:

public class NaiveRandom {
   private int x; // seed

   private int m = 134456; // modulus
   private int a = 8121;   // multiplier
   private int c = 28411;  // increment

   public NaiveRandom()
   {
       x = 0;
   }

   public NaiveRandom(int seed)
   {
       this.x = seed;
   }

   public double next()
   {
       x = (x * a + c) % m;
       return x / (double)m;
   }
}

The original pseudocode and constants in the code above come from an example given in Statistical Mechanics by Werner Krauth. As Krauth explains in his book, these values are good for studying the algorithm, but not great if you need really random values. In the following section we'll see how it compares to Java's built-in PRNG.

The Monte Carlo Pi Program

Take a unit circle inscribed in a square.


The area of a circle is given by the formula

A = πr²

Since the radius is 1, the area is equal to π. Since the diameter of the circle and the length of a side of the square are both 2, the area of the square is 4. The ratio (which we'll call ρ) of the area of the circle to the area of the square is

ρ = π / 4 = 0.785398164

If we select a random sample of points from the square, the proportion of those points lying inside the circle should be equal to ρ. We can multiply this proportion by 4 for comparison to a library value of π. If the random number generator is close to truly random, then the closer our approximation should be to the actual value of π.

We can simplify the calculations necessary for the test if we only concern ourselves with one quadrant of the square. This is possible because it's the proportion of points inside the circle to those inside the square that matters. The proportion of such points is the same in each quadrant as it is in the whole. If we say that the center of the circle is at point (0, 0), then we need only generate random points (x, y) where x and y are both between 0.0 and 1.0. This is the standard output range for most PRNGs, like Java's Random class. Points that lie within the circle will be those that obey the inequality

x² + y² ≤ 1

Here is the Java code for a Monte Carlo Pi simulation.

import java.util.Date;
import java.util.Random;

public class MonteCarloPi {

   public static void main(String[] args) {
       // seed for NaiveRandom
       Date now = new Date();
       int seconds = (int)now.getTime();

       // create random number generators
       NaiveRandom nrand = new NaiveRandom(seconds);
       Random rand = new Random();

       // total number of sample points to take
       int numPoints = 10000;

       int inNaiveCircle = 0;
       double xn, yn, zn;
       // xn and yn will be the random point
       // zn will be the calculated distance to the center

       int inRandCircle = 0;
       double xr, yr, zr;
       // xr and yr will be the random point
       // zr will be the calculated distance to the center

       for(int i=0; i < numPoints; ++i)
       {
           xn = nrand.next();
           yn = nrand.next();

           xr = rand.nextDouble();
           yr = rand.nextDouble();

           zn = (xn * xn) + (yn * yn);
           if(zn <= 1.0)
               inNaiveCircle++;

           zr = (xr * xr) + (yr * yr);
           if(zr <= 1.0)
               inRandCircle++;
       }

       // calculate the Pi approximations
       double naivePi = approxPi(inNaiveCircle, numPoints);
       double randomPi = approxPi(inRandCircle, numPoints);

       // calculate the % error
       double naiveError = calcError(naivePi);
       double randomError = calcError(randomPi);

       System.out.println("Naive Pi Approximation: " +
                naivePi + ", Error: " + naiveError);
       System.out.println("Random Pi Approximation: " +
                randomPi + ", Error: " + randomError);
   }

   static double approxPi(int inCircle, int totalPoints)
   {
       return (double)inCircle / totalPoints * 4.0;
   }

   static double calcError(double pi)
   {
       return (pi - Math.PI)/Math.PI * 100;
   }
}

Results

Run the simulator several times and you will see that Java's built-in PRNG seems to outperform the naive implementation, but not by much. Neither performs particularly well, but Monte Carlo simulations are only expected to be close, not exact. Here are my results after ten runs of the simulation.

Naive Random		Java Random
Pi	Error(%)	Pi	Error(%)
3.122	-0.6237	3.1308	-0.3435
3.1516	0.3185	3.1332	-0.2671
3.1272	-0.4581	3.1352	-0.2035
3.1692	0.8788	3.1352	-0.2035
3.1524	0.3440	3.1416	0.0002
3.1168	-0.7892	3.1340	-0.2417
3.1724	0.9806	3.1040	-1.1966
3.1612	0.6241	3.1244	-0.5473
3.1448	0.1021	3.1428	0.0384
3.1052	-1.158	3.1628	0.6751

At least a small part of the imprecision of these results can be attributed to the fact that I only took 10,000 random points in each sample. A rule of thumb in Monte Carlo simulations is that for every 100X increase in data points, you'll get a 10X increase in the precision of your results. Since I took only 10,000 random points (100 * 100), I only got 2 digits of precision, with the third digit fluctuating.

Try increasing the number of random points to 1,000,000 and you should see that the third digit remains fixed over several runs of the program. The really interesting thing revealed is that our naive implementation continues to perform nearly as well as Java's built-in PRNG. This leads us to the conclusion (which can be easily verified) that Java's PRNG uses the same linear congruential method for generating random numbers as our naive implementation. The only significant difference between the two is that Java's implementation will be able to generate much longer sequences of random numbers before it starts to repeat itself.

Further Investigation

As I mentioned before, there are many statistical tests that can be used to measure the relative randomness of a sequence. I've only covered one of those tests in detail, but there are libraries available like the Diehard Battery of Tests of Randomness and ENT that include a wide variety of tests, and guidelines for interpreting them. If your application depends on randomness, I recommend evaluating your random number generator with one of these test suites.

Rolling Sevens

What's the probability of rolling a 7 on one roll of two standard six-sided dice? To make it easier to visualize, here's a listing of all of the different outcomes of rolling two six-sided dice.

(1,1)	(1,2)	(1,3)	(1,4)	(1,5)	(1,6)
(2,1)	(2,2)	(2,3)	(2,4)	(2,5)	(2,6)
(3,1)	(3,2)	(3,3)	(3,4)	(3,5)	(3,6)
(4,1)	(4,2)	(4,3)	(4,4)	(4,5)	(4,6)
(5,1)	(5,2)	(5,3)	(5,4)	(5,5)	(5,6)
(6,1)	(6,2)	(6,3)	(6,4)	(6,5)	(6,6)

If you look at the long diagonal starting in the bottom left, you can see that there are six ways out of a possible thirty-six to reach a total of exactly 7.

So for two six-sided dice the probability of rolling a seven is

P(7) = 6/36 = 0.1667

Or about one in every six tries.

That question was too easy, so let's make it a little bit tougher. What's the probability of rolling seven 7s in a row? Okay, it's not that hard if you know how to calculate the probability of independent events. You just need to multiply the probabilities of each event. In this case we want to multiply 0.1667 by itself seven times,

0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667 * 0.1667

or we can just raise it to the 7th power.

(0.1667)⁷ = 0.0000036

You can see that rolling seven 7s in a row has some pretty long odds. That will only happen about 36 times in 10 million tries!

But what if you've already rolled six 7s in a row? What's the probability of rolling a seventh 7? Before we do any calculations, would you say that the odds are pretty good or pretty bad of getting a seventh 7?

If you think the probability is extremely bad, you're falling for a very common cognitive bias called the Gambler's fallacy. This fallacy accounts for the belief that a streak of good or bad luck is "due" to change. A gambler who has had a long streak of losing hands in blackjack might decide to increase his bet, banking on the feeling that his luck is about to change.

The Gambler's fallacy arises from out intuitive sense that things have a way of "evening out" in the long run. The truth is that over the very long run, things do even out. This is called the Law of large numbers. If I flip a coin a million times, I can expect to get reasonably close to half-a-million heads. But if I flip the same coin only ten times and get ten heads in a row, the probability of seeing a head on the next flip is still exactly one-half. The Law of large numbers only applies to the average of a large sample, not to individual coin flips, hands of blackjack, or rolls of the dice. The coin (or the cards, or the dice, or the universe for that matter) doesn't remember the result of the previous trials, and therefore cannot be influenced by them.

Oh, I almost forgot, the probability of getting that seventh 7 after rolling six in a row is 0.1667, exactly the same odds as getting a 7 on any other roll. The dice have no memory.

Programming and Experimentation

Give a man a fish and you feed him for a day. Teach a man to fish and you feed him for a lifetime.

-- Chinese Proverb

In a recent post, Great Developers Are Not Afraid to Experiment, Scott Selikoff talks about the fear and insecurity felt by many inexperienced software developers. Scott talks about his experience as a moderator over at JavaRanch, citing the frequency of questions asking "What would happen if I executed the following code?"

Many times the author of such posts can answer the question by copying and pasting his/her code into a Java main() method and running it. Some might chalk these posts up to being lazy, but, clearly, taking the time to write a post on a message board - often signing up as a member for the first time - takes some amount of effort as well. With that, I’m going to be go with the assumption developers avoid experimenting with code because they are scared or unsure of their own knowledge.

Back in college I took a job tutoring students in the introductory computer science courses and I came to the same conclusion that Scott does in his article. I would frequently have students bring code to me and ask me what I thought of it. Some would even go so far as to ask me if I thought their code would compile. I would never answer this question directly (despite Head First Java repeatedly urging me to "Be the Compiler"), but would instead patiently show them how to answer it for themselves. These students weren't lazy, they were scared. In many cases it seemed like they were more scared of being wrong than they were of not knowing the answer. They hadn't learned to experiment yet.

It's important to understand this fear if you're in any kind of position to help people get past it, whether you're a teacher, a writer, a mentor, or just a guy who answers a lot of questions on a programming Q&A web site. If you're a really good programmer, one of your key personality traits is probably an innate sense of curiosity (I'm generalizing, but take a look around at the good programmers you know and see if you disagree). You probably couldn't stop experimenting if you tried. For those of us who have the curiosity trait, it can be puzzling when we encounter someone who lacks it.

Luckily, curiosity is contagious. If you show someone how experimentation works in programming, and you're enthusiastic about learning with them, they might catch the bug from you. I had very few students who were disappointed that I wouldn't just tell them the answers to their programming assignments. Most of them wanted to learn how to do it for themselves once they were convinced that they could.

If you are a teacher or a mentor, the best thing you can do for your student is show them how to find answers on their own. Teach them how to find out what a compiler warning means (don't tell them what it means, even if you know). Teach them how you'd write a test to exercise a tricky piece of code. Teach them how the debugger works.

As the proverb says, "Teach a man to fish..."