What are the best programming puzzles you came across?

Question

Every single programmer worth his salt is inspired by great programming puzzles. Some puzzles are intended to sharpen your analytical abilities while some others make your programming abilities better.

Programming puzzles are the soul of infotainment in the programming community.

What are your favorite programming puzzles?

For the validity of this question, you may want to check out: Posting programming/algorithmic puzzles on SO

EDIT (From Rob Cooper - NOT OP)

Can we please not have lots of links for "Project Euler" and the like, post the "ACTUAL" puzzles that you find difficult/good - Please get CONTENT on StackOverflow, not just links.

Answer 1

http://robocode.sourceforge.net/

Make you robot not die to the other robot.

Very simple to say, nearly impossible to do.

Answer 2

Project Euler has series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.

edit: why it is so bad to copy text from the link. I just wanted to post the link and add little description if someone new doesn't know this site. I think those problems is fun to solve with different programming languages. Feel free to edit or delete this post.

Answer 3

Joels Fizz Buzz.

Not because it is a challenge however, but because it makes it simple to cut the chaff on whom should not be working as a programmer.

Additionally, there is the challenge in writing a fizzbuzz that nobody can understand but still works perfectly, and trying to see whom you can scare with code that should be simple.

Answer 4

I find the best problems to sharpen my problem solving skills to be real world problems. Once a friend asked me to look at the game "Magic the gathering" and make a better way for him to find specific cards. So I figured out a way to get a complete listing of cards in the game and fed it to a little custom parser than can direct the important attributes to a spread sheet or a database(never tested that part though). The game has like 15000 with a whole host different attributes, advantages, disadvantages, etc...

So this problem was very unique and interesting to work on. Granted I enjoyed the game already but, adding a new layer of logic and problem solving was an illuminating experience.

Answer 5

I liked the one with chessboard and question how many "queens" (or was it "bishops"?) can you place on it so they cannot attack each other. Normal computing would take a lot of time, but smart data structures made the trick. I think it's some classic puzzle so it can be googled...

Answer 6

As a data structure question I enjoy asking people how they would define the structures needed to support the question:

How would you find a needle in a haystack?

I look for data structures like:

• Haystack class
  • derives from some sort of IEnumerable<IFarmObject>
• Hay class
  • implements IFarmObject
• Needle class
  • implements IFarmObject
• Searcher class
  • has Find(IEnumerable<IFarmObject> objectToSearch, Type typeOfObjectToSearchFor) method

I can then take it a bit further depending on the data structures that they come up with by asking them to implement in code the data structures they defined and the Find method that they described.

Answer 7

The puzzle I like is a great interview question. Count the set bits in a byte. Sounds simple right? The follow up is, how can you make it faster? Pretty soon you asking whether it's faster to do it in tight assembler running in level 1 cache, or whether a look-up table generated at compile time is faster.

Answer 8

The Eight Queens or N Queens problem is a very interesting algorithmic exercise that I have been asked to solve on a white board during a technical interview. I would not ask this to an interview candidate without prior warning or unless they were interviewing for a senior developer role.

The basic problem statement is:

Given N Queens place count the number of different ways they can be placed on an N x N board so that no queen can attack another queen given one move.

The problem requires an algorithm that implements backtracking:

• place a queen in column 1 in the first square from the top
• place a queen in column 2 in the first square
• check if queens are safe if not move queen in column 2 down one square
• if queen in column 2 can not be placed on the board go back to queen in column one and move down one place
• restart process with queen in column 2
• do this process for each column until a solution is found
• backtrack as far as you have to each time a queen can not be placed

Heuristics (rules of thumb) can also be used to greatly improve the performance of the basic implementation. So if you are testing someone on algorithmic implementation or development this is a great place to look for how they can develop heuristics.

For instance;

• queens can not share columns, rows, or diagonals so you can immediately eliminate all cases where this is the case
• given one solution you can mirror the board to find additional solution without actually computing them, the same is true for non-solutions.

This problem can also be easily tweaked by asking for solutions with other types of chess pieces (rooks, bishops, knights, etc...). Or even a combination of different chess pieces.

Answer 9

One of my favorite programming puzzles was the one given to volunteers as part of an informal study on the efficacy of various programming languages (original here).

A synopsis of the task:

