CS21 Lab 5: more advanced functions

Written Assignment: Due Friday, March 1, in class.

Coding Assignment: Due Saturday, March 2, before midnight.

Make sure all programs are saved to your cs21/labs/05 directory. Files outside this directory will not be graded.

$ update21
$ cd ~/cs21/labs/05

Note that there is a written portion to this lab that is due in class on Friday.

Please read the directions for the coding portion of the lab completely before you start writing code. There are several hints and tips designed to make your life easier in the write-up.

Programming Tips

Topics for this assignment

1. Written Assignment: Stack Diagram

The first part of the lab involves you tracing a program with functions and showing the resulting stack that the function calls generate. This is excellent practice for what will almost certainly be a quiz question! Download the PDF, print it out, and turn it in at the start of class on Friday.

2. Coding Assignment: Lingo

In the file lingo.py you will write several functions to implement a secret word guessing game called Lingo. Lingo is a turn-based guessing game. The computer selects a random five letter word and the player tries to guess the word. Each guess must also be a valid five letter English word (this is what makes the game interesting and hard). After a guess is made, the computer provides status information about how close (or how far) the player is to arriving at the solution. The status information includes which letters are correct, but in the wrong position, and which letters are correct, and in the right position.

Example guessing

To see how the computer displays the status for a given guess, suppose the computer has chosen the secret word guava. In general game play, we do not know the secret word, but using guava as an example will illustrate how the game works.

We begin playing with the initial guess spray. Notice that there is only one letter that in the guess that's also in the target word (the letter a). The status message will specify which letters are exactly correct and which are in the sequence, but in the wrong place. You'll do this by UPPER-CASING exact matches, leaving the inexact matches alone, and replacing the wrong letters with dashes. So, in this case, where the letter a of our guess spray is an inexact match, we'd receive the status message:


As we don't know the word yet, we make another guess: arrow. Again, the only correct letter is the a, and now it's in a different wrong place. So, the status we would receive is:


Our next guess is again. This time the guessed word has two a's, as does the secret word. The first guessed a is in the wrong position and will appear as lower case, but the second guessed a is in the correct position (the third character) and should show up as an UPPERCASE letter in the status. There is also a correctly guessed g but it is in the wrong position and will appear as lower case. Since neither the i nor the n appear in the target word, the status of this guess is the following:


Our next guess is games. While we already know there are no s's in the word from our previous guess of spray, we can use games to see if there is a e or m, or to help find the exact position of the g and the other a. The status message now that we have the g in the right position and the a is still in the wrong position:


Here is this example as it may appear in a game (see the Sample Output section below for other examples of a working solution):

Enter a 5 letter word: spray
- - - a -
Enter a 5 letter word: arrow
a - - - -
Enter a 5 letter word: again
a g A - -
Enter a 5 letter word: games
G a - - -
Enter a 5 letter word: curve
- U - V -
Enter a 5 letter word: suave
- U A V -
Enter a 5 letter word: guava
You won in 7 turns!

Sample Output

You should look at the sample output from a few runs of the completed program.

Writing Helper Functions

You are required to implement and use functions for this lab. We provide one function for you in the cs21s19 library called getWords which returns a list of valid five letter English words.

$ python3
>>> from cs21s19 import getWords
>>> allWords = getWords()
>>> print(allwords[400])

You must write the following additional functions, and your implementation must match the specifications given here. You may write additional function if you'd like. You should read this all the way through and only start programming when you have a good understanding of how main() will use each of the other functions:

Computing Exact Matches

The exactMatch and inexactMatch functions are two of the more technical functions to write in this lab. Both take a list of characters as input parameters and modify that list to update the status. Let's look at exactMatch(statusList, secretList) in more detail. Suppose we have a guess of cloud, and secret word ghoul. These strings will be converted to lists statusList and secretList as shown in the table below in the before column. The exactMatch function would need to check each position in the statusList and determine if the letter in the corresponding position in secretList matches. In this example, both the o and u are exact matches. Your function, according the specification above should uppercase the o and u in statusList. You must also replace the corresponding matches in secretList with a .. By replacing the characters in secretList with dots, we are essentially removing them from the secret list (we'll see how to remove from a list later in the course), so they cannot be counted again as inexact matches later. Note in the after column in the table below, only the lists change.

