LEAD Computer Science - Lab 2

Due: Tuesday, July 17 at 4pm

This assignment has three parts.  Please complete Parts A and B in a file lab2a.py, and complete Part C in a file lab2b.py.  When you are finished, submit both files on csman for Lab 2.

This assignment is rather involved; you aren't expected to complete it in one day! You will be given multiple days to complete it.

Coding Style, Comments and Docstrings

In this lab you will be writing more advanced programs, so you should start focusing on good coding style.  One of the most important aspects of good coding style is to make sure your programs are well-documented so that they are easier to fix and to maintain.  It turns out that the vast majority of a program's lifetime is spent in maintenance and debugging, and complete, concise documentation is essential for this!

You already know how to write comments in Python.  Another helpful technique Python provides is docstrings on functions.  For example, here is a function that specifies a docstring:
def square(x):
    '''This function returns the square of its argument.'''

    return x * x

The bolded line above is a docstring for the square function.  Docstrings are normally written as a triple-quoted string since they tend to span multiple lines, but they can also be written as a normal single- or double-quoted string if they take only one line.

Once we have docstrings, we can actually see our documentation using the built-in help() function!  Typing help(square) at the interactive prompt will give us this output:

Help on function square in module __main__:

square(x)
    This function returns the square of its argument.

That's pretty powerful functionality for such a simple amount of effort.

For this entire assignment, make sure to write a docstring for every function you write in Parts B and C, and make sure to document the internals of your functions using comments.  Also, don't overcomment your code!  Don't write a comment for every single line; rather, explain the complicated parts, and make sure that any subtle code is clearly and briefly explained in comments. 

Part A:  Pitfalls

In this section we're going to review some aspects of Python that can confuse new programmers (and sometimes also experienced programmers). We encourage you to experiment with these examples at the Python command-prompt to get a better understanding of what's going on.

  1. [25] What is wrong with the following snippets of Python code? Write a sentence or two describing what the problem is, why it's incorrect, and how to fix it.

    1.     a = 20
          # ... Do stuff with a.
          
          # Later in the program, test to see if a has become 0.
          if a = 0:
              print "a is zero!" 
    2.     def add_suffix('s'):
              '''This function adds the suffix '-Caltech' to the string s.'''
              return s + '-Caltech'
      
    3.     def add_suffix(s):
              '''This function adds the suffix '-Caltech' to the string s.'''
              return 's' + '-Caltech'
      
    4.     def prompt_and_sum(n):
              '''This function prompts the user for a number, adds n to it, then
              returns the result.'''
              val = raw_input('Enter a number:  ')
              return n + val
      
          prompt_and_sum(15)  # User enters something like 23 at the prompt.
      
  2. [20] Consider the following two functions:

        def add_and_double_1(x, y, z):
            result = 2 * (x + y + z)
            return result
    
        def add_and_double_2(x, y, z):
            result = 2 * (x + y + z)
            print result
    

    Now let's say that you wanted to use the result of these functions somewhere else in your program. Explain why this would work:

        n = 2 * add_and_double_1(1, 2, 3)
    

    and why this would not work:

        n = 2 * add_and_double_2(1, 2, 3)
    

    Write a sentence or two explaining the difference between printing a result and returning a result from a function.

  3. [20] Consider the following two functions:

        def sum_of_squares_1(x, y):
            result = x * x + y * y
            return result
    
        def sum_of_squares_2():
            x = int(raw_input("Enter x: "))
            y = int(raw_input("Enter y: "))
            result = x * x + y * y
            return result
    

    Now let's say that you wanted to use the result of these functions somewhere else in your program. Explain why this would work:

        n = 2 * sum_of_squares_1(2, 3)

    and why this would not work:

        n = 2 * sum_of_squares_2(2, 3)

    Write a sentence or two explaining the difference between passing a value as an argument to a function and getting it interactively using raw_input.

  4. [10] Why won't this function work?

        def capitalize(s):
            '''This function capitalizes the first letter of the string 's'.'''
            s[0] = s[0].upper()
  5. [10] Why won't this function work? (WARNING: Hard!)

        def double_list(lst):
            '''This function doubles each element in a list in-place.'''
            for item in lst:
                item *= 2

