CSCI 150: Lab 3

Prime Egyptian Master Minds
Due: 10PM on Tuesday, February 21

The purpose of this lab is to:

  • Introduce basic graphics
  • Practice loops using graphics
  • Practice procedural decomposition (using functions)
  • Practice using conditionals (if-statements)
  • Program your first interactive game!

Before you begin, please create a folder called lab03 inside your cs150 folder (for a refresher, here's how you did this on lab 02). This is where you should put all files made for this lab.

Part 1 - Walk Like an Egyptian

pyramid.py: 12 points, partner allowed.

If you choose to work with a partner, only one of you should submit a solution, but both of you should indicate your partner and who submitted a solution in your README files. You should also both read the Recurse Center's guide on pair programming before you begin.

Describe the Problem

Write a program called pyramid.py that draws a pyramid of bricks based on user input.

Input: An integer for the width of the image (width) and the height in bricks of the pyramid (n).
Output: An image of a pyramid that is n bricks tall in a square canvas width wide (and thus width tall).

Understand the Problem

Here are three sample outputs for your reference. Notice that the pyramid doesn't necessarily fill the entire canvas to the right and to the top; if the canvas width is not evenly divisible by the number of bricks, then there will be extra blank space. (A question for you to ponder: why is there so much blank space in the third example? Seems like you could fit lots of extra bricks both to the right and up top...)

400 x 400, 3 bricks.
3 bricks

400 x 400, 17 bricks.
17 bricks

400 x 400, 123 bricks.
123 bricks

Design an Algorithm

Write pseudocode to draw the appropriate pyramid. The algorithm is:

  1. Prompt the user for the width width of the canvas.

  2. Prompt the user for the number of bricks tall to make the pyramid, n.

  3. Setup a canvas of size width by width with a cyan background.

  4. Start building the pyramid in the bottom left corner of the canvas. This is the tricky part so we will walk you through it. Very broadly, the algorithm to draw the actual pyramid is:
For each row i of the pyramid
  • Draw row i of the pyramid
Of course, this leaves a lot of details out! The first question you should answer is "How many rows are there in the pyramid?" Hopefully it is clear that the answer here is n.

So we can rewrite the algorithm as:

For each row i from 0 to n-1 do
  • Draw row i of the pyramid
But drawing row i of the pyramid is a whole process in itself. To draw row i of the pyramid, we need to answer the following questions(which you answered on your prelab):
  • How many bricks does the i-th row have (given that the 0-th row has n bricks and the (n-1)-st row has 1)? That is, numBricksi = ??? Write down your answer.
  • What is the side length s of each brick in terms of width and n? That is, s = ??? Write down your answer.
If we take another look at our pseudocode, it would look like this:

For each row i from 0 to n-1 do
  • Draw row i of the pyramid as follows
    • Draw numBricksi bricks, each with side length s
If we were to implement this pseudocode, we would see that all the rows would be squished up against the left-hand side of the canvas... that is, we haven't taken into account that each row itself starts a little bit further to the right than the row below it. Thus, our next questions (which you answered on your prelab):
  • What is the x-coordinate of the first brick of row i in terms of s and i (given that the 0-th row starts at x-coord 0)? That is, startX = ??? Write down your answer.
  • What is the y-coordinate of the first brick of row i in terms of s and i (given that the 0-th row starts at y-coord width - s)? That is, startY = ??? Write down your answer.
Now we have enough to complete our pseudocode with sufficient detail:

For each row i from 0 to n-1 do
  • Draw row i of the pyramid as follows
    • Draw numBricksi bricks, each with side length s
    • Each brick should have y-coordinate startY
    • The first brick should have x-coordinate startX and each subsequent brick should be offset by s from the previous

Implement a Design

Now that you have a detailed algorithm in pseudocode, translate it (bit by bit!) into a Python program named pyramid.py. Although your final program should get the width and number of bricks from the user, you may want to temporarily hard-code this values into your program (using the example values above, perhaps) for now because it will make testing easier for now.

Using the picture module

We have provided you with a module picture that lets you draw pictures. To use it you need to:

  1. Download or copy the picture module into your current working directory (in this case, your lab03 directory).

  2. Before your main declaration, add the line

    
      import picture
                                    
  3. To get started, you need to declare and initialize a new picture object using a constructor function as follows:

    
      canvas = picture.Picture(600, 800)
                                    
    This creates a new picture object called canvas which you'll be able to draw upon and display. The parameters are a pair of integers that specify the width and height of the canvas. Naturally, you can use other values if needed.

  4. At any given time, picture object keeps track of an outline color (lines and edges of shapes) and a fill color (the inside of shapes). The default values of these parameters are black and white, respectively. To change the color of the lines, you'd use the setOutlineColor function, as follows:

    
      canvas.setOutlineColor(r, g, b)
                                    
    Here r is an expression indicating how much red the pen color should have (from 0 to 255). Similarly, g and b indicate how much green and blue are in the pen color. Some useful (r,g,b) values: (255, 255, 0) is yellow, (0, 0, 0) is black, and (0, 255, 255) is cyan.

    The function to set the fill color is what you might expect:

    
      canvas.setFillColor(r, g, b)
                                    
  5. You'll also want to use the drawRect and drawRectFill function to draw rectangles and filled rectangles. For example,

    
      canvas.drawRectFill(x, y, w, h)
                                    
    would draw a filled rectangle in the current pen color. The rectangle would be w pixels wide and h pixels tall. The upper left corner of the rectangle would be located at position (x,y). (Recall that the picture coordinate system, (0,0) is the upper left pixel.)

  6. On older systems, you might need to use the display() function after you've created the image. So you'd write

    
      canvas.display()
                                    
    As you may recall from class, the picture window will close as soon as your program ends, so if you want to be able to admire your creation, you'll need to force the program to wait. The easiest way to do this is by ending your program with an input statement:

    
      input()
                                    

    Now when you run your program, it will open the picture window and keep it open until you press enter.

Implementation Notes

  • All the bricks you draw should be exactly the same size. While you can pass floats to various picture functions, including drawRectFill, in the end these values end up being rounded to integers (since all pixels have integer coordinates). To ensure your bricks are placed exactly as you intend, you may wish to do the rounding yourself.

  • On a related note, sometimes the brick size length won't divide evenly into the canvas size. In these cases, you will have gaps either to the right or to the top of the pyramid. This is okay. However, you should not have gaps to the left or on the bottom of the pyramid. Always start at the bottom left, putting the next brick right next to theprevious one and right on top of the previous layer.

  • Use functions where appropriate. For example, it seems natural to have a function that takes in 4 parameters x, y, numBricks, s and draws numBricks bricks each of side-length s, starting at coordinates (x, y). Use other functions where you think it is appropriate; if you don't use any functions your grade will be lowered accordingly!

Test the Program

Try running the program with the examples given above as well as some others. Make sure you have gaps where you ought to, and that there aren't gaps where there shouldn't be gaps! Your pyramid should not be sloping to one side or floating in the middle. You shouldn't have some bricks that are larger than others. If it looks fishy, go back and examine your math equations, checking that the "integer division" is being used appropriately.

Don't forget to let the user input the width and number of bricks, if you were testing the program with hard-coded values.

Handin

Please handin your lab up to this point so that we have some portion of your code submitted.

Part 2 - Primes

primes.py: 12 points, individual.

As you may know, a number x is said to be prime if x is at least 2, and the only proper factors of x are itself and 1. So the first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, etc. 4 isn't prime, since it is divisible by 2. Same goes for 6 and 8. 9 is out thanks to 3. And so on. There are a lot of primes. More precisely, there are infinitely many primes. This can actually be shown pretty easily; ask if you're curious.

A twin prime is a pair of prime numbers that differ by exactly 2. So (3,5), (5,7), (11,13), (17,19) and (29, 31) are all twin primes. Note that not every prime is part of a twin prime. It is conjectured that there are infinitely many twin primes too, but no one knows for sure.

Describe the Problem

Write a program called primes.py that prints out some number of primes and the number of twin primes amongst them.

Input: A number n.
Output: The first n primes, and the number of twin primes amongst these n.

Understand the Problem

If the user enters 13 then the output should be

  The first 13 primes are:
  2 3 5 7 11 13 17 19 23 29 31 37 41
  Amongst these there are 5 twin primes.
                          
Note that (41, 43) is a twin prime, but we didn't count it since 43 wasn't amongst the first 13 primes.

Design an Algorithm

Write pseudocode to solve this problem. You should decompose your main algorithm into small manageable chunks. For example, you should:

  • design an algorithm that takes in an integer x and determines whether x is prime. For example, "isPrime(10)" would return false, while "isPrime(31)" would return true. You did this on your prelab.
  • make liberal use of this isPrime method to generate the first n primes.

Implement a Design

You may want to use a while loop as you search for primes, since you won't know ahead of time just how far you need to go. Ask if you're not sure what a while loop is, or Google "python while loop".

Test the Program

Try your program with a variety of inputs n. Certainly you should try n=0,1,13 but you should also try n=14 to get that one extra twin prime, as well as others!

Handin

Please handin what you've completed thus far.

Part 3 - Mind Mastery

master.py: 14 points, individual.

Mastermind is a neat (although oftentimes frustrating) puzzle game. It works a something like this: There are two players. One player is the codemaker (your porgram), the other is the codebreaker (the user). The codemaker chooses a sequence of four colored pegs, out of a possible six colors (red, blue, green, yellow, orange, and purple). He may repeat colors and place them in any order he wishes. This sequence is hidden from the codebreaker. The codebreaker has 10 chances to guess the sequence. The codebreaker places colored pegs down to indicate each of her guesses. After each guess, the codemaker is required to reveal certain information about how close the guess was to the actual hidden sequence.

Describe the Problem:

In this part of the lab, you will create a program to play Mastermind, where computer is playing the codemaker, and the human user is the codebreaker. Thus your program needs to generate a secret code, and repeatedly prompt the user for guesses. For each guess, your program needs to give appropriate feedback (more detail below). The game ends when either the user guesses correctly (wins) or uses up 10 guesses (loses).

Understand the Problem:

The trickiest part of this game is determining how to provide feedback on the codebreaker's guesses. In particular, next to each guess that the codebreaker makes, the codemaker places up to four clue pegs. Each clue peg is either black or white. Each black peg indicates a correct color in a correct spot. Each white peg indicates a correct color in an incorrect spot. No indication is given as to which clue corresponds to which guess.

For example, suppose that the code is RYGY (red yellow green yellow). Then the guess GRGY (green red green yellow) would cause the codemaker to put down 2 black pegs (since guesses 3 and 4 were correct) and 1 white peg (since the red guess was correct, but out of place). Note that no peg was given for guess 1 even though there was a green in the code; this is because that green had already been "counted" (a black peg had been given for that one).

As another example, again using RYGY as our code, the guess YBBB would generate 1 white peg and 0 black; yellow appears twice in the code, but the guess only contains one yellow peg. Likewise, for the guess BRRR, only 1 white peg is given; there is an R in the code, but only one. Below is a table with guesses and the correponding number of black and white pegs given for that guess (still assuming the code is RYGY).

guess black pegs white pegs
YYYY 2 0
YRYR 0 3
BBPO 0 0
PGYR 0 3
YYYG 1 2
RYGY 4 0
Check here for an online graphical version of the game (where their red pegs are our black pegs).

A sample run of our text-based program may look like this:

Sample output

  %python3 master.py
    
  I have a 4 letter code, made from 6 colours.
  The colours are R, G, B, Y, P, or O.

	Your guess: GGGG
    Not quite. You get 0 black pegs, 0 white pegs.

        Your guess: YYYY
    Not quite. You get 1 black pegs, 0 white pegs.

        Your guess: YOYO
    Not quite. You get 0 black pegs, 2 white pegs.

        Your guess: PPYO
    Not quite. You get 1 black pegs, 2 white pegs.

        Your guess: POYB
    Not quite. You get 1 black pegs, 3 white pegs.

        Your guess: PBOY
    You win! So clever.
                          

Design an Algorithm

Once you understand how the game works, you should design a pseudocode plan of attack. The general steps are:

  • Randomly choose the codemaker's code.
  • Repeatedly prompt the user for their guess
    • If their guess is correct, end the game with a congratulatory message.
    • Otherwise, give clues (pegs) that correspond to their guess.
Some of these steps are straight-forward, but certainly it would be worth your while to write down an approach to randomly generating the code, and giving the clue. You did some of this on your prelab; our recommendation for the later algorithm is as follows:

  • First assign the black pegs. Do this by iterating through both strings one character at a time, assigning a black peg if the characters in the same position match. If they do match, change that character/peg in your guess to an 'x' and in the code strings to a 'z', say, so that you know you have used both of these pegs for a clue (and you won't use them again when assigning white pegs and accidentaly double-count). (You can find some useful string methods on pg 125 of the text, or here in order to do this.)
  • Next assign the white pegs. Do this by considering the first peg in the guess string and trying to find the matching character in the code string (note that if the first character is an 'x' then there definitely won't be a match in the code string). If you find a match, again change the guess character to 'x', the matching code character to 'y' and continue with the second peg in the guess string, then the third, and so on. Because of your changes to 'x' and 'y', you won't assign both a black and white peg for one guess or clue peg.

Implement a Design

Now that you have some of the kinks worked out in theory, it is time to write your program master.py.

You may assume the user always provides a guess with the available colors, and always in uppercase.

Make and use an integer constant NUM_TURNS that represents the number of allowable turns (say, 10).

generateCode()

To generate the code, write a method generateCode() that generates the codemaker's code (and returns it as a String to the caller). That is, this method should randomly generate 4 colored pegs, selected from R, B, G, Y, O, and P, and return it as a 4-letter string. You'll want to use the random methods as discussed in lab02 in order to randomly generate a color for each peg. In particular, you'll generate an integer between 0 and 5 inclusive, and use if-statements to map each result to one of the 6 colours. Test your generateCode() method thoroughly before continuing. No, seriously, test it before continuing.

clue(code, guess)

Next, write a method clue(code, guess) that prints out the white and black clue pegs according to the given guess and code, and returns true if code equals guess, and false otherwise. Translate the pseudocode above to help you out.

Note that you can "change" the i-th character in a string s to an 'x' as follows:


  s = s[0:i] + "x" + s[i+1:len(s)]
                        
Also note you can omit the len(s) from the above expression. That is, if you write s[i:], Python interprets that as the substring of s from position i to the end. Similarly, s[:i] denotes the substring of s from the beginning up to (but not including) i.

Test the Program

It is hard to test your program when you are given a random code that you don't know. Therefore, you should either hard-code in a code for testing purposes (for example, the code that you checked by hand on the prelab), or you should allow the user of the program the option to input a code (this would make our graders very happy, so I like this option.)

Part 4 - Wrap Up

README: 2 points, individual.

As with every lab, your last job prior to submission is to complete a brief write-up in a README file. If you haven't already done so, please create a new README file in your lab02 folder.

In this file, write a sentence or two about what you learned in this lab. Also give an estimate of the amount of time you spent on the lab. If you have further thoughts about the lab (e.g. parts that were confusing, helpful, annoying, fun, or challenging), please let us know.

Again, if you worked with a partner on Part 1, your README file should indicate the name of the partner, and specify which of you submitted the solution to that problem.

Handin

If you followed the Honor Code in this assignment, insert a paragraph attesting to the fact within one of your README file.

I affirm that I have adhered to the Honor Code in this assignment.

You now just need to electronically handin all your files. As a reminder

 
  % cd             # changes to your home directory
  % cd cs150       # goes to your cs150 folder
  % handin         # starts the handin program
                    # class is 150
                    # assignment is 3
                    # file/directory is lab03
  % lshand         # should show that you've handed in something
                

You can also specify the options to handin from the command line

 
  % cd ~/cs150     # goes to your cs150 folder
  % handin -c 150 -a 3 lab03
                

File Checklist

You should have submitted the following files:

  pyramid.py (unless you worked with a partner, and your partner submitted)
  primes.py
  master.py
  picture.py (you shouldn't have touched this, but it makes grading easier)
  README
                


A. Eck, A. Sharp, T. Wexler, M. Davis, and S. Zheng.