Problem: Six Degrees of Villainy

You are given a file called DrWhoVillains.tsv. It is a TAB separated file containing villains in a science fiction show called Dr. Who. The show is known for its extremely low budget and silly creature effects. Although the modern version is slicky produced and has a higher budget, it still pays homage to the original look and feel of the old villains. Look at the picture of a Dalek (one of the main villains) above to see this for yourself. Each line of DrWhoVillains.tsv contains information on a single villain. No villain is repeated on more than one line. Each line contains the following information (separated by TABs):

1. Villain: name of the villain (e.g. Dalek)
2. Year first: the first year this villain was introduced
3. Year last: the last year this villain was shown
4. no.: the list of doctor ids with this villain, separated by commas
5. Doctor actor: the list of actors for each doctor above
6. Episodes: number of episodes featuring this villain
7. Motivation (invasion earth, kill humans, etc): the description of the mainmotivation of this villain
8. Story titles: the titles of the stories that the villain was involved with,a list of strings separated by commas.

Note that some of the names of the villains are very long!

Your program must do the following:

1. Read through the file to find the villain names and the (set of) stories for each villain. Be careful: the file is manually created and may have repeated story titles, incorrect case, extra spaces before and after names, etc. We will guarantee that each villain only appears on one line and that there are no misspellings, but you must use consistent capitalization and sets to find unique stories.
2. Ask the user for the name of a target villain to try to reach: we are going to see how manysteps it will take us to find this villain in a chain from one of the top ten most popular villains.
3. Find the top 10 most popular villains: those with the top 10 highest number of stories listedin the file and display them to the user, numbered 1 to 10, in decreasing order of popularity. When there is a tie, break it in reverse alphabetic order (starting at Z and going to A). These top ten villains become our initial candidates.
4. In a loop, do the following:
   • Display the candidate villains.
   • Ask the user for a villain number from the candidates list.
   • If the user enters something other than a number from 1 up to and including the numberof candidates, the program displays the current list again and asks for another input.
   • If the user enters a valid option then check if the villain at the index (actually one lessthan the index) in the candidates list is the target villain. If so, report that the target villain has been found and exit. This output should include the number of steps to get to this villain. Incorrect input does not count as a step. If the villain is found right away it is 1 step.
   • Otherwise, print out how many stories this selected candidate villain was in and thengenerate new candidate villains by finding out all of those villains who appeared in a story with the currently selected candidate villain. Order the new candidate villains in the same way as the original villains.

Some Hints

We are not going to tell you exactly how to structure your code, but we are going to give you a few hints.

1. Parsing the villain file is an important of this HW. We suggest you create a function thattakes a single string parameter corresponding to a single line of the input file, parses that line, and then returns a list containing:

[number of shows, villain name, set of show titles]

Think about this a little. It is not overly hard if you realize that we only need information from 2 of the 8 fields contained in the file. The remaining 6 fields Year first, Year last, Doc. no., Doc. Actor, Episodes, and Motivation are not used in this assignment. Take the line, split it at the TABS. Item[0] is the villain name and item[7] is a comma separated string that you can split and turn into a set of story titles.

Test your parsing very thoroughly before proceeding. If you come to use for help after you believe you have parsing working, you must be prepared to demonstrate to us that it is correct!

2. If you maintain a list of lists, for example if you make a list of lists returned by the parsingfunction just described, it is simple to sort this list. As mentioned at the start of this assignment, check out py for code that will help you with this. If you understand example_list_of_lists.py you will see how to easily do the sorting required by this project as well. We suggest you experiment by modifing that program to put all of the states at the same rank, and look at the sorted list before you try the sorting in your program.
3. Start small and build up. Make sure you can parse the lines correctly into a list first and testit. Then build up the list of lists. Then sort it. Then figure out how to generate the list of villains, etc. Once your program is working correctly, get the formatting right.
4. Lab 8 touches on some of the same topics and requires many of the same skills required here.

If you are having problems, work through the material in Lab 8. It will help.

Expected Output

Below you can see the expected functioning of this program with the file we gave you (note: we might change the file in the homework submission server):

Who are you trying to reach? Neo-Nazis, WindSOR Neo-Nazis, WindSOR

1. Daleks
2. Cybermen
3. Master (the)
4. Dalek Supreme (Supreme Dalek), inc Progenitor
5. Sontarans
6. Ice Warriors (inc benevolent appearences)
7. Davros
8. Silurians (exc Sea Devils)
9. Kovarian, Madame
10. Cyber-leader

Enter a selection => 2 2

Cybermen appeared in 24 stories and overlapped with:

1. Daleks
2. Master (the)
3. Dalek Supreme (Supreme Dalek), inc Progenitor
4. Sontarans
5. Ice Warriors (inc benevolent appearences)
6. Silurians (exc Sea Devils)
7. Kovarian, Madame
8. Cyber-leader
9. Black Guardian (the)
10. Ood, the (Oodkind), inc benevolent appearances
11. Cybermat
12. Borusa
13. Yeti
14. Terrible Zodin
15. Rassilon
16. Lytton, Commander Gustav
17. Cyber-controller
18. Cult of Skaro (inc Dalek Sec and three others)
19. Atraxi
20. van Statten, Henry
21. War Lord
22. War Chief
23. Vaughn, Tobias
24. Raston Warrior Robot
25. Peinforte, Lady
26. Neo-Nazis, Windsor
27. Mawdryn
28. Manton, Colonel
29. Mailer, Harry
30. Lumic, John
31. Kellman
32. Keller Machine
33. Kalik
34. Headless Monks
35. Hartman, Yvonne
36. Hartigan, Mercy
37. Drashigs
38. De Flores
39. Cybershades
40. Cyberman Android
41. Alliance onscreen Daleks, Cybermen, Sontarans & Autons, (cameos Silurians, Sycorax,

Enter a selection => 38 38

De Flores appeared in 1 story and overlapped with:

1. Cybermen
2. Cyber-leader
3. Peinforte, Lady
4. Neo-Nazis, Windsor

Enter a selection => 4 4

You reached the villain Neo-Nazis, Windsor in 3 steps.

Have a nice day.

A second example:

Who are you trying to reach? Daleks

Daleks

1. Daleks
2. Cybermen
3. Master (the)
4. Dalek Supreme (Supreme Dalek), inc Progenitor
5. Sontarans
6. Ice Warriors (inc benevolent appearences)
7. Davros
8. Silurians (exc Sea Devils)
9. Kovarian, Madame
10. Cyber-leader

Enter a selection => stop stop

1. Daleks
2. Cybermen
3. Master (the)
4. Dalek Supreme (Supreme Dalek), inc Progenitor
5. Sontarans
6. Ice Warriors (inc benevolent appearences)
7. Davros
8. Silurians (exc Sea Devils)
9. Kovarian, Madame
10. Cyber-leader

Enter a selection => -1 -1

1. Daleks
2. Cybermen
3. Master (the)
4. Dalek Supreme (Supreme Dalek), inc Progenitor
5. Sontarans
6. Ice Warriors (inc benevolent appearences)
7. Davros
8. Silurians (exc Sea Devils)
9. Kovarian, Madame
10. Cyber-leader

Enter a selection => 1 1

You reached the villain Daleks in 1 steps.

Have a nice day.