• Each letter in the English alphabet corresponds to a single digit, similar to how characters are mapped on a phone.
• You get a dictionary of words, and an input set of phone numbers.
• Your software must, for each phone number, try and construct a string out of words in the dictionary, and display every possible permutation.
• Where no words are available, a single digit may be used, but never more than one digit in succession.
• There are few other minor rules and a very comprehensive example to resolve ambiguities in the spec.

The beauty here is that this problem is trivially solved in any number of ways; a good programmer should be able to complete the task in 2-4 hours, but the variability in the solutions is astonishing. Some exhibit very good performance, some exhibit very low memory utilization and some are merely elegant, but the results of this programming exercise alone can IMO give a very good gauge of the quality of a programmer. Which data structure and algorithm was chosen? How well-factored is the code? Are corner cases handled properly?

Plus, it's genuinely fun to solve...

Answer 10

The Seven Bridges of Königsberg is a great algorithmic problem as it rely on graph theory for a solution. It is also historically relevant as it lead to Euler's introduction of graph theory to mathematics in the 1700's.

The basic problem statement is:

A city is built on boths sides of a river with two islands between the east and west side of the city. Seven bridges connect the islands to each other and the mainland, the two sides of the city are also directly connected. How can someone walk around the city and cross each bridge only once?

This is somewhat of a trick question in that there is no actual solution. If the above problem is expressed as a graph you will see that each node in the graph has an odd number of edges. For this problem to be solvable at most two nodes source and destination can have an odd number of vertices, the reason for this is that as you travel from one island to another you need a coming and a going bridge. If there are an odd number of bridges you can come and go and come but you can not leave again.

Because there are 4 nodes and you only need to introduce an edge to two of those nodes for a solution to be possible the introduction of an 8th bridge to the question makes it solvable.

Answer 11

The function rand5() returns an integer between 1 and 5, inclusive (that's 1,2,3,4,5), with equal probability. Use rand5() to create a function called rand7() that returns an integer between 1 and 7, inclusive, with equal probability.

Sounds easy, but it's not. Assume that rand5 generates very high quality random numbers. Can you write a rand7 that has the same randomness quality (e.g. even distribution AND randomness)?

Answer 12

There are many different kinds of problems that I've found interesting.

First there are those that are interesting because solutions use interesting techniques. For example the Hamming sequence is the list of positive integers whose only factors are 2, 3, and 5 (repeated any number of times. It starts off 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20... However it gets more sparse, for instance the 2999th Hamming number is 278,628,139,008. What is the 5000th number in the Hamming sequence? If you wish to see the techniques behind a solution discussed, read Infinite Lists in Perl.

Then there are problems that are fun because there are many possible solutions. An example was the person who had an array of positive integers and wanted to break the array into n columns of as close to the same length as possible. Note that the order does not change, you are only breaking up the list. See Puzzle: need a more general algorithm for where this was asked on another site, and many resulting attempts at solutions of different levels of efficiency. (The most efficient was in another thread at Re: Balance columns.)

There are problems that are fun because they look impossible. For example write an algorithm that will break a list of integers into two lists whose sums are as close to even as possible. It should always be right, and should be able to handle a list of 100 integers of size 1-500 in reasonable time on a PC. There is an obvious exponential solution that won't work. If you search, you will find that solving this implies a solution to the Partition Problem, which is NP complete. Yet, believe it or not, the problem as stated is solvable.

Then there are arbitrary constraints. See the many golf problems that are out there. To state a simple one, suppose we have two arrays. The first is an array of characters. The second is an array of words made out of those characters. If the first array defines some alphabet in order (it might not be sorted in ASCIIbetical order), write a function that takes references to both arrays and returns the second array in "alphabetical" order. See Golf: Arbitrary Alphabetical Sorting for a series of ever better solutions in Perl.

Answer 13

Write a program which outputs its own text.

Reading source code from file and output it to console is inappropriate solution.

Two variations:
1. Character codes can be used.
2. Character codes can NOT be used.

This puzzle is also known as quine.

Answer 14

Using 2 6-sided dice, be able to show all the days in a 31-day month.

What numbers do you put on the dice?

Answer 15

I like the classic, detect a loop in a singly-linked list. This puzzle is just easy enough to ask a candidate in an interview, and have them solve it iteratively on the spot. By iteratively, I mean that most candidates will first come up with an algorithm that is slow or memory intensive, or both. For example:

1. Create an empty set of nodes visited
2. Begin walking the list
3. For each node visited, check if it has been visited before by looking in the set
4. If it has, you have found a loop
5. Otherwise, add this node to the set
6. If the next node is null, you are finished and the list has no loop
7. Get the next node and GOTO 2

This solution executes in O(n * log(n)) time and uses O(n) memory. Not great. Other crummy solutions exist, but a good solution runs in O(n) time and uses O(1) memory.

Answer 16

As far as I know, this puzzle is solvable in C language, but I think it is possible to solve it in other languages too.

You have two variables X and Y, and you have to exchange values between those two variables without using a third variable.

a) try first with numbers: X = 10, Y = 20 b) then with strings: X = "hello", Y = "goodbye"