Part B:  Loops, Lists and Modules

As stated at the start of this assignment, make sure to write a docstring for each function you create in this part, and make sure to clearly comment any subtle or complex parts of your code.

[45] Number Guessing Game

Most people are familiar with the simple "number guessing game," which has very simple rules:  Player 1 chooses a random number in some range.  Player 2 then attempts to guess Player 1's number; after each guess, Player 1 responds whether the guess is too high, too low, or exactly right.

This is a very easy game to implement in a computer program.  In your implementation, the program will be Player 1, choosing a random number in the range [1, 100].  (The random number should be an integer, so that the game is not frustrating to human beings!)  Here are some additional tips:

Here is example output from running the game:

>>> guess_num()
I have a number between 1 and 100.  Guess it!
What is your guess?  50
Your guess is too high!
What is your guess?  25
Your guess is too high!
What is your guess?  12
Your guess is too low!
What is your guess?  18
Your guess is too high!
What is your guess?  15
You got it!  The number was 15.

Miniproject: The game of Mastermind

Note:  Your implementation of this project should be in a file lab2b.py , in a separate file from the first part of the lab.

Mastermind is a simple board game for two players. The rules are listed here, but here is a quick summary. One player (the "codemaker") picks a secret code consisting of four code pegs which can be any of six colors (we'll use the colors red, green, blue, yellow, orange, and white, which we'll abbreviate as 'R', 'G', 'B', 'Y', 'O', and 'W'). The order of the pegs is important, so a code of "RGBB" is not the same as a code of "BRGB". Colors can be duplicated in a code. The codemaker puts the four pegs representing his/her code in a secret location where the other player can't see them. That player (the "codebreaker") tries to guess the code by laying down four code pegs that he/she thinks might be the correct code. The codemaker compares the guess with the real code, and puts down zero to four key pegs which indicate how close the guess is to the solution. For every code peg which is the correct color in the correct location, a black key peg is put down. For every code peg which is a correct color but not in a correct location, a white peg is put down. Victory occurs when four black pegs are put down, which means that all the code pegs in the guess are the same as those in the secret code. The objective is to guess the code in as few moves as possible.

