Central Character
Purpose: branching and looping
Network theory has a host of applications. One fun application is to find the central character in a novel. Such an analysis was recently performed on the hugely popular book "The Songs of Fire and Ice" by George R.R. Martin which has been made into the the television show "Game of Thrones.. 1" The central character is defined by the one with the most connections to other characters. The authors of the paper considered two characters to be connected if their names appeared within 17 words of each other.
In this problem we will apply a similar procedure to the book "Storybook Treasury of Dick and Jane and Friends" by William S. Gray. This book was among the first books your parents (or grandparents) studied when they were learning to read. This book is very short and has only three main characters : Dick, Jane, and Sally. Due to the simplicity of the book we consider the two characters to be connected if their names appear within 5 words of each other.
See Dick run. Run Dick run. See Jane run. Dick likes to play with Spot. Sally likes Puff. Dick likes Puff.
In the above text :
Dick has 3 connections : 2 with Jane and 1 with Sally
Jane has 2 connections: 2 with Dick
Sally has 1 connection: 1 with Dick
Your task to to read in a set of text and determine which of the 3 main characters is the most connected.
Input: The first line of input will contain an integer t representing the number of test cases to be tested. Each test case will be on 2lines. The first line of the test case will contain a single integer n representing the number of words to be considered. The second line of the test case hold n words each words. Each word separated a single space with no punctuation.
Output: For each test case your program will display which character name {Dick, Jane or Sally }which has the most connections in the text, followed by the number of connections on a single line. If there is a tie, list the character that comes first alphabetically.
Sample Input
1
21
See Dick run Run Dick run See Jane run Dick likes to play with Spot Sally likes Puff Dick likes Puff
Sample Output
Dick 3
Possible Algorithm
(the connection length (number of words between a connection should be a named constant)) You can read each word
If the word is one of the three characters
check the last location of the other two characters and if they are within 5 update the number of connections of that character and the character just read update the last location of the character just read
After all the words are read, compute the character with maximum number of connections print out the result