CS105  		Final Project		Due: 12:30 12/9/96

Choose one of the final projects from the list below.  By class on
11/26, you should hand in a statement of which project you have chosen,
and a  design document  that describes the design of your program.  The
design document should describe the classes and functions you plan to
write.  You should state what functions will be in each class (as well
as listing the functions that won't belong to any class), and tell what
parameters each function will need.  You should not worry about actually
writing the functions for the design document.

The program itself is due during the lab period on 12/8.  At this time,
you should hand in your program, and give a short (3-5 minute)
demonstration for me during the lab period (I ll hand out a sign-up
sheet for time slots later).  The demonstration will count in the grade
for the project, so you should prepare an example that will show off
your program.

Projects 1 and 2 require that you read input one character at a time -
to do this, just create a variable of type "char" (for a single
character), use the >> operation to read input into it.  This will get
the next non-blank character - fortunately you will not need to do
anything with blank spaces in these projects.

1) Game playing program

Write a program to play a simple game, such as tic-tac-toe.  Use a game
with only a few moves (unlike chess), and without hidden information or
random events (unlike poker).  The computer must be one player in the
game, and choose its moves reasonably well.

The basic idea behind most game playing programs is this:  we choose a
move by considering every possible move, and trying to figure out what
the final outcome will be if we make that move and both players continue
to play without making mistakes.  If there's a move that we can make
that will lead to a win, we make that move (if there's more than one
such move, we can pick any of them);  if there's no move that leads to a
win, but there is a move that produces a tie, then we pick that move. 
Otherwise we know we will probably  lose, and can either pick any move,
or resign.

We predict the final outcome of each move as follows:  For a single move
can end the game (by producing a win, loss, or tie immediately),
predicting the final outcome only requires that we are able to detect
wins, losses, and ties.  In other cases, we predict the move that each
player will make at each step in the game, and see what the final
outcome is.  Note that our algorithm for choosing a move can be used for
predicting the moves of a player who does not make mistakes - we just
need to figure out what move our algorithm will make at each step in the
game.

You do not have to provide a fancy graphical interface to your program -
just have it print out moves with cout.
  2) Programmable calculator

Write a prefix notation calculator that allows the operations +, -, *,
and /, and allows user-defined functions.

Start by allowing only the four basic operations on  integers.  Note
that, with prefix notation, the operation is given first; for example,
to add 2 and 4, we use  + 2 4 ; to add 7 to the product of 5 and 3,  + 7
* 5 3.  You may find it easier to use a special character (such as #) to
indicate that a number is the next item to be entered.  For example, you
would write those expressions as  + #2 #4  and  + #7 * #5 #3.  You may
restrict input to single-digit integers if you wish, but you should
allow arbitrarily complicated or simple prefix expressions (for example,
both * * + * 4 3 9 - 5 3 - * 6 3 + 1 2 and 7 are valid prefix
expressions - the first is equal to 630, and the second to 7).  Note
that we have asked you to write a calculator that uses prefix notation
because there is a (recursive) algorithm that is much simpler than the
algorithms for traditional "infix" notation.

Allow user-defined functions with single-letter names.  Choose a
character such as  f  or   ~  to indicate a function definition, and
parenthesis to show the list of parameters.  For example, the input 
f s ( x ) * x x
f t ( x y ) - * x y + x y
would define a function named  s  that produces the square of its
parameter, and a function named  t  that produces the product of its
parameters minus their sum.  Function definitions can be followed by
equations that use  s  as an operation, for example, we could enter
f s ( x ) * x x
f t ( x y ) - * x y + x y
s 5
* 2 s + 1 3
t 3 4
and the calculator would print out 25  (52), 32  (2 * (1+3)2), and 5 (3
* 4 - (3 + 4)).  You should also allow function definitions to make use
of earlier functions.

You may assume that no function will have more than 3 parameters.  If
you wish to simplify your functions further, you may assume that there
will always be exactly three parameters, named  x ,  y , and  z  - this
would make it possible to define the above functions as follows:
f s * x x
f t - * x y + x y
s 5 0 0
* 2 s + 1 3 0 0
t 3 4 0
  3) Enigma simulation

Simulate the version of the Enigma encryption system that was used by
the German fisheries before World War II, and a system to "crack" the
code by decoding a message with all possible "rotor settings" and
checking for a test word.

The Enigma encryption system (used first by the German fisheries, and
then the German military in World War II) applied a series of
ever-changing permutations to the letters of the input, producing an
encrypted result that could not (theoretically) be read by anyone
without the same enigma system and the same setup information.  A
permutation is a rearrangement of letters in which each possible input
letter is associated with one result letter (e.g. the input 'b' might be
associated with the result 'q') and each possible input has a different
result (if 'b' gives the result 'q', then no other input could give the
result 'q').  The permutations in the Enigma system were created by
wiring together two disks, each of which had one electrical contact for
each letter (in our example, the contact for 'b' on the input disk would
be wired to the letter 'q' on the output disk).  We can change the
permutation by rotating the disk so that the wires connect different
pairs of letters (so now the wire that used to connect 'b' to 'q' now
connects 'a' to 'p', and some new wire connects 'b' to some other output
letter).  Such a wired pair of disks was known as a "rotor".

Note that we could also apply a rotor "backwards", which gives a
permutation that is different from (though related to) the permutation
when the rotor is applied in the usual fashon.  For example, sending 'q'
through the rotor described above, if it was in its original position,
would produce 'b'.

The Original Enigma system had 3 such rotors and a  "reflector" that
corresponds to the permutation a-z, b-y, c-x ... y-b, z-a.  As each
letter was typed on the keyboard, it was permuted by each of the three
rotors, reflected, and then permuted by the rotors in reverse  -- that
is, it went through the first rotor, then the second, then the third,
then the reflector, then backwards through the third rotor, backwards
through the second rotor, and backwards through the first rotor.  You
may choose any permutations you like for the rotors, as long as no
letter is ever permuted to itself.  The Enigma allowed only a sequence
of letters, without numbers or spaces or punctuation (this just made the
messeges a bit harder to read, and the code a lot harder to break).

After each letter was encrypted, one or more rotors were rotated in the
fashion of a car odometer - that is, the third rotator always moved, and
each time it ruturned to its original position (i.e. done 26 rotations)
the second rotor moved as well; when the second rotor returned to its
original position, the first was rotated as well.  Due to the nature of
the enigma, the result can be decrypted by running the encrypted text
through the same set of rotors, as long as they are started at the same
initial position (you should check to be sure your machine does this).

To make the code even harder to "crack", the rotors could also be
rotated before any text was encrypted.  For example, you might rotate
the first rotor 7 times, the second rotor 3 times, and the third rotor
16 times, and then encrypt a message.  To decrypt a message, you (or
someone else) would have to have the right set of rotors and set them to
the correct starting position.

Also create a simulation of a device that attempts to  crack  an
encrypted message by trying all possible initial positions of the three
rotors and testing to see if a given test word (such as  "one " or 
"eine" ) is contained in the message.  The message cracker should use
the same 3 rotors as the encryption program.







4) Choose your own project

You may choose another project if you get my permission in advance.  If
you want to do so, you must get my approval of the project by the end of
lab on November 24, in order to have time to write up your design
document.