1.
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.cyields 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.