Connection Status:
Competition Arena > Spamatronic

Spamatronic

SRM 180 · 2004-01-22 · by Eeyore

SRM 180 · 2004-01-22 · by Eeyore · String Manipulation, String Parsing
Class Name: Spamatronic
Return Type: int[]
Method Name: filter
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Spamatronic Corporation made its mark by selling unsolicited commercial email delivery systems, and has lately expanded into the lucrative business of filtering unsolicited commercial email. You have been hired to implement the adaptive filtering algorithm devised by Spamatronic's research department. The premise of this algorithm is that new spam is composed largely of old spam.

Given a corpus of email messages that are known to be spam, consider the tokens that occur in it. A token is defined as a sequence of letters ('A' though 'Z' and 'a' through 'z') that are not adjacent to any other letters in the text. Since the Spamatronic algorithm is case-insensitive, all token occurrences are rendered in lowercase, and then reduced to a token set in which each token appears exactly once. For example, the token set derived from the messages 


    Good day, sir. It is with good will and confidence that I
    make this urgent and private business proposal to you.

and 


    Herbalize your bald spot! Gentle herbs flush negative ions
    from your system and stimulate super-growth. Gain confidence!

is the following when sorted alphabetically. 


    {"and", "bald", "business", "confidence", "day", "flush", "from",
    "gain", "gentle", "good", "growth", "herbalize", "herbs", "i", "ions",
    "is", "it", "make", "negative", "private", "proposal", "sir", "spot",
    "stimulate", "super", "system", "that", "this", "to", "urgent",
    "will", "with", "you", "your"}

Now consider a newly arrived email message. If at least 75% of the tokens in its token set also appear in the token set of the spam corpus, the filtering algorithm decides that this message is a piece of spam. It is deleted from the user's mailbox and added to the spam corpus so that it may influence future filtering decisions.

You are given two String[]s, knownSpam and newMail. The former contains the initial spam corpus, while the latter is a collection of recently arrived email. Each String element constitutes one whole message. Use the Spamatronic adaptive filtering algorithm to process the messages of newMail in the given order, and return a int[] containing the zero-based indices, in ascending order, of the messages that are not spam.

Constraints

  • knownSpam and newMail each contain between 1 and 50 elements, inclusive
  • each element of knownSpam and newMail is between 1 and 50 characters long, inclusive
  • each character in every element of knownSpam and newMail is a printable character with an ASCII value between 32 and 126, inclusive
  • each element of newMail will contain at least one token.
Examples
0)
{"This is a vile piece of spam."}
{"Spam is spiced ham.",
 "Spam is VILE!",
 "Spam is not vile."}
Returns: { 0 }

The algorithm is case-insensitive.

1)
{"We have the best mortgage rates. Refinance today.",
 "Money-making opportunity! $5000/week potential!!!",
 "Don't Feel Short; try Elevator Shoes for increase.",
 "All-new pics: Stacy, Tiffany, Donner, and Blitzen."}
{"5000 bucks for shoes?",
 "Short bucks for new shoes?"}
Returns: { 0 }

Under our definition, "5000" is not a token

2)
{"We have the best mortgage rates. Refinance today.",
 "Money-making opportunity! $5000/week potential!!!",
 "Don't Feel Short; try Elevator Shoes for increase.",
 "All-new pics: Stacy, Tiffany, Donner, and Blitzen."}
{"On, Dasher! On, Dancer! On, Donner and Blitzen!"}
Returns: { 0 }

Our algorithm counts the members of a token set, and the number of times a token occurs in the text is irrelevant.

3)
{"We have the best mortgage rates. Refinance today.",
 "Money-making opportunity! $5000/week potential!!!",
 "Don't Feel Short; try Elevator Shoes for increase.",
 "All-new pics: Stacy, Tiffany, Donner, and Blitzen."}
{"Try the prime ribs.",
 "Donner: New Prime Rates Today",
 "Try the prime ribs."}
Returns: { 0 }

The order in which new mail arrives is significant.

4)
{"One, two, buckle my shoe.",
 "Eins, zwei, polizei.",
 "On the first day of Christmas, my true love",
 "gave to me a partridge in a pear tree."}
{"Christmas shoe buckle madness!",
 "Partridge polizei madness day!",
 "I did not shoot the deputy.",
 "The second day of Christmas, a partridge bit me."}
Returns: { 2 }

Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Spamatronic with a public method vector<int> filter(vector<string> knownSpam, vector<string> newMail) · 78 test cases · 2 s / 256 MB per case

Submitting as anonymous