Python final: bagels

posted by: Ms. Martin 15 June 2011 No Comment

Thanks to Stuart Reges for this assignment.

Bagels is a variant of the game Mastermind where the computer thinks of a random number and the user tries to guess it.  Each digit of the random number is a value from 1 through 9.  No 0 digits are included, but the same digit might appear more than once.  The player is told how many digits the number has.

Below is a sample log of execution (user input is underlined).

I'm thinking of a 4 digit number. Each digit is between 1 and 9.
Try to guess my number, and I'll say "fermi" for each digit you get right,
and "pica" for each correct digit in the wrong place. 
Your guess? 1234
Your guess? 5678
fermi fermi pica 
Your guess? 5566
Your guess? 8877
fermi pica pica 
Your guess? 5587
fermi pica pica 
Your guess? 5778
fermi fermi pica pica 
Your guess? 7578
You got it right in 7 guesses!

You may assume that the user will always type a valid guess with the right number of digits from 1-9. In this game, the clues are based on digits that match between the correct answer and the guess. For each digit in the guess that exactly matches the corresponding digit in the answer, the program outputs ”fermi”.  For each digit in the guess that appears in the answer but at a different index, the program outputs “pica”.  If the guess does not contain any digits that appear in the correct answer (no “fermi” or “pica” matches), the output is “bagels”.

It is helpful to think of the correct answer and the guess as lists of digits.  Suppose the correct answer is 7578 and the user guesses 5587 (the fifth guess in the log above).  The above guess has one “fermi” match: the digit 5 at index 1.  It also has two “pica” matches: the digit 8 at index 2 of the guess matches the 8 at index 3 of the correct answer; and the digit 4 at index 3 of the guess matches the 4 at index 0 of the correct answer.

Notice that the digit 5 at index 0 of the guess is neither a fermi match nor a pica match; there is a digit 5 in the correct answer, but it is already claimed by its fermi match with index 1. index  0 1 2 3 correct answer 7 5 2 8 guess 5 5 8 7 The computer’s clue consists of the word “fermi” once for each fermi match (correct digit at correct index), followed by the word “pica” match for each pica match (correct digit, wrong index).  All of the fermi clues are reported first so as not to give any extra information to the player.  The clue for the above guess would be “fermi pica pica”.

You should use lists to store the computer’s random number and the user’s guesses as appropriate, as shown in the diagrams.  This will be a useful way to represent the numbers so that you can compare them one digit at a time.  You can pull digits off of an int by repeatedly dividing and modding (%) the number by 10.

The most difficult part of the assignment is comparing the user’s guess to the correct answer and providing the correct clue.  You will likely want to use a “two phase” algorithm that compares the two arrays of digits in two passes:

  • The first pass looks for “fermi” matches, where a digit in the guess is correct and in the correct place.
  • The second pass looks for “pica” matches, where a digit in the guess exists in the answer, but at a different index.

The same digit cannot be used for two different matches.  For example, using the correct answer of 7578 and the guess of 5587 from the previous page, the digit 5 at index 0 of the guess doesn’t match anything, because the digit 5 in the guess is already claimed as part of a fermi match.  To implement this functionality correctly, you should find  a way to mark individual digits as being “used” so that they will not be used again in another match.

One way to “mark” a digit would be to change its value.  But you should be careful not to damage the original list for the correct answer, so you may want to make a copy of it or implement some way to restore its state later.  Note, if list a exists, b = a[:] will store a copy of it in variable b. Careful — b = a does not do what you want!  Another way to ”mark” digits would be to keep a separate temporary array of marking values.

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)
Loading ... Loading ...

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>