handout #17
CS341—Programming Languages
Programming Assignment #8 (Ruby)
due 11 pm Friday, 3/9/07
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. 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.
You should use a 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. 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
>> sum = 0
=> 0
>> 28.factors {|n| sum +=
n}
=> nil
>> sum
=> 56
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.
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.
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 putlic 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 adds the word
to the dictionary. 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 aseries 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.
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? 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.