variable before after
secret "ghoul" "ghoul"
guess "cloud" "cloud"
statusList ['c', 'l', 'o', 'u', 'd'] ['c', 'l', 'O', 'U', 'd']
secretList ['g', 'h', 'o', 'u', 'l'] ['g', 'h', '.', '.', 'l']

Computing Inexact Matches

After computing exact matches, we reuse the modified statusList and secretList to compute inexact matches as follows: We consider each character in statusList sequentially. For each character ch in statusList, we first check if ch is upper-case. If it is, it must have been an exact match and we can ignore it for inexact matching. If it is lower case, we check if ch appears anywhere in secretList. If the answer is no, we can replace the position in statusList containing ch with a - indicating this letter was neither an exact match nor an inexact match. If ch does appear in secretList however, we do not need to modify statusList at all. We do need to find some location in secretList containing a ch and replace this location with a . so that we do not attempt to match this letter in secretList with some other letter in statusList.

For our particular example of a secret word ghoul and guess cloud, this algorithm would first look at the c in cloud. There is no c in gh..l, so we replace the c with a -. The next letter l does appear in gh..l, so we do not need to update statusList, but we do replace the l in statusList with a . to indicate the l can no longer match other letters in the guess. The next two letters O and U are upper-case exact matches, so there is no need to update either statusList or secretList. Finally, there is no matching d, so our final statusList is ['-', 'l', 'O', 'U', '-']. We could later use the characters in this list to print the status to the user, but without all the extract [''] syntax.

variable before after
statusList ['c', 'l', 'O', 'U', 'd'] ['-', 'l', 'O', 'U', '-']
secretList ['g', 'h', '.', '.', 'l'] ['g', 'h', '.', '.', '.']

Writing a main Function

In the beginning, you should use main() to incrementally test your individual functions and then gradually build the complete program, similarly to how you worked on lab 04, except instead of using multiple files, you are using one file.

A finished program might have the primary steps in main() shown below. Think about how to use the helper functions to implement each step.

  1. Print out general instructions to the user

  2. Pick a secret word for the user to guess

  3. Show the initial status of the game, - - - - -

  4. Ask the user for an initial guess

  5. Until the user guesses the secret word or types QUIT:
  6. Show the total number of turns needed to win, or show the secret word if the user decided to quit.

Strategy and Tips

It is very important that you think carefully about how each of your functions is being used. Each of the steps in the main function that we have outlined should only need a few lines of code – the functions handle most of the complexity.

Additionally, it is incredibly important that you use incremental development. The outline of main is a good starting point - you should complete one step at a time, thoroughly test it to see if your program works, and only move on after getting it to work. The ninjas and lab instructors will ask you to backtrack and do incremental development if you do not follow this strategy. If you try to implement the whole program at once, you will waste a lot of time and energy trying to fix your program.

It may be helpful to print out the secret word at the beginning when testing, but remember to remove this code when you are finished and submit the lab. #NoSpoilers!

At some point you will need to convert a string type into a list of characters. Just like we used int(), float(), and str() to convert from one type into another, we can use list(txt) to convert the string variable txt into a list.

lst = list(txt)
['h', 'e', 'l', 'l', 'o']

You may also need to convert a character to upper case. You can use some ord() and chr() tricks to write a toUpper(ch) function, but you can use python's built in upper() method. We will talk about methods and objects soon, but for now, you can just copy/paste this syntax. <var>.upper() will compute the upper case version of any string variable <var>

ch = "h"
up = ch.upper()

text = "hello"
up = text.upper()

Likewise, you can use Booleans and string comparisions to determine if a character is an upper/lower case letter, but there is a method for those too.

ch = "h"

3. Answer the Questionnaire

Each lab has a short questionnaire at the end. Please edit the QUESTIONS-05.txt file in your cs21/labs/05 directory and answer the questions in that file.

Turning in Your Labs

Don't forget to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.