# Classic Computer Science Puzzles

Software developers do have a proclivity for puzzles. Perhaps that's why books like To Mock a Mockingbird exist. It's a collection of logic puzzles which is considered an introduction to lambda calculus, one of the core concepts of Lisp.

This is a companion discussion topic for the original blog entry at: http://www.codinghorror.com/blog/2007/09/classic-computer-science-puzzles.html

Interesting way to tie puzzles back to what programmers really do. However, I still think even these are useless for most jobs since these puzzles focus on comp sci problems and hardly any jobs do. Most jobs are about building CRUD application. What good is puzzle solving if you job revolves around storing stuff in a database, reporting on it and transforming it?

Re: random “solving” the two generals problem

The problem isn’t asking for a solution that works most of the time, it’s asking for a solution that works no matter what. The whole point is that such a solution is impossible.

It’s definitely possible (and not very hard) to come up with a strategy that works 99.99999% of the time (for as many 9s as you want).

Jeff,

I’m a big fan of Dennis Shasha’s “Dr. Ecco” series of books and magazine puzzle columns. If you’ve never read any of them, I’d encourage you to take a look.

It’s not that LISP is dense and impenetrable, although Common Lisp took it a good long way down that road. Unfortunately, many Lisp programmers were dense and impenetrable.

Lisp had a lot of nice features that never got used because Lisp vendors never understood their market, outside of research universities.

I remember one called the “Sleeping Barber” problem, related to communication between separate processes.

http://en.wikipedia.org/wiki/Sleeping_barber_problem

If I recall correctly, the eight queen problem is not about how many queens can be placed, the number of queens is always N for a NxN chess board. The problem is how to place the queens, and how many different solutions there are.

Here’s a great history of the traveling salesman problem.

http://www.tsp.gatech.edu/index.html

If you prove this is a NP-complete problem (not just NP-hard), you could win a \$1,000,000 dollar millennium prize:

## one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like [travelling salesman] certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer.

Boston only has two outbound routes and New York only has inbound routes, therefore the problem can not be solved.

Also, the two generals problem is easily sovlable in the real world - you acknowledge the fact that a transaction may fail, and include sufficient auditing and administration tools to allow detection and repair of failures. And for those who haven’t studied the real world, the probability of six thousand messages being lost (after the first one is lost, given a dumbass with a backhoe hitting the network link at the wrong time) is approximately 100%. Any system designed with a suitable strategy to cope with a failure (whether the probability of failure is 99.999999999% or 0.000000001% will be equally effective.

The problem can not be solved - but in the real world you can always have a plan B to account for the reality.

Honestly, you can whinge about “probability” all you like, but if “the chance of failure is the same as your chance of winning the lottery” is your justification for not providing a strategy to cope with errors then I don’t want to use your software. And if you do provide quality software, then you’re acknowledging that there is always a possibility of failure.

Besides, if you try the “6 acknowledgement messages and then commit” approach to transactional reliability, your system will be a lot slower than most, and lets be fair - the odds of a network outage that can’t be automatically repaired pretty quickly is already quite low.

I’ve a coworker dealing with management of an outsourced program who is backtracking on just about everything she promised in writing, including giving the money back.

I’d love to see a similar problem used for the yet-to-be-hired programmer to figure out.

And honestly, isn’t dealing with people one of the hardest puzzles out there

Because of the nature of the situation, truthful and accurate, I can’t post my name, but I’m a regular reader.

as for other “fundamental” puzzles - perhaps the classic “conway’s game of life”? not an actual puzzle (althought you can create puzzles using it) but quite scientific and entertaining at the same time.

Einar, thanks for the correction. I didn’t quite finish writing the Eight Queens description up and I didn’t realize it before I pressed the post button. The question is not “how many queens can exist on a chessboard of a given size without attacking each other” (although that’s interesting, too).

the two generals problem is easily sovlable in the real world -

If two generals is too easy, you should move on to byzantine generals.

http://en.wikipedia.org/wiki/Byzantine_fault_tolerance

You now have (n) generals who must decide to attack unanimously. And here’s the other twist: some of them are traitors.

I think all job interviews are missing one essential skill test: can the person touch type?

There’s something wrong if you work in tech and you still have to hunt-and-peck and look at the keyboard while you type.

Screw hiring smart people – hire people who don’t make typos.

Sierpinski Triangle
Recursion
http://en.wikipedia.org/wiki/Sierpinski_triangle

Short of spending a day looking over the shoulder of a candidate, there really is no remotely save way to be sure that they are capable enough to hire. Gets even worse if you have to hire someone to do something that YOU YOURSELF don’t understand (aka some expert sub-field). It’s odd that programmers with their desire to solve problems haven’t come up with a decent hiring solution yet.

By the way, you forgot the “sleeping barber”, a classic programming problem to process communication and synchronicity (is that a word ?) that involves deadlocks and starvation.