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 SPOJ 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.


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 Prolog isn't your thing, you can also do the 99 Problems in Haskell, Python, Scala, or Lisp.)

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.

Programming Puzzles & Code Golf is a Stack Exchange site originally started for gathering user-submitted Code Golf problems and the shortest solutions in various programming languages.  The site's scope later expanded to include any programming puzzle, not just Code Golf style questions.  Follow the code-challenge tag for general programming puzzle questions. 

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.
** LOL, "video store"! What am I, like 60? Get it from Netflix.

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."

Sturgeon's Law - "90% of everything is crap."

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."