CSCI 150: PreLab 5

Lists and Strings

Click here for the answer key

In this optional prelab (you do not have to turn this in, it is just an additional resource), we will formulate some of the ideas necessary to complete Lab 5.

Primes

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 (meaning that x cannot be divided by any number itself itself and 1). 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.

Prime numbers have many important uses, especially in helping keep communications secure on the internet. Therefore, an important problem is being able to create a list of prime numbers, which we will explore in this lab.

Describe the Problem:

 The problem you will solve on your lab is as follows.

Input: An integer n from the user that represents the number of primes to print out.
Output: The first n primes.

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

Design an Algorithm:

 Write pseudocode to solve this problem. You should decompose your main algorithm into small manageable chunks. For example, you should
  • design a function that takes an integer x and determines whether x is prime. E.g. isPrime(30) should return False, while isPrime(31) should return True.
  • make repeated use of this isPrime(x) method to generate the first n primes.
Q1. You are given two variables x and f that both store integer values. Find a boolean expression that should be True if x is evenly divisible by f, and False otherwise. For example, if x and f are 18 and 6 respectively, then the expression should evaluate to true, since 6 goes evenly into 18. For 18 and 5, however, the expression should evaluate to false, since 5 doesn't go evenly into 18.

Q2. Use the expression from question 1 to create pseudocode for an algorithm that determines whether x is prime.

Mind Mastery

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 program), 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). They may repeat colors and place them in any order they wish. 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 their 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.

Check here for an online graphical version of the game. Note this version uses red instead of black pegs to indicate a correct guess. Also note, this isn't the pinacle of gaming technology.
Assuming the code is RYGY, fill in the appropriate number of black and white pegs for each guess.

guess black pegs white pegs
Q3. BBPO
Q4. YYYY
Q5. YRYR
Q6. PYGR

Consider the following algorithmic approach for calculating the number of white pegs to be awarded for a given guess. 
 set a white counter to 0
 loop through the four positions of the guess
    loop through the four positions of the code
       if the current code character matches the current guess character
       and the guess and code positions are not the same,
       increment the white counter and exit the inner loop
What goes wrong with this algorithm?

Q7. Give an example of a code and a guess where the algorithm gives an incorrect hint.

Q8. For your code and guess in Q8, provide the correct number of white pegs that should be generated, along with the incorrect number of white pegs hint that this pseudocode instead creates.

Honor Code

If you followed the Honor Code in this assignment, write the following sentence attesting to the fact at the top of your homework.

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