handout #17
CSE341—Programming Languages
Programming Assignment #9 (Ruby)
due 11 pm Friday, 6/5/09
You can use up to two late days for this assignment (assuming you have late days left to spend). This assignment will give you practice with Ruby. First you are to solve several small Ruby problems:
1. (5 points) Define a method fib(n) that returns the nth Fibonacci number. Recall that the sequence begins with the values 1, 1 (which we'll consider fib(1) and fib(2)) and then each successive number is the sum of the previous two. You should define this as a simple, top-level method. It should efficiently compute the sequence rather than using the inefficient recursive solution. You may assume that n is greater than 0. For example:
>> (1..10).map {|n| fib(n)}
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>> fib(100)
=> 354224848179261915075
>> fib(200)
=> 280571172992510140037611932413038677189525
2. (10 points) Define a method prompt(msg, error) that prompts the user for a value that satisfies a particular predicate and that returns the user’s response. In prompting, you’ll want to execute the equivalent of Java’s System.out.print. We’ve seen that the puts method is like System.out.println. The print method is like System.out.print (i.e., it displays but stays on the same line). You can also use the printf method if you prefer. So your method should call print or printf to prompt the user with the given message. Then you should use gets to read a line of input from the user and use chomp to eliminate any newline characters at the end of the string. If the input satisfies the predicate, you should return it (the chomped input). Otherwise you should issue the given error message and start prompting again. The predicate will be specified as a block and you should include a call on yield to check whether the user's input satisfies the predicate. Below is a sample interaction with user input underlined:
>> s = prompt("3 char string? ", "not 3 chars") {|str| str.length == 3}
3 char string? foobar
not 3 chars
3 char string? howdy
not 3 chars
3 char string? hi
not 3 chars
3 char string? help
not 3 chars
3 char string? ruby
not 3 chars
3 char string? foo
=> "foo"
3. (10 points) Extend the class Integer to include a new iterator called factors. It should produce each of the factors of the number in increasing order. An iterator is simply a method like each that calls yield to produce a particular sequence of values. The factors iterator should generate each factor of the number from 1 up to the number. For example:
>> 24.factors {|n| puts n}
1
2
3
4
6
8
12
24
=> nil
>> 16.factors {|n| puts n}
1
2
4
8
16
=> nil
>> sum = 0
=> 0
>> 28.factors {|n| sum += n}
=> nil
>> sum
=> 56
As indicated in the sample log above, your method should not return a value. Your method should compute factors by checking every integer starting at 1. Your iterator has to be efficient in two specific ways. In general, it shouldn't compute a value before it needs it. For example, you aren't allowed to precompute all of the factors before you call yield. Your method also has to take advantage of the fact that most factors come in pairs, as in 2 * 12. As a result, you don't have to compute factors beyond the square root of the number. Your method should remember the factors that come after the square root. For example, in computing the factors of 24, when it finds that 2 is a factor, it should remember that 12 is also a factor, although it won't report that factor until later because the factors are supposed to be generated in increasing order. You might want to call Math.sqrt to find the square root of a number. You may assume that the integer is greater than or equal to 0 (or you can add code that immediately returns nil for numbers that are less than or equal to 0).
Then you are to complete one of two programs: Bagels or Jotto. Each program is described below and there is a log of execution for each. You are to exactly reproduce the format of the log. Completing Bagels is worth 65 points, which would allow you to score 90 points for the assignment. Completing Jotto is worth 75 points, which would allow you to score 100 points for the assignment. You are not to solve both. Include your answers in a file called hw9.rb (the bagels and jotto drivers assume that such a file has been defined).
4. (65 points) Define a class called Bagels that can be used to play the game of Bagels. It should have the following public methods:
|
initialize |
Your public constructor (takes no arguments) |
|
play |
Plays one game of Bagels with the user, asking the user how many digits to use, making up a number to be guessed, giving clues until the user guesses the right answer and reporting the number of guesses the user takes to guess the right answer. |
|
stats |
Reports statistics about total games played, total guesses made and average guesses per game (a real number). If no games have been played, it should instead print "No games played." |
|
clue_for(guess, answer) |
Takes two strings as parameters and returns a string representing the clue to give for this combination. The string should always begin with "clue:" and then should have some combination of the words "fermi", "pica" and "bagels", as described below, separated by spaces. |
You should not have any public methods other than these, although you may have as many private methods as you want.
The game of Bagels involves guessing a particular sequence of digits. Only the digits 1 through 9 are used (no 0's). As the log indicates, your program must make sure that the user supplies a positive number for the number of digits and enters a guess of appropriate length, but your program doesn't have to verify that all of the characters of a guess are digits (if the user guesses something other than a digit, then that's a wasted guess anyway). If no digits in the user's guess match any digits in the answer, the clue given is "bagels." Otherwise, you compare the digits from the answer against the digits from the guess looking for matching pairs of digits. Each matching pair of digits produces either the word "fermi" or "pica". Each pair of digits that matches and is in the correct position produces a "fermi". Each pair of digits that matches and is in the wrong position produces a "pica". No digit can match more than once and fermi matches are given precedence over pica matches. For example, if the answer is 249 and the user guesses 444, the response should be "fermi" (one digit right and in the right place). All fermis should be reported before any picas in the clue string.
4. (75 points) Define a class called Jotto that can be used to play the game of Jotto. It should have the following public methods:
|
initialize |
Your public constructor (takes no arguments) |
|
play1 |
Plays Jotto with the user with the computer picking a word at random from the dictionary for the user to guess. Reports the total guesses the user makes before getting the right answer. |
|
play2 |
Plays Jotto with the user with the user picking a word for the computer to guess. If the word is unknown to the computer and the user gives appropriate clues, the program congratulates the user. If the user gives incorrect clues, the computer reports all incorrect clues in the order in which they were given. |
|
jots_for(word1, word2) |
Takes two strings as parameters and returns an integer indicating the number of jots that should be reported for this combination, as described below. |
You should not have any public methods other than these, although you may have as many private methods as you want.
Your program will need to read in the Jotto dictionary. In Jotto you compare two words for pairs of letters that match. Each match is called a jot. Unlike Bagels, it doesn't matter whether the match is in the correct position or not. But a given pair of letters can match only once. For example, for SUGAR and SEEPS the number of jots would be reported as1 because the "S" in "SUGAR" matches one of the S's in "SEEPS" (but not both). Notice that it is possible to get 5 jots and still not have the right answer. For example, if the answer is TIERS and you guess TIRES, you'd be told that you have 5 jots (all letters right, but you still don't have the right word).
In the play1 method, your program should pick a word at random from the dictionary. It then allows the user to guess words. If the user guesses something that is not 5 letters long, you should produce an error message. In Jotto, the guesses themselves must be legal words. So you should also make sure that the user guesses words that are in the dictionary. If they aren't in the dictionary, you should reject them. For each guess made by the user, the program indicates the number of jots. Play continues until the user guesses the right word, at which time you report how many guesses it took.
In the play2 method, your program is trying to guess a word that the user has in mind. You should do this by working with a copy of the dictionary. Initially all of the words are candidates. You always pick a word at random from your list of candidates. You then ask the user if you got it right, making sure they answer "y" or "n". If you got it right, you report how many guesses it took you. Otherwise you ask for the number of jots, making sure that the user enters a number between 0 and 5. You then prune the list of words to just those that have this number of jots when compared to your guess and by eliminating the word that was guessed. Eventually your program will either guess the word correctly or will run out of words to guess. If it runs out of words to guess, it should ask what the answer was, again making sure that the user gives you a 5-character string (although you don't have to guarantee that they are letters). Your program should remember all of the clues given by the user so that it can make sure that the user told the truth. If the user did, it should congratulate the user on stumping the computer. If the user lied, your program should report each incorrect clue in the order given. In terms of error checking, it's okay to let illegal numbers be interpreted as 0 when you ask for the number of jots so that you can call to_i to convert from a string to an integer.
In solving these problems, you will want to make use of either the print method or the printf method. The printf is similar to printf in C and Java. The print command takes a series of values to print separated by commas, as in:
print "x = ", x, "\n"
Notice that you need to include the "\n" to get print to produce an entire line of output. You might also find it useful to use the to_i method of the String class to convert from a String to an integer, the rand(n) method that returns an integer between 0 and (n – 1), the member? method of the array class, and for Jotto folks, the upcase method of the String class that converts to uppercase. The to_i method of the String class has a slightly odd behavior that "3.45".to_i returns 3, but we’ll just live with that behavior for these programs (that means, for example, that some user input errors won’t be caught by our programs).
There are main programs called bagels.rb, jotto1.rb and jotto2.rb available from the class web page. Sample executions using these programs are provided below. Your program should exactly reproduce the format of these logs.
Bagels Log of Execution (user input underlined)
attu1% ruby bagels.rb
Welcome to the game of Bagels
How many digits? -8
Enter a positive integer
How many digits? foo
Enter a positive integer
How many digits? 3
Your guess? 1234
Please enter a 3-digit number
Your guess? 12
Please enter a 3-digit number
Your guess? 123
clue: fermi pica pica
Your guess? 132
You got it right in 2 guesses
Play again? maybe
Enter y or n
Play again? nope
Enter y or n
Play again? y
Welcome to the game of Bagels
How many digits? 3
Your guess? 123
clue: fermi
Your guess? 456
clue: pica
Your guess? 789
clue: fermi
Your guess? 149
clue: bagels
Your guess? 683
You got it right in 5 guesses
Play again? y
Welcome to the game of Bagels
How many digits? 3
Your guess? 123
clue: fermi
Your guess? 456
clue: pica
Your guess? 789
clue: pica
Your guess? 167
clue: fermi
Your guess? 148
clue: fermi pica
Your guess? 169
clue: fermi pica
Your guess? 347
clue: pica
Your guess? 194
You got it right in 8 guesses
Play again? y
Welcome to the game of Bagels
How many digits? 3
Your guess? 123
clue: pica
Your guess? 456
clue: pica pica
Your guess? 265
clue: pica pica
Your guess? 534
clue: fermi pica
Your guess? 542
You got it right in 5 guesses
Play again? y
Welcome to the game of Bagels
How many digits? 3
Your guess? 123
clue: bagels
Your guess? 456
clue: bagels
Your guess? 789
clue: fermi
Your guess? 777
You got it right in 4 guesses
Play again? n
Total games = 5
Total guesses = 24
Guesses/game = 4.8
Jotto1 Log of Execution (user input underlined)
attu1% ruby jotto1.rb
Welcome to Jotto. I'll let you try to guess my 5-letter word.
Your guess? strip
1 jot(s)
Your guess? chips
1 jot(s)
Your guess? abc
Enter a 5-letter word
Your guess? abcdefg
Enter a 5-letter word
Your guess? abcde
Not in the dictionary...try again
Your guess? meets
3 jot(s)
Your guess? stain
3 jot(s)
Your guess? seams
4 jot(s)
Your guess? smear
4 jot(s)
Your guess? shame
4 jot(s)
Your guess? means
5 jot(s)
Your guess? names
You got it right in 9 guess(es)
Jotto2 Log of Execution (user input underlined)
attu1% ruby jotto2.rb
Welcome to Jotto. I'll try to guess your 5-letter word.
I guess SLAPS
Am I right? maybe
Enter y or n
Am I right? yup
Enter y or n
Am I right? n
Okay, how many jots? 2
I guess SHYLY
Am I right? n
Okay, how many jots? -8
between 0 and 5 please
Okay, how many jots? 9
between 0 and 5 please
Okay, how many jots? 1
I guess PANTY
Am I right? n
Okay, how many jots? 0
I guess FUSES
Am I right? n
Okay, how many jots? 2
I guess RISKS
Am I right? n
Okay, how many jots? 2
I give up
What was your word? spek
Enter a 5-letter word
What was your word? speaky
Enter a 5-letter word
What was your word? speak
You said SLAPS gets 2 jot(s) when it really gets 3 jot(s)
You said PANTY gets 0 jot(s) when it really gets 2 jot(s)
attu1% ruby jotto2.rb
Welcome to Jotto. I'll try to guess your 5-letter word.
I guess GRAMS
Am I right? n
Okay, how many jots? 1
I guess ACHED
Am I right? n
Okay, how many jots? 0
I guess BRUNT
Am I right? n
Okay, how many jots? 1
I guess MOTIF
Am I right? n
Okay, how many jots? 2
I guess SPLIT
Am I right? y
I got it right in 5 guess(es)
attu1% ruby jotto2.rb
Welcome to Jotto. I'll try to guess your 5-letter word.
I guess RONDA
Am I right? n
Okay, how many jots? 0
I guess HILLS
Am I right? n
Okay, how many jots? 1
I guess VICKY
Am I right? n
Okay, how many jots? 2
I guess CHUCK
Am I right? n
Okay, how many jots? 0
I guess JIMMY
Am I right? n
Okay, how many jots? 2
I guess WITTY
Am I right? n
Okay, how many jots? 2
I give up
What was your word? zippy
Congratulations, you stumped me.
attu4% ruby jotto2.rb
Welcome to Jotto. I'll try to guess your 5-letter word.
I guess FRESH
Am I right? n
Okay, how many jots? 5
I give up
What was your word? fresh
I guessed that word and you said I was wrong