0. Introduction.

In this assignment, you will write a Python program that is given example words, and generates random words that resemble them. For example, after being given the last names of all U.S. presidents, the program generated the names BumpRoe, Cartoon, Forthis, Fovenay, Gaylton, Haneram, Hansoro, Madiela, Ninasoo, Relayle, Ronburd, and Wanhumo. Perhaps these will be the names of future presidents. It is claimed that the names of some companies and commercial products were produced by programs similar to this one.

1. Theory.

For this project, you need an algorithm that generates random integers. You also need an algorithm that records example words, and another algorithm that uses the random integers and example words to generate random words.

Random integers. No algorithm can generate truly random integers, but it can generate pseudo-random integers that seem random, even though theyre not. Python has its own random number generator, but for this project you must implement your own. The Park-Miller algorithm (named for its inventors) is a simple way to generate a sequence of pseudo-random integers. It works like this. Let N be an integer called the seed. The seed is the first term of the sequence, and must be between 1 and 2 2. Starting from N, later terms N, N ..., are produced by the following equation.

N_k+1 = (7⁵ N_k) % (2³¹ 1)

Here 7 is 16807, and 2 is 2147483648. The operator multiplies two integers, and the operator %returns the remainder after dividing one integer by another. You will always get the same sequence of integers for a given seed. For example, if you start with the seed 101, then you get a sequence whose first few terms are 1697507, 612712738, 678900201, 695061696, 1738368639, 246698238, 1613847356, and 1214050682. Some of these integers are large, but you can make them smaller by using the % operator again. If N is an integer from the sequence, then N % M gives you an integer between 0 and M 1. For example, if you need a pseudo-random integer from 0 to 9, then you write N % 10. You can use this to choose a random element from a sequence. If S is a sequence, then the Python expressionS[N % len(S)] returns a randomly-chosen element of S.

Recording example words. Heres how to record example words. A letter is a single-character string, 'A''Z' and 'a''z'. Suppose that first is a string of letters, and is initially empty. As its name suggests, first will hold the first letter of each example word. Also suppose that follow is a dictionary, also initially empty, whose keys are letters, and whose values are strings of letters. The dictionary follow will hold strings of letters that can follow other letters. If youre given the example word 'Trump', then you add 'T' to first, because 'T' is the first letter of the word. You also add 'r' to the string in follow that is the value of the key 'T', because 'r' follows 'T'. Similarly, you add 'u' to the string that is the value of the key 'r', because 'u'follows 'r'. You add 'm' to the string that is the value of the key 'u', because 'm' follows 'u'. Finally, you add 'p' to the string that is the value of the key 'm' because 'p' follows 'm'. After many example words, first will record the first letters of each one, and follow will record how letters follow one another in the example words. Letters may appear more than once in the string first, and in the strings from follow.

Generating random words. Heres how to use first and follow to generate a random word, one letter at a time. You get the first letter of the word by randomly choosing it from first. Next, you look up the first letter in follow, obtaining a string of possible letters. You get the second letter by randomly choosing it from that string. Then, you look up the second letter in follow, obtaining another string. You get the third letter by randomly choosing it from that string. You continue like this, choosing letters from strings, and concatenating them together, until youve constructed the entire word. The number of times a letter appears in a string records how often that letter appeared in the example words. As a result, if you choose a letter at random from a string, then it is more likely to be chosen if it appeared often. Also, follow records how letters followed other letters in the example words. This lets you generate words that are roughly similar to the ones that were given as examples. One potential problem remains. While youre generating a random word, you may find that there is no string in follow for some letter. If this happens, then you choose a letter at random from first instead, and continue generating the word as before. The Python-2 expressionfollow.has_key(l) tests if there is a string in follow for the letter l. The Python-3 equivalent is l in follow.

2. Implementation.

You must write two Python classes. The first class must be called Random, and it must implement the Park-Miller random number generator discussed in section 1. The class Random must have the following methods.

__init__(self, seed)

(5 points.) Initialize an instance of Random with the integer seed. Assume that seed is in the proper range for the Park-Miller algorithm to work.

next(self, range)

(5 points.) Generate the next random number in the sequence. Use it to return a nonnegative integer greater than or equal to 0, but strictly less than the integer range. Return that random number. Assume that range is an integer greater than 0.

choose(self, characters)

(5 points.) Choose a character from the string characters at random, using an index obtained by calling next. Return that character. You may assume that characters is not empty.

The second class must be called Words, and it must implement the random word generation algorithm discussed in section 1. The class Words must have the following methods.

__init__(self, seed)

(5 points.) Create private variables first, follow, and random. The variable firstmust be an empty string. The variable follow must be an empty dictionary. The variable random must be an instance of Random, whose seed is the integer seed. You may assume that seed is in the proper range for the Park-Miller algorithm to work.

add(self, word)

(10 points.) Add the string word as a new example, using first and follow as described in section 1. You may assume that word is made up entirely of letters, and that it has at least one letter. Return None.

make(self, size)

(10 points.) Create a new example word using first, follow, and random as described in section 1. The word must be a string with exactly size letters. Return that string. You may assume that size is an integer greater than or equal to 0.

For efficiency, first must be a string, and the keys and values of follow must also be strings. You will receive ZERO POINTS for this project if you use lists or tuples instead of strings! My code for Random is about half a page of code, and its methods have one to three lines each. My code for Words is about one page. Python can be very concise! If you find yourself writing much more code than this, then you do not understand this assignment, and you should ask for help.

3. Example.

The random names from part 0 were generated by the following fragment of Python code. First, a new instance of the class Words is created, called prez. Then prez is given the last names of all U.S. presidents. Some names appear more than once because a president served for two non-consecutive terms, or because two presidents had the same last name.

prez = Words(101) prez.add('Washington') prez.add('Adams') prez.add('Jefferson') prez.add('Madison') prez.add('Monroe') prez.add('Adams') prez.add('Jackson') prez.add('Vanburen') prez.add('Harrison') prez.add('Tyler') prez.add('Polk') prez.add('Taylor') prez.add('Fillmore') prez.add('Pierce') prez.add('Buchanan') prez.add('Lincoln') prez.add('Johnson') prez.add('Grant') prez.add('Hayes') prez.add('Garfield') prez.add('Arthur') prez.add('Cleveland') prez.add('Harrison') prez.add('Cleveland') prez.add('Mckinley') prez.add('Roosevelt') prez.add('Taft') prez.add('Wilson') prez.add('Harding') prez.add('Coolidge') prez.add('Hoover') prez.add('Roosevelt') prez.add('Truman') prez.add('Eisenhower') prez.add('Kennedy') prez.add('Johnson') prez.add('Nixon') prez.add('Ford') prez.add('Carter') prez.add('Reagan') prez.add('Bush') prez.add('Clinton') prez.add('Bush') prez.add('Obama') prez.add('Trump')

After this, each call to prez.make(7) returns a new seven-letter word, roughly similar to the names that prez was given. Some look more like English words than others. The longer the words, the less they look like English.