Here is an online programming contest we are planning to have.
What could be possible approaches to solving the same?
From a random IRC (Internet Relay Chat) log, a small percentage of the user nicknames will be randomly deleted. The participant’s code must be able to fill in the missing user nicks. In other words, this event requires you to come up with an intelligent program that can figure out “who could have said what”.
It may be assumed that all communication will be in modern English, with or without punctuation.
For example -
Original Chat:
...
<user1>: Hey!
<user2>: Hello! Where are you from, user1?
<user3>: Can anybody help me out with Gnome installation?
<user1>: India. user3, do you have the X Windows System installed?
<user2>: Cool. What is Gnome, user3?
<user3>: I don’t know. How do I check?
<user3>: Its a desktop environment, user2.
<user2>: Oh yeah! Just googled.
<user1>: Type “startx” on the command line. Login as root and type “apt-get install gnome”.
<user3>: Thanks!
<user5>: I’m root, obey me!
<user2>: Huh?!
<user3>: user2, you better start using Linux!
...
The following only will be given to the participant.
Chat log with some nicks deleted:
..
: Hey! : Hello! Where are you from, user1? : Can anybody help me out with Gnome installation? : India. user3, do you have the X Windows System installed? : Cool. What is Gnome, user3? <%%%>: I don’t know. How do I check? <%%%>: Its a desktop environment, user2. : Oh yeah! Just googled. : Type “startx” on the command line. Login as root and type “apt-get install gnome”. : Thanks! <%%%>: I’m root, obey me! <%%%>: Huh?! : user2, you better start using Linux! ...
The participant’s code will have the task of replacing "<%%%>s" with the appropriate user nicks. In ambiguous cases, like the random comment by in the above example (which could have been said by any other user too!), the code should indicate the same.