Here's an example of a sample game. Let's say that the secret code was 'ROOB' (Red, Orange, Orange, Blue). We'll show the code pegs on the left and the key pegs on the right (as black ('b'), white ('w'), or blank ('-')).

    Guess    Result
    -----    ------

    RGBY     bw--   (R is in the correct location, B is not, other colors wrong)
    OOWW     bw--   (One O is in the right location, one isn't, other colors wrong)
    RBOR     bbw-
    RBBW     bw--
    RBOO     bbww   (All colors correct, but not in the right order)
    ROOB     bbbb   (All colors correct and in the right order; victory!)

Your job will be to write a computer program to play Mastermind against you. The computer will be the codemaker and will choose a random code. You will be the codebreaker. The computer has to take your guesses and report how well you are doing. An interaction with the computer will look like this:

    New game.
    Enter your guess: RGBW
        Result: bw--
    Enter your guess: OOWW
        Result: bw--
    Enter your guess: RBOR
        Result: bbw-
    Enter your guess: RBBW
        Result: bw--
    Enter your guess: RBOO
        Result: bbww
    Enter your guess: ROOB
        Result: bbbb
    Congratulations!  You won in 6 moves!

We will build up to this in stages. All of your functions should have docstrings in which you state what the function does, what the arguments mean, and what the return value represents. Import whatever modules you need to solve the problems.

None of these functions need to be very long, so if you find yourself writing a lot of code for any function (say, more than 20 lines), you are probably going about the task the wrong way, so ask us for help!

  1. [15] Write a function called make_random_code which takes no arguments and returns a string of exactly four characters, each of which should be one of 'R', 'G', 'B', 'Y', 'O', or 'W'. You may find the random.choice function very useful for this problem.

  2. [15] Write a function called count_exact_matches which takes two arguments which are both strings of length 4 (you don't have to check this). It returns the number of places where the two strings have the exact same letters at the exact same locations. So if the two strings are identical, it would return 4; if the first and third letters of both strings are the same but the other two are different, it would return 2; and if none of the letters are the same at corresponding locations it would return 0. Examples:

        count_exact_matches("ABCD", "ABCD")  # --> 4
        count_exact_matches("ABCD", "EFGH")  # --> 0
        count_exact_matches("ABCD", "BCDA")  # --> 0  (not in the same locations in string)
        count_exact_matches("AXBX", "AABB")  # --> 2
    

    Use a for loop, which should iterate over the indices of the string (i.e. the list [0, 1, 2, 3]). Recall that you can access letters of a string using the same syntax you use to access elements of a list (because they're both sequences).

  3. [30] Write a function called count_letter_matches which is like count_exact_matches except that it doesn't care about what order the letters are in; it returns the number of letters of the two strings that are the same regardless of order. Examples:

        count_letter_matches("ABCD", "ABCD")  # --> 4
        count_letter_matches("ABCD", "EFGH")  # --> 0
        count_letter_matches("ABCD", "BCDA")  # --> 4  (the order doesn't matter)
        count_letter_matches("AXBX", "AABB")  # --> 2
    

    This function is a bit tricky, so here are some hints. Of course, you don't have to follow our hints; you can solve this problem any way you like as long as the solution isn't ridiculously long or convoluted.

    1. Convert the two strings into lists using the list built-in function before doing anything else.

    2. Go through one list character by character using a for loop. For each character that is in the other list, increment a counter variable and then remove the character from the second list (not the list you are iterating over) using the remove method on lists. Use the form <x> in <list> (see section B) to find out if a character is in a list.

    3. Once you have gone through the list, the counter variable is the answer.

  4. [30] Write a function called compare_codes which takes two arguments which are both strings of length 4. The first argument is called code and will represent the secret code chosen by the codemaker. The second argument is called guess and will represent the guess of the codebreaker. The function will output a string of length four consisting only of the characters 'b', 'w', and '-' (for black, white, and blank key pegs). This represents the key pegs i.e. the evaluation of the guess (so 'bbbb' would be a perfect guess, 'wwww' would mean all colors are correct but in the wrong order, and '----' would mean that no colors are correct).

    This function is the heart of the game. Fortunately, if you've written the two previous functions correctly, writing this one is a piece of cake. Here is the algorithm (solution method) you should use:

    1. The count of black pegs can be obtained just by calling the function count_exact_matches.

    2. The count of white pegs can be obtained by calling both the functions count_letter_matches and count_exact_matches and subtracting the result of the second function call from the first.

    3. The count of blank pegs is the difference between 4 and the sum of the count of black and white pegs.

    You will need to take these three counts and create a string for the result. Make sure that the string includes the 'b's first, then the 'w's, then the '-'s.

    Examples:

        compare_codes("ABCD", "ABCD")  # --> 'bbbb'
        compare_codes("ABCD", "EFGH")  # --> '----'
        compare_codes("ABCD", "BCDA")  # --> 'wwww'
        compare_codes("AXBX", "AABB")  # --> 'bb--'
        compare_codes("ABDC", "ABCD")  # --> 'bbww'
    
  5. [30] Now we're ready to write the function that actually runs the game. It will be called run_game, and it will take no arguments. When called, this function will do the following:

    1. Print "New game.".

    2. Select a secret code using the make_random_code function you defined above, and store this in a variable.

    3. Prompt the user for a guess using the raw_input function and the prompt string ""Enter your guess: ".

    4. Evaluate how well the guess matches the stored code using the compare_codes function and print out the result in the format "Result: <result string>".

    5. If the result string is "bbbb", then the function will print "Congratulations! you solved the game in <N> moves!" and exit (where <N> is the number of moves since the game began). Otherwise, the function will go back to step 2 above.

    In other words, the interaction with the user should be the same as what was described above at the beginning of this section. Here are a few hints:

    1. Every time the function asks for a guess, a counter which holds the number of moves should be incremented.

    2. Consider using an infinite loop (with a while statement) and a break statement inside the loop once the exit condition applies.

Submission

Once you have completed all parts of this lab, submit both lab2a.py and lab2b.py for Lab 2 on csman.


Copyright (c) 2012, California Institute of Technology. All rights reserved.
Last updated July 11, 2012.