This week's lab is part of a two-part assignment where you will first design and then implement a more complex program. A skeleton version of the program ghost.py will appear in the directory cs21/labs/06 when you run update21 in a terminal window. The program handin21 will only submit files in this directory.

You may work with one partner on this lab. If you work with a partner, put your name and the name of your partner in the list of authors at the top of your program. Only one partner needs to run handin21 to submit the files for the group. Both partners will receive the same grade.

Over the next two weeks, you will write a program that plays the word game Ghost. For Lab 6, you will focus on using top-down design to create the overall structure of the program. Once your proposed structure has been reviewed, then for Lab 7 you will focus on using bottom-up implementation and unit testing to incrementally construct the program.

Ghost is a word game where players take turns adding letters to a growing word fragment, trying to avoid being the one to actually spell a valid word. However, the word fragment must always be the start of some valid word. If a player doesn't believe that the current fragment could make an actual word, he or she may challenge the other player to produce a valid word from the fragment. A player wins by forcing the other player to add a letter that spells a complete word. A player can also win by challenge. One additional constraint is that any word of three letters or fewer does not count. To make things more concrete let's consider a couple of examples.

Suppose that you are playing with a friend.

• The friend begins with the letter i.
• You add the letter g, making ig.
• The friend adds the letter l, making igl.
• You add the letter o, making iglo.
• The friend now realizes that he's stuck. The only letter he can think of that is part of a valid word is the letter o, but that will spell the word igloo. He concedes the game, making you the winner.

You decide to play again, but this time the friend wants you to go first.

• You decide to start again with the letter i.
• Your friend is ecstatic thinking he's going to win this one and adds the letter g, making ig.
• But you've got a plan, and add the letter u, making igu.
• Your friend is not so ecstatic now. He can't think of a word that begins like that and decides to challenge you.
• You point out that the word iguana begins with igu. Sadly, your friend concedes the game again.

Your friend decides to give it one more try, and it's his turn to start.

• He begins with the letter c.
• You add the letter h, making ch.
• He adds the letter a, making cha.
• You add the letter n, making chan.
• He adds the letter g, making chang.
• You realize that you may be in trouble this time. You don't want to add the letter e because that would spell the word change. You try to prolong the game by adding the letter i, making changi.
• He adds the letter n, making changin.
• This time you have to concede, because the only letter you can think to add is g, but that spells the word changing.

For this lab, instead of playing against a friend you will be playing against the computer. This is much more challenging because the computer has access to a complete dictionary of words. Here are a few sample runs showing how your program might work.

Welcome to the game of Ghost.
The current word fragment is: h

1. Add a letter 
2. Challenge
Choice: 1

Enter a letter: e
The current word fragment is: he

Computer will add the letter: m
The current word fragment is: hem

1. Add a letter 
2. Challenge
Choice: 1

Enter a letter: l
The current word fragment is: heml

Computer will add the letter: o
The current word fragment is: hemlo

1. Add a letter 
2. Challenge
Choice: 1

Enter a letter: c
The current word fragment is: hemloc

Computer will add the letter: k
Computer just made the word hemlock

Congratulations, you just outsmarted the computer!

Notice in the above example that the three-letter word hem appeared, but the computer did not lose the game, this is because only words of length four or longer count.

Welcome to the game of Ghost.
The current word fragment is: r

1. Add a letter
2. Challenge
Choice: 1

Enter a letter: o
The current word fragment is: ro

Computer will add the letter: m
The current word fragment is: rom

1. Add a letter
2. Challenge
Choice: 1

Enter a letter: b
The current word fragment is: romb

Computer challenges!
romb is NOT the start of any valid word.

Sorry, you lose.

For Lab 6, you must turn in just your top-down design for a solution to this game.

• Your main program should be fleshed out and call whatever functions that you think will be necessary to solve this problem. The main program should be short and clearly structured, much like an outline.
• Each function should be stubbed out, meaning it will be defined with a name and parameters, but should not be implemented yet. It should include a clear comment, explaining what inputs it receives, what it returns, and its purpose. It should return a temporary value of the correct type. If the function has no return value then it should simply have an empty return.
• Once you have stubbed out these initial functions needed by the main program, continue to refine your design. Do these functions need further helper functions? Keep dividing up the work required into additional functions until you have a function that would be relatively straightforward to implement.
• Your program should run when executed, although it won't do much yet. It should not contain any syntax errors.

Here is an example of a stubbed out program. What you turn in for this lab should be similarly structured.

• The online dictionary is stored in the file: /usr/share/dict/words. Your program should read in all of the words from this dictionary that are the appropriate length (four or more letters), are not proper nouns (so must begin with a lower case letter), and do not contain an apostrophe. It should store all of these valid words in a list.
• It is possible to create an optimal computer player that would pick the best letter to make the human player lose. You will only be required to create a competent computer player. The computer player should always select a valid letter, if one exists. Otherwise it will challenge the human player, and win.
• One enhancement you may want to add is that when the computer player is about to lose (because it only has one option and that will make a word), it can try to bluff by choosing a random letter instead.

Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.