Answer 17

This is a good one.

A census taker came to a house where a man lived with three daughters. "What are your daughters' ages?" he asked.

The man replied, "The product of their ages is 72, and the sum of their ages is my house number."

"But that's not enough information," the census taker insisted.

"All right," answered the farmer, "the oldest loves chocolate.

What are the daughters' ages?

Answer 18

Find the most common entry in an array

Answer 19

The puzzle I like the most goes like this: You have a read only array with n + 1 integers that are in the range 1..n, find one integer that appears at least twice in this array in O(n) time and O(1) extra memory.

Answer 20

My favorite problem is given a binary tree attach a integer weight >= 1 to each leaf such that the sum of the weight in the left and right sub tree of every non leaf node is equal. What is the minimal amount of weight needed to make every node balanced?

Answer 21

It's not a single puzzle, but I've really been enjoying my time spent on the ones from Project Euler.

So far easily my favorite has been problem 15, as I ended up spending several hours deriving the formula to solve it and had some cool realizations and learned quite a bit in the process (I wont give anything away here;)).

---

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner (See link for picture).

How many routes are there through a 20×20 grid?

Answer 22

Given a list of words, find two pairs of words where the pairs are permutations on each others' letters.

For example, if the words are U.S states then one pair is ("south carolina", "north dakota") and the other pair is ("north carolina", "south dakota"). (This is a nice trivia question by itself. It's funny because people try to permute states' letters and when they are told the answer they are surprised how simple it is)

The solution is to make a canonic representation of the letters in each pair (sort the letters). Then sort all the pairs by their sorted-letters and see if then any two consecutive pairs have the same sorted-letters. The sorted table should be keeping indexes/pointers to the original pairs so you will find the answer.

Answer 23

I messed around with writing a sudoku solver and grader for a while. The grader is the hard part. There are many interesting opportunities for puzzle solving when coding a puzzle solver. One thing that comes up in sudoku is finding the canonical form of a solution. The canonical form is used for grading and comparing.

You can swap all occurrences of any two digits and get an equivalent board. You can swap any two rows or columns in a box, or any two box rows or box columns, and the board will be equivalent. Every board has roughly 600 billion equivalent forms and the one that compares least as a string is the canonical form. It will start with 1 through 9 in the first row.

So the puzzle is simply to write an efficient algorithm for finding the canonical form of a sudoku board. You do not need recursion. You do not need much storage.

With a 9x9 board there are roughly 5 billion canonical solutions with 6^8*9! equivalent forms each. For a larger board the complexity of finding a canonical form quickly grows.

Answer 24

Given only a random bit-generator which is biased (probability of 0 or 1 is not 50/50), can you create a perfect random bit-generator (probability of 0 or 1 is exactly 50/50)?

You don't know anything about the exact probabilities of the bits other than they are > 0%

Answer 25

Answer 26

Has anyone seen the Toughest Developer Puzzle Ever? Looks like they just launched 100 new levels yesterday. Pretty cool stuff.

http://toughestdeveloperpuzzleever.com

Answer 27

This is an interesting problem I came across -

You are in the center of a room which has balloon of various sizes at random location. You have a high powered laser gun which when fired will burst all the balloons which come in its path. So the question is , how will burst off all the balloons in minimum number of shots fired from the laser. You are given the coordinates (x,y,z) of the balloons and also the radius of each. You can assume the laser to be at position (0, 0, 0)

Answer 28

A couple of my favourite algorithmic puzzles are:

1) Given an array a1 a2 ... an b1 b2 ... bn rearrange it to become b1 a1 b2 a2 ... bn an in O(n) time and O(1) space.

2) An O(logn) (integer arithmetic operations) algorithm for computing the nth fibonacci number.