Exercise 5.1 (markov.py). Write a program that takes in a filename, reads each line of the file, converts the lines into a format convenient for making Markov chains, and then prints out a new sentence randomly generated from the data, based on the Markov algorithm. You may use any file you wish for test input, though alice.txt and cthulhu.txt are provided on Canvas. alice.txt is a slightly edited version of the complete text of Lewis Carroll's Alice's Adventures in Wonderland, taken from https://www.gutenberg.org/files/11/11-h/11-h.htm. cthulhu.txt is a slightly edited version of the complete text of H.P. Lovecrafts's The Call of Cthulhu, taken from http://www.hplovecraft.com/writings/texts/fiction/cc.aspx. When parsing the input file, you should ignore any blank lines. Treat the lines in the file as separate sentences. That is, if "Hello, how are you?" and "Where are my keys?" are lines in a file, then "you?" should not be followed by "Where" when generating a chain. However, "are" should be allowed to be followed by either "you?" or "my", as seen in Figure 1. When creating a new chain, the first element should always be a randomly selected first word of a line in the file. The chain should end when either: • There are no valid choices to continue the sentence with. ⚫ The sentence has reached a length of 100 words. Remember that you need to account for different frequencies of possible follow words. That is, a situation like in Figure 2 where the word "a" is followed by two "is" and one "known". You need to account for whatever word frequencies might come up within your input file. Hint 3 You may find dictionaries to be useful in implementing Markov chains. For example, the Markov chain in Figure 1 could be represented using this dictionary: 'Hello,': ['how'], 'how': ['are'], 2 'Where': ['are'], 'are': ['you', 'my'], 'you?': [], 'my': ['keys'], 'keys?': []} To generate a Markov chain, pick a random word from a list of first words. Then pick a random word that comes after the first word. Keep picking random next words until no more words are left or until the length limit is reached.