Fun programming problems

Here are a few fun programming problems. Variations on them are also potentially fun. These vary greatly in difficulty. Most of them are not original with me.

Background problem: Insert + or - signs anywhere between the digits 123456789 in such a way that the expression evaluates to 100. The order of the digits must not be changed.

Sample solution: 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

Programming problem: Write a program to output all solutions.
[This is various problems, depending on the programming language and other constraints.]

2. Write a program whose output is its own text. E.g.

	./a.out | diff - self.c
yields no output. Do not consult the program text directly; e.g. "cat" is not a solution. The program text is the output of the algorithm in the program.

More than the above, this one is a different problem for each programming language. Another variant: Write a pair of programs, each of whose output is the other. A sub-variant: The two programs should be in different programming languages.

3. Write a program to play a perfect game of Tic-Tac-Toe: to make its move, it plays all possible games to the end, recursively. (So you choose a move which inevitably leads to a win, if possible; else a move which leads sometimes to a win and sometimes to a draw; else at least a move which never leads to a loss.)

4. A topological sort is an interesting program to write. Look up algorithms. You'll want to do this in a programming language which has associative arrays.

5. Think of some clever ways to cast the "nim" game-playing algorithm as a shell script. How do you do an 'xor' in shell script? I have a short solution which I think is clever, using 'dc' to convert between base 10 and binary, but not for any other purpose.

6. Write atoi(). It has to work for the minimum integer too, without overflowing.

7. If you start with $1 and, with each move, you can either double your money or add another $1, what is the smallest number of moves you have to make to get to exactly $200?
(write a program to calculate this)

8. Many basic unix utilities are fun to write.
Also, write "diffbar" which runs "diff" with the -D option and turns the output into something which shows all lines with change bars (or similar) as applicable.

9. Randomize the sequence of lines in a file (work from stdin to stdout). Your random selection must be completely uniform, i.e. all n! possible outputs are equiprobable.

10. Choose a sequence of the numbers from 1 to 10 such that no two adjacent entries are adjacent numbers. Your random selection must be completely uniform amongst the possible outputs.
There is a brute force algorithm which simply chooses a permutation of the numbers from 1 to 10 (like the previous problem) and checks whether it satisfies the other constraints, and if not, it just tries again. This does not have bounded running time. You can improve on it. In fact I believe that it is possible to write a solution with no backtracking at all, but I'm not sure how difficult this is. I have to solve this one again myself.

11. Write a program which generates all permutations of the sequence of characters in a supplied word. Write a shell script which compares this to /usr/share/dict/words and thus solves "jumble" puzzles.